HOME»応用情報技術者試験掲示板»平成19年春期 問9
投稿する
平成19年春期 問9 [3804]
完全2分木についてさん(No.1)
最大比較回数=log2要素数
上記の式について質問させてください。
例えば、
要素数が4の時は、最大比較回数は2回
要素数が8の時は、最大比較回数は3回
これは分かります。
ただ例えば
要素数が5である場合、
最大比較回数が3回となる意味が分かりません。
(色々調べてみたのですが)
最大比較回数は2回ではないのでしょうか。
どなたか教えていただけますと幸いです。
上記の式について質問させてください。
例えば、
要素数が4の時は、最大比較回数は2回
要素数が8の時は、最大比較回数は3回
これは分かります。
ただ例えば
要素数が5である場合、
最大比較回数が3回となる意味が分かりません。
(色々調べてみたのですが)
最大比較回数は2回ではないのでしょうか。
どなたか教えていただけますと幸いです。
2022.10.05 23:05
GinSanaさん(No.2)
★AP プラチナマイスター
平均比較回数は [log2N] 回、最大比較回数は[log2N]＋1回
です。
www.fe-siken.com/s/kakomon/20_aki/q13.html
基本情報 平成20年 問13 2分探索法の最大比較回数
です。
www.fe-siken.com/s/kakomon/20_aki/q13.html
基本情報 平成20年 問13 2分探索法の最大比較回数
2022.10.05 23:12
完全2分木についてさん(No.3)
ご教授いただきありがとうございます。
式で考えると分かるのですが、
実際に想像してみると分からないです、、
1,2,3,4,5 と並んでいて、5を探索する場合
3より大きい←比較1回目
4より大きい←比較2回目
となり、
比較3回目に達するパターンがないように思えまして。。
式で考えると分かるのですが、
実際に想像してみると分からないです、、
1,2,3,4,5 と並んでいて、5を探索する場合
3より大きい←比較1回目
4より大きい←比較2回目
となり、
比較3回目に達するパターンがないように思えまして。。
2022.10.05 23:57
Howitzerさん(No.4)
まず、完全2分木って要素数が４とか８とか５ってことはないです。
要素数は２のべき乗－１ですよ。
それは一旦忘れて、
5と等しい＝見つかった←比較3回目
※4の右側が5ではないかもしれない
要素数は２のべき乗－１ですよ。
それは一旦忘れて、
> 1,2,3,4,5 と並んでいて、5を探索する場合
> 3より大きい←比較1回目
> 4より大きい←比較2回目
5と等しい＝見つかった←比較3回目
※4の右側が5ではないかもしれない
2022.10.06 00:25
完全2分木についてさん(No.5)
ありがとうございます。
二分木と完全二分木は分けて考えるようにします。
あまり「要素数」を理解できていませんでした。
一旦完全二分木については、
根を含めた全要素数では理解しにくいので、
節(葉)が2倍になると、比較が1回増える
で理解します。
教えていただきありがとうございました。
二分木と完全二分木は分けて考えるようにします。
あまり「要素数」を理解できていませんでした。
一旦完全二分木については、
根を含めた全要素数では理解しにくいので、
節(葉)が2倍になると、比較が1回増える
で理解します。
教えていただきありがとうございました。
2022.10.06 22:21