【问答官每日挑战】如何用最少的老鼠试出有毒的牛奶？
如何用最少的老鼠试出有毒的牛奶？
有 n 桶牛奶，其中有 1 桶有问题，老鼠喝了后第二天会死掉。如何在最短时间内用最少的老鼠测出有问题的那瓶牛奶？
截止时间：3月20日晚18：00
要求：拥有详尽的解题思路，不得雷同。快来挑战吧~
最佳解析奖将会获得神秘小礼物一份哦~
写回答
-
-
-
答案
如果 n 是 2 的整数次幂，就是 n 转换为二进制后的位数减一。如果 n 不是 2 的整数次幂，就是 n 转换为二进制后的位数。即下面的计算
log2(n)，如果是整数，那这个整数就是最少的老鼠。如果有小数，整取后并加1后的值为最少的老鼠数操作方案
为了方便演示假设 n = 8，转换成二进制位 1000，可知需要最少的老鼠是 4 只，但因为 8 是 2 的整数次幂，其实最后只需要 3 只老鼠，我们先用 4 只老鼠说
第一步
给 8 桶牛奶用二进制编号
第 1 桶牛奶 0001
第 2 桶牛奶 0010
第 3 桶牛奶 0011
第 4 桶牛奶 0100
第 5 桶牛奶 0101
第 6 桶牛奶 0110
第 7 桶牛奶 0111
第 8 桶牛奶 1000
第二步
4 只老鼠按顺序排好，面对着牛奶对应的二进制编号，每桶二进制编号为 1 对应的老鼠喝牛奶
老鼠 1 喝第 8 桶的牛奶
老鼠 2 喝第 4、5、6、7 桶的牛奶
老鼠 3 喝第 2、3、6、7 桶的牛奶
老鼠 4 喝第 1、3、5、7 桶的牛奶
第三步
第二天后把这 4 只老鼠还按昨天的顺序排好，死了的老鼠标记为 1，没有死的老鼠标记为 0，这这样 4 只老鼠就组成了一个二进制的数，与之对应的牛奶编号就是有毒的那桶。比如老鼠 2 和老鼠 3 死了，对应的二进制编号为 0110，那就说明第 6 桶牛奶有毒
我们知道 n 为 2 的整数次幂的话，对应的二进制只有在最高位为1，也就是对应的第 n 桶牛奶只有一只老鼠喝，我们可以把这个老鼠省下来，用剩下的老鼠喝其余桶中的牛奶。如果这些老鼠都没死，那就说明是第 n 桶牛奶有毒了。
2020-03-20 15:32:25赞同 展开评论 打赏 -
老鼠设为Y ，有n桶牛奶，2的Y次方>=n 即可，例如有10桶牛奶，2的Y次方>=10,所以只需要4只老鼠即可在一天后找到有问题的牛奶
2020-03-20 15:06:40赞同 1 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
