[過去ﾛｸﾞ] スレ立てるまでもない質問はここで 165匹目 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
207: デフォルトの名無しさん (ﾜｯﾁｮｲ 4220-gXHy) [sage] 2023/11/04(土) 10:25:35.74 ID:+c1eUFX20(1/4) AAS
アルゴリズムについて、以下のことが可能かどうか分かる人がいたら教えてほしい
・N個の箱があって、1から順番にNまでの通し番号がついている（Nは数百から数千くらい）
・1つの箱の中には白玉か赤玉のどっちかの玉が1個だけ入っているが、箱を開けないと分からない
・白玉の入っている箱はすぐ開けられるが、赤玉の入っている箱は空けるのに数秒から最悪1分くらいかかる
・箱の中の玉を1番から順に取り出し、取り出した順番に並べると
・パターン1：白白・・・白 で赤玉が全く入っていない
・パターン2：赤赤・・・赤 で白玉が全く入っていない
・パターン3：白白・・・白赤赤・・・赤 のように白玉がいくつか連続して続いた後、赤玉が最後まで連続して続く
・パターン4：白白・・・白赤赤・・・赤白白・・・白 のように白連続→赤連続の後、また白連続が最後まで続く
・パターン5：赤赤・・・赤白白・・・白 のように赤連続の後、白連続が最後まで続く
の5つのパターンのうちどれかの入り方になりそれ以外はない（どのパターンかは事前には分からない）
・白玉又は赤玉が何個連続して入っているかは分からない
・白玉と赤玉の連続している個数が等しいという保証はない
この条件下で、白連続から赤連続＆赤連続から白連続に切り替わる箱がそれぞれ何番の箱か調べたいけど、
1つの箱を開けるのに時間がかかる上に箱の数が非常に多いので、極力少ない回数の箱開けで特定したい
こういう状況だとやっぱり1番から順に箱を開けてしらみつぶしに調べつくすしか方法はない？
パターン3と5のどちらかしかないなら1番とN番の箱の両側から二分法で調べていけば数千個の箱があっても
十数回の箱開けくらいで突き止められると思うんだけど、他のパターンの可能性も想定しなきゃいけないので
そう簡単にいかなくて困ってる
諦めてしらみつぶしに全部調べる＆赤玉の箱を開ける時間をどうにかして短縮する方向でいくしかないかな・・・
211: デフォルトの名無しさん (ﾜｯﾁｮｲ 4220-gXHy) [sage] 2023/11/04(土) 15:31:06.34 ID:+c1eUFX20(2/4) AAS
>>208-209
ありがとう
赤を開けるのにかかる時間は実時間の話
赤を開ける場合実時間で数十秒かかるだろうと考えていて、赤が連続する個数は数十〜数百程度と
見積もっているので、総当たりで全チェックだとリアルに数十分〜数時間待たされる可能性がある
なのでできれば回数を減らしたいってのがあった
白を開けるのにかかる時間は実時間でおそらく1ミリ秒もかからないはずなので無視できる
両端開けてチェックしてみるのはやってみようと思ってるけど、両端とも白だった場合にパターン1なのか
パターン4なのかを区別できないのが一番の悩みの種になってて、どっちのパターンなのかをできるだけ
少ない箱開け回数で見極められないかと頭を悩ませてる
（箱の個数や赤玉の数はシナリオによって大きく変わるけど、パターン1か4になる可能性が一番高い）
最初に両端を開けてみて色が違ったら二分法、同じだったらしらみつぶしでいくしかないのかなー
213: デフォルトの名無しさん (ﾜｯﾁｮｲ 4220-gXHy) [sage] 2023/11/04(土) 15:37:06.21 ID:+c1eUFX20(3/4) AAS
>>210書き込んでる間に次のレスが
そっかそんな簡単な手があったか
しらみつぶしの時は前からしか順に開けてはいけないと思い込んでたんで
後ろから赤に当たるまでしらみつぶしは全く思いつきもしなかったお恥ずかしい
まだアルゴリズム検討の段階で実際のコーディングはこれからなんで
結果が出るまで時間がかかりそうだけど道が拓けた気がする
どうもありがとう
214(1): デフォルトの名無しさん (ﾜｯﾁｮｲ 4220-gXHy) [sage] 2023/11/04(土) 15:44:10.42 ID:+c1eUFX20(4/4) AAS
>>212Excel VBAなのでそれができなくて・・・
ここでは箱開けと表現したけど、実際はもっと複雑な問題だったりする
諸事情でそれをそのまま晒せないので、箱を開けて玉の色を確認するという
別の問題に言い換えさせてもらった
とりあえず提示してくれた方法で何とかなりそうなのでそれでやってみる
VBAじゃなくてVB.NETならそれこそ並列で箱開けられるのにw
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.035s