分享一个逻辑题:1000瓶药水找毒药
题目描述如下:
一共 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