6

私の友人はインタビューのためにこの質問をされました、そしてその瞬間それを解決することができませんでした。私は同じことを共有すると思いました。

チョコチップクッキーは千個あり、そのうちの1つが毒されています。1日あたり10匹の実験用ラットにアクセスできます。各ラットは任意の数のクッキーをかじることができ、各クッキーは任意の数のラットによってかじることができます。ネズミが毒入りのクッキーをかじった後、ネズミが毒殺された場合の影響を確認するのに1日かかります。

日数を最適化します。毒入りのクッキーを1日で見つける方法はあると思いますが、2日で見つけるアルゴリズムを思いつくことができました。

4

2 に答える 2

7

これは、3日間で「簡単な」ソリューションです。

  • まず、各ラットが100個のクッキーをかじることを許可します。
  • 1日後、各ラットが死んだラットが食べたクッキーを10個かじるのを待ちます。
  • 2日後、各ラットが2番目の死んだラットが食べたクッキーの1つをかじるのを待ちます。
  • 3日後、どのCookieが汚染されているかがわかります。

さて、1日で「難しい」解決策を見つけましょう。

  • すべてのCookieに2進数で番号を付けます。
  • 各ラットは、バイナリ表現がラットのインデックスに設定されたビットを持っているクッキーをかじることになっています。したがって、たとえば、ラット1はすべての奇数番号のCookieをかじります。
  • 言い換えれば、クッキー37はラット1、3、6によってかじられます。したがって、これらの正確に3匹のラットが翌日死亡した場合、クッキー37が毒されたものであることがわかります。
于 2012-07-14T23:39:01.727 に答える
3

わかったと思います。

ルートとして1024個のCookieを使用するバイナリツリーを想像してみてください（この数はよりクリーンになりますが、これは1024未満の任意の数で機能します）。その1024個のCookieを512個の2つのグループに分割します。これらの各グループは、ルートの子です。次に、512の各グループを256のグループに分割し、それらをそれぞれの子にします。ツリーの11レベルで終わるはずです。

ルートを除くツリーのレベルに各ラットを割り当てます。各ラットは、レベルの左側の枝にあるクッキーのみを食べます。翌日、木を繰り返し、死んだネズミごとに左の枝をたどり、生きたネズミごとに右の枝をたどります。結果として得られるCookieは、汚染されたCookieである必要があります。

于 2012-07-14T23:13:51.513 に答える