AOBA's Information Processing Education
１９９７／０９／２１
注意１：このページは、回線を切断した後でゆっくりご覧になってください（テキストを印刷する場合は、その取り扱いに注意してください）。
注意２：背景が白地の画面を長時間見つめていると頭が痛くなってしまいますので、ここは背景をグレーにしています。
「平成３年 第１種 午前 問８」 問８ 表探索に関する次の記述中の（ ）に入れるべき適切な字句を、解答群の中から選べ。解答は重複して選んでもよい。
10,000個の相異なる要素が、キーの昇順に整列された表がある。この表を外部から入力されたデータのキーをもとに探索して、該当するキーの要素を取り出す方法を考える。ただし、入力キーは一様分布しているものとする。また、入力キーの値が表中にないこともある。
この表を探索する方法として次の(1)，(2)の方法を考える。
(1)この表を先頭から順次比較して、該当キーを見付け出す。
(2)この表を１ブロックＸ個で、10,000／Ｘ個（小数点以下切上げ）のブロックに分割し、目的キーがどのブロックにあるかを、先頭ブロックから順に、各ブロックの最後尾のキー（各ブロックの中で最も大きなキー）だけ逐次探索し、該当ブロックを見付ける。次に該当ブロック内を逐次探索して、該当キーを見付ける。
(1)の逐次探索の場合、平均比較回数は、約（ ａ ）回であり、最大比較回数は、（ ｂ ）回である。
(2)の場合、Ｘの値によって、平均比較回数は変化する。すなわち、全要素をＮとすると、平均探索回数は、式（ ｃ ）で表せる。
Ｎが10,000のとき、式（ ｃ ）が最小となるＸは、（ ｄ ）であるから、平均探索回数は、（ ｅ ）回である。
ａ，ｂに関する解答群
ア 1,000 イ 2,000 ウ 3,333 エ 5,000 オ 10,000
ｃに関する解答群
ア Ｎ／Ｘ イ Ｎ／（２Ｘ） ウ Ｘ＋（Ｎ／Ｘ） エ （Ｘ／２）＋（Ｎ／（２Ｘ）） オ Ｘ2＋（Ｎ／Ｘ2） ｄ，ｅに関する解答群
ア ８ イ ９ ウ 12 エ 13 オ 14 カ 15 キ 50 ク 100 ケ 150 コ 200
解説 情報処理に関する知識は必要ない問題です。ただし、設問ｄを解答するには少しだけ数学の知識が必要でした。ここが分かれば全問正解でしょう。
(1)の方法は単純に先頭からひとつづつキーを比較する方法です。対して(2)の方法は要素をブロックに分割し、まず求める要素がどのブロックにあるかを見付け、次にブロック内を(1)と同じ方法で探索します。
つまり(2)の方法は、ブロックの代表値（この問題ではブロックの最後尾のキー）の比較とブロック内の要素の比較、と２段階で探索を行います。ａ，ｂについて
最小比較回数は１回、最大比較回数は10,000回。
平均比較回数＝（最小比較回数＋最大比較回数）／２＝（１＋１００００）／２≒5,000回
これについては解説はいらないでしょう。
ｃについて
まず、求める要素がどのブロックにあるかを見付けるための探索（比較）回数を考えます。
全要素数がＮ個、１ブロックの要素数がＸ個ならば、ブロックの数はＮ／Ｘ個です。
求める要素がどのブロックにあるかを見付けるための平均探索回数は、ブロック数の約半分ですので、Ｎ／（２Ｘ）となります。次に、ブロック内の探索回数を考えます。
１ブロックがＸ個ならば、ブロック内の平均探索回数はこの値の約半分ですので、Ｘ／２です。したがって、(2)の場合の平均探索回数はこれらの値を加算して、
（Ｘ／２）＋（Ｎ／（２Ｘ）） です。
ｄについて
これがちょっとやっかいでしたね。高校１年（２年だったかな？）の時の数学の授業を思い出しましょう。
ここではくどくど解説せずに、結論だけ言います。関数ｆ（Ｘ）の値を最小にするＸは、ｆ（Ｘ）をＸで微分した式を０とおくことで求めることができます。これを本設問に適用します。つまり、
ｆ（Ｘ）＝（Ｘ／２）＋（Ｎ／（２Ｘ））
＝（１／２）＊Ｘ1＋（Ｎ／２）＊Ｘ-1 をＸで微分するのです。ｆ’（Ｘ）＝（１／２）−（Ｎ／２）＊Ｘ-2＝０
上記式のＮに１００００を代入して変形します。
Ｘ2＝１００００ したがって、Ｘ＝１００（負はありえないので除外）
ｅについて
設問ｃの解答、（Ｘ／２）＋（Ｎ／（２Ｘ））に、Ｎ＝１００００，Ｘ＝１００（設問ｄの解答）を代入することで求めることができます。
（Ｘ／２）＋（Ｎ／（２Ｘ））＝（１００／２）＋（１００００／（２＊１００））＝１００
と、こんなところでしょうか。
解答
ａ−エ ｂ−オ ｃ−エ ｄ−ク ｅ−ク