###やりたいこと
正解ビットが存在します。
与えられたnビットの入力に対して、正解のビットとの距離が返されるので、ビット数+1以内のクエリで正解ビットを当てるプログラムを書きたいのですがどのようにすれば良いでしょうか?
例えば正解ビットが000101
だとします。
最初のクエリが000000
と当ててみます。
正解ビットとクエリビットでは4ビットあっているので4が返却されます。
次に000100
と当ててみます。
正解ビットとクエリビットでは最後の1以外あっているので5が返却されます。
といった具合です。
最後のクエリでビット数 or 0が返却されたら正解ビットが分かるので終了します。
###試したこと
まず000000
で何ビットが0なのか調べる、、、という所までしかできていません。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答5件
0
ベストアンサー
正解
000101
クエリ
000000
-> 4
000001
-> 5
000010
-> 3
000100
-> 5
001000
-> 3
010000
-> 3
100000
-> 3
てな感じにやりまして、全部0のときより増えてればそこは1
、減ってりゃ0
でありんす。
■追記: 改善方法、長考した結果
あんま綺麗なコードじゃなくて恐縮なんですが、二分探査的に置き換えていって、連続した0
または1
を検出したらそこで足切りする方法試してみました。
長さ 1000 で 10 回計測したところ、クエリ回数が平均 717.5 となりました。
# coding: utf-8 import random def make_string(int_array): return "".join(map(str, int_array)) LENGTH = 1000 REAL_ANSWER = make_string([random.randint(0, 1) for i in range(LENGTH)]) print "REAL_ANSWER:\t" + REAL_ANSWER count = 0 def check(query): global count count += 1 print "query (" + str(count) + "):\t" + query ret = 0 for i in range(0, len(query)): if query[i] == REAL_ANSWER[i]: ret += 1 return ret NUM_OF_ZERO = check(make_string([0] * LENGTH)) my_answer = [0] * LENGTH # 引数 todo: 訂正すべき数 def solve(begin, end, todo): middle = (begin + end) / 2 tmp_array = [0] * LENGTH for i in range(begin, middle): tmp_array[i] = 1 tmp_score = check(make_string(tmp_array)) left_todo = (tmp_score - NUM_OF_ZERO + middle - begin) / 2 right_todo = todo - left_todo if (left_todo == 0): pass elif (left_todo == middle - begin): for i in range(begin, middle): my_answer[i] = 1 else: solve(begin, middle, left_todo) if (right_todo == 0): pass elif (right_todo == end - middle): for i in range(middle, end): my_answer[i] = 1 else: solve(middle, end, right_todo) solve(0, LENGTH, LENGTH - NUM_OF_ZERO) print "my_answer:\t" + make_string(my_answer) print make_string(my_answer) == REAL_ANSWER
投稿2018/10/25 16:20
編集2018/10/26 00:33総合スコア2413
0
範囲を広げ、その範囲を再帰的に二分割しながら探索すれば早く終わることもあります。
正解が 000011 の場合
000000 と比較して 4 ポイント
次に前半を反転した 111000 と比較して 1 ポイント
3 ビット反転して 3 ポイント減ったので前半の 000 が確定します。
後半を更に二分割し、前半 1 ビットと後半 2 ビットに分けます。
1 回目の前半が 000 で確定したので、これと 2 回目の前半を反転した 1 と 2 回目の後半 00 を合わせて 000100 と比較します。
結果は 3 ポイントとなり、100 が全て間違っていることが確定します。
それで 000011 という正解が 3 回の比較で得られました。
投稿2018/10/25 23:35
編集2018/10/25 23:38総合スコア28656
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/10/25 23:59
2018/10/26 00:17
2018/10/26 00:34
2018/10/26 00:40
2018/10/26 01:08
0
適当に思いついたやつを。ミスがあるかもしれません。
1 適当なn bitのクエリを作り、投げて「前の値」として記録する
2 先頭2 bitを反転させてクエリを投げ、
2.a 値が2増えたら「前の値」を2加算して次の2 bitを見る(2つとも間違っていたパターン)
2.b 値が2減ったら元に戻して次の2 bitを見る(2つとも正解だったパターン)
2.c 値の変化が0だったら2 bitのうちどちらかを反転させてもう一度クエリを投げ、(どちらか正解でどちらか間違いのパターン)
2.c.a 値が1増えたら「前の値」を1加算して次の2 bitを見る
2.c.b 値が1減ったら両方反転してから「前の値」を1加算して次の2 bitを見る
(途中で値がnに達したら打ち切る)
(nが奇数だった場合の端数の処理は考慮していない)
やればできるっぽいです。クエリを投げる回数はナイーブに1 bitずつ見る方法と比較して3/4くらいになるかな。
場合の数的に考えると、1度のクエリで2増えるor2減る、0なのでどちらか反転させてもう一度投げてみる*2のどちらかなので、それぞれ
1query/2bit
2query/2bit
で、確率は同じなので平均して3/4 query/bitですね。
2 bitずつ見て改善するということは3 bitずつ見るともっと良くなるのか? は検討していません。宿題とします(私の)。
投稿2018/10/25 22:41
編集2018/10/25 23:00総合スコア30933
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/10/25 23:02 編集
2018/10/26 00:31
2018/10/26 02:58 編集
2018/10/26 02:49
2018/10/27 10:14
2018/10/27 11:19 編集
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 終了
投稿2018/10/25 22:27
総合スコア1009
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/10/25 16:24
2018/10/25 16:26
2018/10/25 22:30
2018/10/25 22:33
2018/10/26 00:30
2018/10/26 01:59 編集
2018/10/26 02:28