失われたボトルを見つける（アルゴリズムの問題）

Question

質問は次のとおりです。

科学者は化合物Aと呼ばれる新しい化合物を作成し、それは化合物Bと混合されてから10日後に爆発します。 > $ n-1 $ $ 非反応性材料のボトル、そして科学者はどちらが複合Aであるかわからない。 $ n $ 棚の上のボトル。科学者は、 $ O（log（n））$ ビーカーを持っています。 N $ ボトルは、正確に10日間の時間の化合物Aですか？

私は10日しかわずか10日で特定のボトルを絞り込む方法がわからないので少し動いています。ボトルの前半を最初のビーカーに適用することができるだけでは、それが反応しない場合はかなり明らかです。目的のボトルが後半などにあることを知っています。しかし、最初のいくつかのテストの結果を目撃していないことなく、どのように絞り込むのですか？

一連の爆発が私たちが絞り込むのを助けることができるようなものを作成する必要があります（最初はN / 4の中で、次にN / 10、次にN / 100など）。 どうやってこれをやるのですか？

Answer 1

これは、私が以前にCS質問ではなくパズルとして囲まれている古典的な問題です（一部の固定 $ n $ 、および固定数のビーカー数）私はそれのためのソースを覚えていませんが。

次のように解決できます。 $ 0 $ から $ n-1 $ から $ 1 $ $ \ lfloor \ log_2（n-1）\ rforoor + 1 $ （表現に必要なビット数）番号 $ n-1 $

今瓶ごとに、次の手順を実行します。 $ x $ をボトルのラベルにします。 $ i $ の場合"" $ i $ ' $ x $ のバイナリ表現内の位置は、ビーカーの $ i $ 。

今10日後、爆発するビーカーはバイナリの爆発瓶の数を正確に綴ります。