令和5年秋季 午後プログラミング問題について
ゆちさん
(No.1)
和5年秋季 午後プログラミング問題について解説お願いいたします。
空欄 ウ、オに関してなんですが
正答はh1=2、h1=-2
自分の回答はh1>=2、h1<=-2でした。
これは正解になりますか?
また不正解だとしたら何が問題なのでしょうか?
空欄 ウ、オに関してなんですが
正答はh1=2、h1=-2
自分の回答はh1>=2、h1<=-2でした。
これは正解になりますか?
また不正解だとしたら何が問題なのでしょうか?
2024.07.24 11:37
boyonboyonさん
★AP シルバーマイスター
(No.2)
本文中にある下記の手順を実現するプログラムについて考えます。
①:T の左側の部分木の高さが T の右側の部分木の高さより2大きい場合
②:T を根とする部分木に対して右回転を行う。
③:ただし,T の左側の子ノード U について,U の右側の部分木の方が U の左側の部分木よりも高い場合は,
④:先に U を根とする部分木に対して左回転を行う。
①の条件は
height(t.left)が、height(t.right)より2大きい場合
height(t.left)=height(t.right)+2の場合
height(t.left)-height(t.right)=2の場合
になり
h1←height(t.left)-height(t.right)
とすれば、
h1=2の場合
と書くことができます。
②に対応するのは、
t←rotateR(t) の所
③の条件は、
//ただし、の部分は②より優先するという意味なのでプログラムでは先に書いてあります。
height(t.left.right)の方が、height(t.left.left)よりも高い場合は、
height(t.left.right)>height(t.left.left)の場合は、
height(t.left.right)-height(t.left.left)>0の場合は、
になり
h2←height(t.left.right) - height(t.left.left)
とすれば
h2>0の場合
と書けます。
④に対応するのは
t.left←rotateL(t.left)の所
少し長くなりましたが、問題文からプログラムを作っていくと上記のようになります。
逆に、条件を
h1>=2にするならば
文章では
T の左側の部分木の高さが T の右側の部分木の高さより2以上大きい場合
と書いてあるべきかと思います。
3,4,・・・になることはありませんね。
①:T の左側の部分木の高さが T の右側の部分木の高さより2大きい場合
②:T を根とする部分木に対して右回転を行う。
③:ただし,T の左側の子ノード U について,U の右側の部分木の方が U の左側の部分木よりも高い場合は,
④:先に U を根とする部分木に対して左回転を行う。
①の条件は
height(t.left)が、height(t.right)より2大きい場合
height(t.left)=height(t.right)+2の場合
height(t.left)-height(t.right)=2の場合
になり
h1←height(t.left)-height(t.right)
とすれば、
h1=2の場合
と書くことができます。
②に対応するのは、
t←rotateR(t) の所
③の条件は、
//ただし、の部分は②より優先するという意味なのでプログラムでは先に書いてあります。
height(t.left.right)の方が、height(t.left.left)よりも高い場合は、
height(t.left.right)>height(t.left.left)の場合は、
height(t.left.right)-height(t.left.left)>0の場合は、
になり
h2←height(t.left.right) - height(t.left.left)
とすれば
h2>0の場合
と書けます。
④に対応するのは
t.left←rotateL(t.left)の所
少し長くなりましたが、問題文からプログラムを作っていくと上記のようになります。
逆に、条件を
h1>=2にするならば
文章では
T の左側の部分木の高さが T の右側の部分木の高さより2以上大きい場合
と書いてあるべきかと思います。
3,4,・・・になることはありませんね。
2024.07.24 17:00