HOME»基本情報技術者試験掲示板»大滝みや子先生のかんたんアルゴリズム解法P133

基本情報技術者試験掲示板


[0073] 大滝みや子先生のかんたんアルゴリズム解法P133

 みなこさん(No.1) 
お世話になります。

標記の本、第2部第3章までひととおり読んでみたのですが、
P133のTRY!が特に分かりませんでした。

2分探索法で、プログラムの実行回数を聞かれています。
9つの要素の中からひとつの値を探すのですが、
最初は一つ目と九つめの間の、要素5、
2回目は一つ目と四つ目の間の、要素2、
3回目は三つ目と四つ目の間で、要素3(3+4/2で3.5小数点以下切り捨て)
がmidになりますよね。
最後に、要素4をチェックしないといけないのですが、
要素4は、要素4と要素3の間をmidとする、と云うことになって、
開始位置>終了位置、で探索不能で終わるのだと思ったのですが、
この要素4と要素3の比較も回数に入れるものなのですか?

答えは「4回」プログラムを実行する、とあります。

この問題を見て、最後は比較出来ないから答えは3回かなと思いました。
どなたか、解説してくださればと思います。
どうぞよろしくお願いいたします。
2012.12.10 13:09
海賊さん(No.2) 
みなこ様

α部分実行回数1回目  2回目  3回目  4回目  
low        1        1      3      4
high      9        4      4      4
mid        5        2      3      4

疑似言語の条件式に注目して下さい。
■  low≦high  かつ  idx=0
が継続条件です。
これを終了条件に変換します(ド・モルガンの法則を適用します。よく使います)
        low>high  または  idxは0でない
すなわち、Low=4、High=4の時は、まだ終了しないので4回目のループに入ります。そしてLow=5、High=4となって初めてlow>highを満たすのであαは実行されずプログラムは終了し、変数Idxは0のままとなります。

海賊




2012.12.11 10:11
 みなこさん(No.3) 
海賊さま

感動です!分かりやすいです。

lowとhighが同じ要素になることがあるんですね。
まだまだ読みこめていませんね。

海賊さまのように論理的な頭になりたいです。
何度もありがとうございます!
2012.12.11 10:31

返信投稿用フォーム

スパム防止のために初投稿日から30日経過したスレッドへの書き込みは禁止しています。

© 2010-2022 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop