【大厂智力题】瓶水有毒问题

智力题】瓶水有毒问题"/>

【大厂智力题】瓶水有毒问题

瓶水有毒问题的变型有很多：

1. 1000瓶水有1瓶水有毒，老鼠喝一滴就会死，但是需要一月毒发，请问最少需要多少老鼠才能找到那瓶有毒的水。
2. 1000瓶药水，1瓶有毒，老鼠毒发24h，如何用最少的老鼠在24h内找出毒药。
3. …

反正老鼠就不是立马死（老鼠：我太难了）。所以在实际可行的情况下，无法利用1只老鼠测出哪瓶水有毒。

这个时候就需要动点脑筋了。如果你了解布隆过滤器，那么这个问题对你来说，是比较轻松的事情（思路可借鉴呀）。

这道智力题，重在考察你对二进制生活中的场景的应用。

我们知道 2的10次方等于1024，1024以内的所有自然数都可以用10个数位的二进制数表示出来。1000 <= 1024。那就好办了，

我们将1000瓶水从water[0]到water[999]分别进行编号，并转化成10个数位的二进制数。

9 8 7 6 5 4 3 2 1 0 位数

0 0 0 0 0 0 0 0 0 0 对应编号0
0 0 0 0 0 0 0 0 0 1 对应编号1
1 1 1 1 1 0 0 1 1 1 对应编号999

我们将10只老鼠从mouse[0]到mouse[9]进行编号

1. 让第mouse[0]只老鼠喝第0位为1的水
2. 让第mouse[1]只老鼠喝第1位为1的所有的水
3. 让第mouse[2]只老鼠喝第2位为1的所有的水
4. 依次类推

最后可以根据老鼠的死亡情况，推算出编号n。从mouse[0]到mouse[9] 活着的老鼠对应位为0，死了的老鼠对应位为1。