面试智力题

二进位bit

1. 题目：一千杯水，一杯水有毒，怎么用10只老鼠，把这杯水找出来

（1）解法1：常规法

1、方法1，二分搜索

500 250 125 63 32 16 8 4 2 1

假设毒性在一个小时才会发作，这样可以用10只老鼠来判断，但是在灌入250瓶的时候，必须等灌入500瓶的结果，来确定是哪250瓶，因此一共需要10只老鼠，需要10个小时。
1
2
3
4
5

（2）bit法（位数法）

将瓶子编号，老鼠也编号
那么n只老鼠，最大可以判断2^n瓶药水有没有毒
比方 第7瓶药水编号是 0000000111，那么编号为0，1，2的老鼠喝这瓶
这样每个老鼠喝多瓶药水，只需要1个小时就可以判断哪瓶药水有毒
分析：比方说 0110010100号药水有毒，那么只有2 4 7 8号老鼠会死亡，根据老鼠死亡的0，1确定最终毒药的编号

参考：https://blog.csdn.net/chenlong_cxy/article/details/113057754?utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromMachineLearnPai2~default-1.control&dist_request_id=&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromMachineLearnPai2~default-1.control
1
2
3
4
5
6
7

(3) 时间法

方法3，时间法
这个看评论区一个老哥的思路，只需要一个老鼠
毒性在一个小时内发作，那么将一个小时划分为1000段，3600秒/1000 = 3.6秒
那么每隔3.6秒就给老鼠喂一瓶水，只要看老鼠在哪个时间段暴毙的就可以知道对应的药瓶

这种方法需要1只老鼠，2个小时。
参考：https://blog.csdn.net/mystyle_/article/details/115430197
1
2
3
4
5
6
7

三级目录