- 212 名前：デフォルトの名無しさん mailto:sage [2023/11/04(土) 10:25:35.74 ID:+c1eUFX20.net]
- アルゴリズムについて、以下のことが可能かどうか分かる人がいたら教えてほしい
・N個の箱があって、1から順番にNまでの通し番号がついている（Nは数百から数千くらい）
・1つの箱の中には白玉か赤玉のどっちかの玉が1個だけ入っているが、箱を開けないと分からない
・白玉の入っている箱はすぐ開けられるが、赤玉の入っている箱は空けるのに数秒から最悪1分くらいかかる
・箱の中の玉を1番から順に取り出し、取り出した順番に並べると
・パターン1：白白・・・白 で赤玉が全く入っていない
・パターン2：赤赤・・・赤 で白玉が全く入っていない
・パターン3：白白・・・白赤赤・・・赤 のように白玉がいくつか連続して続いた後、赤玉が最後まで連続して続く
・パターン4：白白・・・白赤赤・・・赤白白・・・白 のように白連続→赤連続の後、また白連続が最後まで続く
・パターン5：赤赤・・・赤白白・・・白 のように赤連続の後、白連続が最後まで続く
の5つのパターンのうちどれかの入り方になりそれ以外はない（どのパターンかは事前には分からない）
・白玉又は赤玉が何個連続して入っているかは分からない
・白玉と赤玉の連続している個数が等しいという保証はない
この条件下で、白連続から赤連続＆赤連続から白連続に切り替わる箱がそれぞれ何番の箱か調べたいけど、
1つの箱を開けるのに時間がかかる上に箱の数が非常に多いので、極力少ない回数の箱開けで特定したい
こういう状況だとやっぱり1番から順に箱を開けてしらみつぶしに調べつくすしか方法はない？
パターン3と5のどちらかしかないなら1番とN番の箱の両側から二分法で調べていけば数千個の箱があっても
十数回の箱開けくらいで突き止められると思うんだけど、他のパターンの可能性も想定しなきゃいけないので
そう簡単にいかなくて困ってる
諦めてしらみつぶしに全部調べる＆赤玉の箱を開ける時間をどうにかして短縮する方向でいくしかないかな・・・
|
 |
