文章来自 @一个搬砖的胖子 我只是搬运工
顺便推荐胖哥开发的高频题库 https://codetop.cc 真的nice！！
一共 1000 瓶药水，其中 1 瓶有毒药。已知小白鼠喝毒药一天内死，若想在一天内找到毒药，最少需要几只小白鼠？
答案：10 只。
解析：二进制思想。
0 000 000 001表示 1 号老鼠，喝了药水 1 。
0 000 000 010表示 2 号老鼠，喝了药水 2 。
0 000 000 011表示 1 号、 2 号老鼠，喝了药水 3 。
… …1 111 101 000表示 4、6、7、8、9、10号老鼠，喝了药水 1000。
按照上述的方法依次喝
第一回合，1 号老鼠喝药水 1
第二回合，2 号老鼠喝药水 2
...
第一千回合，4、6、7、8、9、10号老鼠喝药水 1000
喝完一天时，看 10 只老鼠的状态，根据老鼠状态就知道哪瓶药水有毒了。
比如最后只是 2 号老鼠死了，那就说明第2瓶药水有毒；如果4、6、7、8、9、10死了，那就说明第1000瓶药水有毒！
想明白这个道理，再来看怎么答案为何是10
我们需要让二进制表示的种类数>=药水总数（1000）
求的是最小值，显然，为10的时候满足要求
也可以这么计算：⌈ log N ⌉，log底数为2
全部评论
(0) 回帖