2019-02-13 思考:1000瓶药水,1瓶有毒,老鼠毒发24h,如何用最少的老鼠在24h内找出毒药?

题目:

现在有1000瓶药水,其中一瓶有毒,一只老鼠喝了在24h后会准时死亡,药水无色无味,如何用最少的老鼠在24h内找出毒药?

分析: 时间限制为24h,说明我们只有一次喂老鼠的机会,需要一波找出来死亡的老鼠,先从小举例:1瓶药水–1只老鼠;2瓶药水–1只老鼠;3瓶药水–2只老鼠;4瓶药水–2只老鼠(方案:1只老鼠喝1,1只老鼠喝2,老鼠会出现死与不死两种情况,2只老鼠一起喝3则简单推断),从中可以看出,老鼠的死与不死能组成几种组合,则最多可辨别几瓶药水。故只需 2n>1000 2^n > 1000 即可,得到n为10。



加强题目:若将题中一天改为2天,3天……?

思路同理:如改为2天,则每只老鼠可能有3种情况:
1.第一天死
2.第二天死
3.两天都不死

那么只需 3n>10003^n>1000
得到n=7.


那么具体的解决方案则只需想到如何安排老鼠喝药才能最简单的判断药水的毒性?可以想到,用进制转换即可:

1000瓶药水编号 1~1000,转换为2进制:
0000000001
0000000010
0000000011
0000000100
0000000101
……
则可以看出每一个十进制数字对应一个具有鲜明特征的二进制
我们只需要将10只老鼠分别安排在0号到9号位
是1喝,是0不喝就可以了

比如: 0000000001 ——0号喝
            0000000101 ——0号喝2号喝

到最后将死亡老鼠重新组合为2进制数后转化为10进制则为有毒的那瓶了。


妙啊

原文地址:https://www.cnblogs.com/roccoshi/p/13027090.html