→をクリックすると非真理設定が非表示になります。ページを再読み込みすると戻ります。
二等分で検索することの応用範囲は、名簿から名前を探すといったことに限られません。数学的な問題を解く際にも用いることができるのです。
例えば、次のような問題を考えましょう。「同じ大きさの正方形のタイルが17枚あるとする。これで作れる最大の正方形の辺は何枚のタイルからなる？」すぐに分かるように、答えは4です。なぜなら、一辺4の正方形は16枚のタイルで作れますが、一辺5の正方形を作るには25枚のタイルが必要だからです。
ということで、この問題を解く[指令](cersva)を書いていきましょう。情報は次のように与えられるものとします。
| 自由 | 自由 | 自由 | 戻る場所 | タイルの枚数 |
指令が終わったときにf0に入っている数値が答えであるとします。
タイルの枚数は負にはなりませんから、タイルの枚数を表すスイッチ列は[負でない](ny snakxaz)方の解釈をすることとしましょう。そうなると、可能な値は0以上[2の32乗](2-inie-32)未満なので、辺の長さは0以上[2の16乗](2-inie-16)未満となります。
ということで、この上で探索をしていきましょう。まず、0と[2の16乗](2-inie-16)の中央に位置する[2の15乗](2-inie-15)（[2の8乗](2-inie-8)ではないことに注意！）を試してみて、それが予測値として大きすぎるのか小さすぎるのか調べていくのです。とりあえず、f1に数値15を入れ、それを2倍し、f3に数値1を入れ、それを30桁左にずらすことで2の30乗が手に入ります。あ、f1は元に戻しておきましょう。
kRz 15 f1 kRz 1 f3 dRo 1 f1 dRo f1 f3 dto 1 f1 …
そのあとは、与えられた枚数と2の30乗を比較します。今回は[負でない](ny snakxaz)方の解釈ですから、「未満」はxyloではなくxylonysです。
もしタイルの枚数が足りなかったら、f1を減らして再挑戦です。再挑戦で飛ぶ場所はkRz 15 f1より後であるべきでしょう。その場所にはあとでpoltoという名前をつけてやるとして、
… fi f5+4@ f3 xylonys malkRz nartain xx … nll nartain nta 1 f1 kRz polto xx
となります。
まとめると、現状は
kRz 15 f1 nll polto kRz 1 f3 dRo 1 f1 dRo f1 f3 dto 1 f1 fi f5+4@ f3 xylonys malkRz nartain xx … nll nartain nta 1 f1 kRz polto xx
までできていて、あとはタイルの枚数が足りていたときの処理を書けばいいだけです。
おっとその前に、辺の長さが「2の0乗」枚、つまり1枚、と仮定してもなおタイルの枚数が足りない場合を処理しておきましょう。これは、f1が負であるときにf0が0になって処理が終了すればいいのですから、
kRz 0 f0 kRz 15 f1 nll polto fi f1 0 xylo malkRz f5@ xx kRz 1 f3 dRo 1 f1 dRo f1 f3 dto 1 f1 fi f5+4@ f3 xylonys malkRz nartain xx … nll nartain nta 1 f1 kRz polto xx
とでもしてやればよいでしょう。
さて、では残りの箇所です。足りた場合はどうすればいいでしょうか。
とりあえず、解が2のf1乗以上であることが判明するので、f0に2のf1乗を足し合わせましょう。また、少なくともf3枚のタイルはf5+4@から確保できることが分かったので、その分をf5+4@から引いてしまいましょう。
kRz 0 f0 kRz 15 f1 nll polto fi f1 0 xylo malkRz f5@ xx kRz 1 f3 dRo 1 f1 dRo f1 f3 dto 1 f1 fi f5+4@ f3 xylonys malkRz nartain xx kRz 1 f2 dRo f1 f2 ata f2 f0 nta f3 f5+4@ nll nartain nta 1 f1 kRz polto xx
ここで、f5+4@を勝手に書き換えてしまっていることに違和感を覚える人も多いかもしれません。実際、「タイルの枚数」は上記の図では緑の「使用中」に属する情報ですから、書き換えることは本来あまり行儀よくありません。とはいえ、実際問題としてはこの「タイルの枚数」という情報は受け取る側の[指令](cersva)が専有している情報ですし、あとで自分が困らないのであれば別に書き換えてしまってもそこまで問題は無いのです。
ただし！「戻る場所」を書き換えてしまうと、指令を終わらせて主処理に戻ることができなくなってしまうので、大いに気をつけましょう！
さて、f5+4@を書き換えたあとは、このままだとそのままf1から1を引く処理に入ります。別に問題ないでしょう。問題はその後です。
予測値を立てて、「少なくともその大きさの正方形は取れる」という処理を行った以上、予測値を増やして次に正方形を取り除く際には、下の図のピンクだけでなく緑も取り除いてやる必要があります。
■■■■■■■■■■□
■■■■■■■■■■□
■■■■■■■■■■□
■■■■■■■■■■□
■■■■■■■■■■□
■■■■■■■■■■□
■■■■■■■■■■□
■■■■■■■■■■□
■■■■■■■■■■□
■■■■■■■■■■□
□□□□□□□□□□□
緑の部分の面積は旧予測値と予測値増分の積の2倍なので、当該箇所では「予測値の増分は2のf1乗」「旧予測値はf0」であることを考えると、
kRz 0 f0 kRz 15 f1 nll polto fi f1 0 xylo malkRz f5@ xx kRz f0 f2 ata 1 f1 dRo f1 f2 nta 1 f1 … kRz 1 f3 dRo 1 f1 dRo f1 f3 dto 1 f1 fi f5+4@ f3 xylonys malkRz nartain xx kRz 1 f2 dRo f1 f2 ata f2 f0 nta f3 f5+4@ nll nartain nta 1 f1 kRz polto xx
とすることで…の箇所ではf2に緑の部分の面積が入ります。
あとは、正方形の面積を引くところで緑も引けばよいわけです。
kRz 0 f0 kRz 15 f1 nll polto fi f1 0 xylo malkRz f5@ xx kRz f0 f2 ata 1 f1 dRo f1 f2 nta 1 f1 kRz 1 f3 dRo 1 f1 dRo f1 f3 dto 1 f1 ata f2 f3 fi f5+4@ f3 xylonys malkRz nartain xx kRz 1 f2 dRo f1 f2 ata f2 f0 nta f3 f5+4@ nll nartain nta 1 f1 kRz polto xx
これで完成です。なお、実はあと少し削ることができて、
kRz 0 f0 kRz 15 f1 nll polto fi f1 0 xylo malkRz f5@ xx kRz f0 f2 dRo 1 f2 dRo f1 f2 kRz 1 f3 dRo f1 f3 dRo f1 f3 ata f2 f3 fi f5+4@ f3 xylonys malkRz nartain xx kRz 1 f2 dRo f1 f2 ata f2 f0 nta f3 f5+4@ nll nartain nta 1 f1 kRz polto xx
とできます。