天天看點

2021-08-27 思考:1000瓶藥水,1瓶有毒,老鼠毒發24h,如何用最少的老鼠在24h内找出毒藥?

題目:

現在有1000瓶藥水,其中一瓶有毒,一隻老鼠喝了在24h後會準時死亡,藥水無色無味,如何用最少的老鼠在24h内找出毒藥?

分析: 時間限制為24h,說明我們隻有一次喂老鼠的機會,需要一波找出來死亡的老鼠,先從小舉例:1瓶藥水–1隻老鼠;2瓶藥水–1隻老鼠;3瓶藥水–2隻老鼠;4瓶藥水–2隻老鼠(方案:1隻老鼠喝1,1隻老鼠喝2,老鼠會出現死與不死兩種情況,2隻老鼠一起喝3則簡單推斷),從中可以看出,<code>老鼠的死與不死能組成幾種組合,則最多可辨識幾瓶藥水。</code>故隻需

2021-08-27 思考:1000瓶藥水,1瓶有毒,老鼠毒發24h,如何用最少的老鼠在24h内找出毒藥?

即可,得到n為10。

加強題目:若将題中一天改為2天,3天……?

思路同理:如改為2天,則每隻老鼠可能有3種情況:

1.第一天死

2.第二天死

3.兩天都不死

那麼隻需

2021-08-27 思考:1000瓶藥水,1瓶有毒,老鼠毒發24h,如何用最少的老鼠在24h内找出毒藥?

得到n=7.

那麼具體的解決方案則隻需想到如何安排老鼠喝藥才能最簡單的判斷藥水的毒性?可以想到,用進制轉換即可:

1000瓶藥水編号 1~1000,轉換為2進制:

則可以看出每一個十進制數字對應一個具有鮮明特征的二進制

我們隻需要将10隻老鼠分别安排在0号到9号位

是1喝,是0不喝就可以了

比如: 0000000001 ——0号喝

0000000101 ——0号喝2号喝

最後将死亡老鼠重新組合為2進制數後轉化為10進制則為有毒的那瓶了。

繼續閱讀