→をクリックすると非真理設定が非表示になります。ページを再読み込みすると戻ります。
ksi.2のlexn.5では、値を探索する処理を書きました。端から順に値を見ていき、一致すれば終了、という方法を取りました。
しかし、我々の日常で物を探索するとき、常にこのような方法が取られているでしょうか？必ずしもそうではありません。
500人ほどが記載されている名簿があるとしましょう。この名簿に特定の人の名前が載っているかどうかを調べるのに、わざわざ端から見ていくというのでは大変です。このとき、辞書順この時代の辞書順って何なんでしょうね。に名前が並んだ名簿なら、端から見ていくことなく効率的に探すことができます。
ということで、このような探索をするmelfertという[指令](cersva)を書いていきましょう。なお、諸情報は次のように与えられているものとします。
| 自由 | 自由 | 戻る場所 | 目的の値 | 要素数 | 名簿の先頭の番地 |
「名簿の先頭の番地」「名簿の先頭の番地+4」「名簿の先頭の番地+8」…と要素が「要素数」個ある名簿を考え、「番地が増えれば必ず格納されている値も大きくなる」という性質が成り立っているとします。この名簿の中に目的の値があればf0に1を入れて[指令](cersva)を終了し、目的の値がなければf0に0を入れて[指令](cersva)を終了する、という仕様にしましょう。
とりあえず、終了箇所から考えましょう。
… nll molniv kRz 0 f0 kRz f5@ xx nll mol kRz 1 f0 kRz f5@ xx
こうしておけば、「見つかった」と確定したときにkRz mol xxし、「見つからなかった」と確定したときにkRz molniv xxとすればよくなります。
さて、具体的な探索方法について考えましょう。順番に並んでいる数を探索するとき、以下のような特徴があります。ある位置を見て目的の値より大きかったら、目的の値は（あれば）その位置より小さい番地にしかありえず、ある位置を見て目的の値より小さかったら、目的の値は（あれば）その位置より大きい番地にしかありえないのです。
ということは、「もしあるとしたらこの範囲しかない」というのを2つのfirjalを使って保持し、その中央あたりの値と目的の値を比較していって毎回区間を半分にしていけばよいわけです。
区間をどう保持するかですが、範囲の左端をf1、右端をf3に入れておきましょう。あとで番地を計算するときに便利になるよう、1番目の要素は0、2番目の要素は1といったふうに、1減らして保持しておきましょう。
処理が始まった段階では、左端は0で右端は要素数から1引いたものになります。ということで、その処理を書いていきましょう。
要素数の情報を得て、そこから1を引き、f3に入れます。
nll melfert kRz f5+8@ f3 nta 1 f3 kRz 0 f1 …
要素数が0以下のときにはmolnivに飛ぶようにしましょう。f3から1を引いた段階で負かどうかを確認すればいいですね。
nll melfert kRz f5+8@ f3 nta 1 f3 fi f3 0 xylo malkRz molniv xx kRz 0 f1 …
さて、今度は「範囲の真ん中にある値を読んで、それを目的の値と比較する」という処理を書いていきましょう。
… kRz f3 f0 ata f1 f0 dtosna 1 f0 kRz f0 f2 dRo 2 f2 ata f5+12@ f2 fi f2@ f5+4@ clo malkRz mol xx …
最初の3行で、f1とf3の平均がf0に入ります。次の3行では、f0をf2に複製し、f2を4倍してから名簿の先頭に足し合わせることにより、範囲の中央に対応する番地が得られます。最後に、これを目的の値と比較し、等しかったらmolへと飛びます。
ここまでのをまとめると、先頭あたりで
nll melfert kRz f5+8@ f3 nta 1 f3 fi f3 0 xylo malkRz molniv xx kRz 0 f1 …
とし、途中で
… kRz f3 f0 ata f1 f0 dtosna 1 f0 kRz f0 f2 dRo 2 f2 ata f5+12@ f2 fi f2@ f5+4@ clo malkRz mol xx …
をし、最後に
… nll molniv kRz 0 f0 kRz f5@ xx nll mol kRz 1 f0 kRz f5@ xx
を置く、というのが大まかな流れです。残りを埋めていきましょう。
f5+4@とf2@が等しかった場合の処理はもう書きました。それ以外の場合を考えましょう。
f2@が目的の値であるf5+4@より小さい場合、f0に入っているf1とf3の平均よりも1大きい値が、範囲の新たな下限になります。つまり、f3は変わらずf1だけが変わります。ゆえに、
… nll xyloler kRz f0 f1 ata 1 f1 …
であり、またこの操作によってf3がf1を下回ってしまった場合、範囲が消えてしまったからには値が見つかるはずが無いので、molnivに飛びましょう。
… nll xyloler kRz f0 f1 ata 1 f1 fi f3 f1 xylo malkRz molniv xx …
そうでなければ、平均値を求める処理に戻ればいいので、
… nll polto kRz f3 f0 ata f1 f0 dtosna 1 f0 kRz f0 f2 dRo 2 f2 ata f5+12@ f2 fi f2@ f5+4@ clo malkRz mol xx …
と名前を付けておいて
… nll xyloler kRz f0 f1 ata 1 f1 fi f3 f1 xylo malkRz molniv xx kRz polto xx …
最後に、f2@が目的の値であるf5+4@より大きい場合。このときは、
f0に入っているf1とf3の平均よりも1小さい値が、範囲の新たな上限になります。つまり、f1は変わらずf3だけが変わります。ゆえに、同様に
… nll leloler kRz f0 f3 nta 1 f3 fi f3 f1 xylo malkRz molniv xx kRz polto xx
としてやればよいわけです。
最後に、今までに書いた断片をまとめましょう。
その1: 冒頭melfert
nll melfert kRz f5+8@ f3 nta 1 f3 fi f3 0 xylo malkRz molniv xx kRz 0 f1 …
この断片には最後にkRz polto xxを付ければ完璧です。
その2: 平均を求めて探索を行うpolto
… nll polto kRz f3 f0 ata f1 f0 dtosna 1 f0 kRz f0 f2 dRo 2 f2 ata f5+12@ f2 fi f2@ f5+4@ clo malkRz mol xx …
後ろにfi f2@ f5+4@ xylo malkRz xyloler xxとkRz leloler xxを足せばこの断片も完成です。
その3: 目的の値より小さかった場合のxyloler
… nll xyloler kRz f0 f1 ata 1 f1 fi f3 f1 xylo malkRz molniv xx kRz polto xx …
これはこのままで完成です。
その4: 目的の値より大きかった場合のleloler
… nll leloler kRz f0 f3 nta 1 f3 fi f3 f1 xylo malkRz molniv xx kRz polto xx
これもこのままで完成です。
その5: 終わりの処理をするmolnivとmol
… nll molniv kRz 0 f0 kRz f5@ xx nll mol kRz 1 f0 kRz f5@ xx
これもこのままで完成です。
この5つをまとめると、
nll melfert kRz f5+8@ f3 nta 1 f3 fi f3 0 xylo malkRz molniv xx kRz 0 f1 kRz polto xx nll polto kRz f3 f0 ata f1 f0 dtosna 1 f0 kRz f0 f2 dRo 2 f2 ata f5+12@ f2 fi f2@ f5+4@ clo malkRz mol xx fi f2@ f5+4@ xylo malkRz xyloler xx kRz leloler xx nll xyloler kRz f0 f1 ata 1 f1 fi f3 f1 xylo malkRz molniv xx kRz polto xx nll leloler kRz f0 f3 nta 1 f3 fi f3 f1 xylo malkRz molniv xx kRz polto xx nll molniv kRz 0 f0 kRz f5@ xx nll mol kRz 1 f0 kRz f5@ xx
となり、これで一応完成です。