ジュニア問題/B倉庫
倉庫
ビーバー村の大工さんは，1番から31番の番号のついた31個の倉庫を作り，1番の倉庫から順に使っていきました。ところがある日，大工さんは何番の倉庫までを使っているかを忘れてしまいました。
ドアを開ける回数をできるだけ少なくしたい大工さんは，次のように何番の倉庫までを使っているかを調べることにしました。
まず，真ん中の16番の倉庫のドアを開けます。
その倉庫を使っているかどうかで，次の2つに場合分けをして，次に開けるドアを決めます。
もし，16番の倉庫が空ならば，1番から15番までを調べればいいことがわかります。ですから，今度は，その真ん中の8番の倉庫のドアを開けます。
もし，16番の倉庫を使っていれば，17番から31番までを調べればいいことがわかります。ですから，その真ん中の24番の倉庫のドアを開けます。
その後，開けた倉庫が空か使っているかによって同じように場合分けをするということを繰り返します。
1番から15番までを使っていることがわかりました。大工さんは何回ドアを開けたでしょうか？
- 解説を見る
- 正解は 5 回です．
- 1番から15番の倉庫を使っているので
- 16番の倉庫のドアを開けて，使っていないことが分かる（1回）
- 1番から15番の倉庫を調べるため，8番の倉庫のドアを開けて，使っていることが分かる（2回）
- 9番から15番の倉庫を調べるため，12番の倉庫のドアを開けて，使っていることが分かる（3回）
- 13番から15番の倉庫を調べるため，14番の倉庫のドアを開けて，使っていることが分かる（4回）
- 15番の倉庫のドアを開け，使っていることが分かる（5回）
- 1番から15番の倉庫を使っているので
- 解説
この方法は2分探索と呼ばれ，整列されたデータの中から探しているものを効率よく見つけ出すアルゴリズムです．
- 正解は 5 回です．
注があるものを除き, このサイトの内容物は
