8

これは、アルゴリズム クラスの追加クレジット用です。問題の状態

王は N 本のワインセラーを持っており、1 本のボトルが毒されています。
毒が効くまでに約1ヶ月かかります。王様は、1 か月以内にできるだけ少ないテスターを使用して正確なボトルを識別したいと考えています。

私の解決策は

  • Nボトルをロットに分割し、M「M テスター」を使用します

    • 最初のテスターは、最初と最後のロットの両方を試飲します

    • 2 番目のテスターは、最初のロットと 2 番目のロットの両方を試飲します。

    • 3 番目のテスターは、2 番目と 3 番目のロットの両方を試飲します。

    • テスターがロットをオーバーラップさせて、M ロットについて続行します。

  • 汚染されたワインを試飲した2人のテスターが病気になったとき、ロットが特定されました. テスターは、汚染されたロットから 1本M-2ずつ味見をし、病気になった 3 番目のテスターが汚染されたボトルを識別します。

ただし、このアルゴリズムは作業に割り当てられた時間の 2 倍を必要とします。つまり、汚染されたロットを特定するのに 1 か月、汚染されたボトルを特定するのに 2 か月かかります。より効率的なアルゴリズムはありますか?

4

4 に答える 4

7

log2(N)かなり巧妙なアルゴリズムを備えたテスターでそれを行うことができます。

簡単な例でそれを示しましょう。と仮定しN = 1000ます。

0でボトルにラベルを付けると、各ボトルは( 10 進数) から ( 10 進数)まで999の一意の 2 進数で表すことができます。00000000000111100111999

主張: 毒入りのボトルを見つけるのに必要なテスターは 10 人だけです。注: log2(N) = log2(1000) = 10.

アルゴリズム:M番目のボトルについて、最初に の 10 ビット バイナリ表現を取得しMます。i2 進数の th ビットが の場合、テスターに​​ボトルからワインを飲ませます1。i注: 0 < M <1000, 0 < i <10.

1st、4th、9thテスターが死亡し、1 か月後に他のテスターが生きている例を考えてみましょう。は 10 進数の 2 進数表現である289thため、ボトルは毒入りのボトルであると結論付けます。0100100001289

テスターだけで、ボトル10の中から毒物を特定できるのはなぜですか?1000

テスターが10最終的に死んでいるか生きているかで、合計の1024組み合わせができるため、それぞれの組み合わせを使用して、多くのボトルから 1 つのボトルを毒物として一意に識別することができます1024。

于 2013-01-19T05:11:16.380 に答える
5

これは古典的なパズルなので、すぐに答えを教えたくはありませんが、ここにヒントがあります: ワインのボトルを 2 つのグループに分け、それぞれにボトルの半分が含まれているとします。 . これにより、どのボトルが毒されているかをボトルの半分に絞り込むことができます。

問題はこれです - ワインボトルを半分に分割し、上記のアプローチを並行して実行するさまざまな方法を思い付く方法はありますか? ヒントとして、N の 2 進数表現について考えてみましょう。

お役に立てれば！

于 2013-01-18T19:57:37.243 に答える
0

例を挙げてください:

各ボトルに 1 から n までのラベルを付け、それぞれを 2 進数と見なします。例：11本

00000001 
00000010 
00000011 
00000100 
00000101 
00000110 
00000111
00001000 
00001001 
00001010 
00001011

次に、右から左へ、まず、一番右のビットが「1」に設定されている各ボトルから 1 滴を取り、最初のカップに入れます。次に、2 番目のビットが「1」に設定されている各ボトルから 1 滴を取り、2 番目のカップに入れます。
最上位ビットまで同様の方法で続行します。したがって、合計で 4 つのカップと 4 つのテイスターが必要です。

taster4 taster3 taster2 tester1
cup4     cup3    cup2     cup1

ここで、テイスターをカップにマップし、カップをビットにマップします。したがって、テイスターをビットにマップすると、テイスターに飲むように命令します。1 か月以内に、テイスターの何人かが死亡します。たとえば、taster3 とtaster1 が死んでから、対応するビットを 1 に設定し、他のすべてのビットを 0 に設定します。結果として得られる 2 進数 00000101は、毒入りのボトルを識別します。テイスターの数 f(n) = (int)(logn)+1 なので、f(n) は O(logn)

于 2016-01-31T05:46:59.553 に答える
0

これが私が提案するものです。これは基本的に並列アルゴリズムに由来します。

  1. ボトルを n/log2(n) で割ります。各部門を解決するサブ問題と呼びます。
  2. ステップ 1 の各サブ問題に各 log2(n) テスターを割り当てます。
  3. 最後に、1 人のテスターが死亡したとします。log2(n) 個のボトルが残っていて、log2(n) - 1 人のテスターがいるとします。
  4. 各テスターは 1 本のボトルをテストします。そして残り1本。
  5. テスターが死亡しない場合 (または、少なくとも最初の数日間は症状を示さない場合... それが私の仮定です)、犯人は置き去りにされたボトルであることがわかります.
  6. いずれかのテスターが死亡した場合 (または少なくとも病気を示した場合)、そのテスターに​​よってテストされたボトルが原因であることがわかります。

これには log2(n) + 1 か月かかります。1 は定数なので無視して、O(log2(n)) と言えます。

于 2013-10-13T18:50:45.610 に答える