質問: ### やりたいこと 正解ビットが存在します。 与えられたnビットの入力に対して、正解のビットとの距離が返されるので、ビット数+1以内のクエリで正解ビットを当てるプログラムを書きたいのですがどのようにすれば良いでしょうか? 例えば正解ビットが`000101`だとします。 最初のクエリが`000000`と当ててみます。 正解ビットとクエリビットでは4ビットあっているので4が返却されます。 次に`000100`と当ててみます。 正解ビットとクエリビットでは最後の1以外あっているので5が返却されます。 といった具合です。 最後のクエリでビット数 or 0が返却されたら正解ビットが分かるので終了します。 ### 試したこと まず`000000`で何ビットが0なのか調べる、、、という所までしかできていません。
回答: > > もしビットの数が大きくなった場合クエリの数を極力減らす為にはどうすれば良いでしょうか? > > > 最下位から最上位まで調べる方法では `110000`や`100001`だとどんなに桁数が多くても結局最初から最後まで探索する必要があるかと。 `001100`や`000011`などの途中で打ち切り出来る時に少しだけ早く終る程度です。 最長で`n-1`回の探索であればこれ以上速くなることは無いのではないでしょうか。 余談ですが・・・ 極端な例ですと1万桁で正解の`1`が1個の時に最下位`1`と最上位`1`であれば約1万回差が出ます。 もし要件として桁数が数万桁でとても大きくて1が極端に少ないなら2分探索などが可能かなと。 要件が不明なのであしからず。 総桁数を`n`とした場合 `000000`で出た答え`a` `n-a`は`1`の数となる 最下位ビットから最上位ビットまで最長ループでn-1回探索する 途中で正解が分かったら以降そこには`1`を立てる 探索範囲の残りと答えの残りが同じなら残りは全て答えとなるので探索を打ち切れる 以下総桁数n=6桁,1の数a=2個のパターン 探索範囲の最初に正解がある場合最短 `000011` -> 6 正解 `000000` -> 4 残り2 `000001` -> 5 残り1 `000011` -> 6 終了 探索範囲の最後に正解がある場合最長 `110000` -> 6 正解 `000000` -> 4 残り2 `000001` -> 3 `000010` -> 3 `000100` -> 3 `001000` -> 3 残り2 == 探索範囲の残り2なので残り全てが答え 探索範囲の途中に正解がある場合 `001100` -> 6 正解 `000000` -> 4 残り2 `000001` -> 3 `000010` -> 3 `000100` -> 5 残り1 `001100` -> 6 終了 探索範囲の途中と最後に正解がある場合最長`n+1回` `100100` -> 6 正解 `000000` -> 4 残り2 `000001` -> 3 `000010` -> 3 `000100` -> 5 残り1 `001100` -> 4 残り1 `010100` -> 4 残り1==探索範囲の残り1なので最後のビットが正解となる `100100` -> 6 終了