1000瓶水里面有一瓶毒水,通过用兔子去喝水的方式检验,只能让兔子喝一次水,那么最少用多少只兔子检验出来是哪一瓶?
首先我们知道最多的情况,就是1000只,让他们同时喝,答案一定能够出来!
最少的,先说答案,10只
我们以10瓶水举例讲解
十瓶水,我们用2进制表示
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
现在我们把10瓶水,然后取其中的某些瓶分成组
像这样
第4位为1 | 第3位为1 | 第2位为1 | 第1位为1 |
---|---|---|---|
0001 | 0010 | 0100 | 1000 |
0011 | 0011 | 0110 | 1001 |
0101 | 0110 | 0111 | 1010 |
0111 | 0111 | ||
1001 | 1010 |
把每一纵列的水取出来一滴然后混合,现在我们有四瓶混合水
现在我们需要四只小兔兔,准备为了伟大的算法题而献身
她们喝水的时候我不敢看~ _ ~
把第一位为1的给一号兔兔
把第二位为1的给二号兔兔
把第三位为1的给三号兔兔
把第四位为1的给四号兔兔
喝完
现在假设四号兔子,死了,另外3只没死
这意味着什么?
意味着第四位为1的瓶子中有一瓶有毒!
嫌疑人有
0001
0011
0101
0111
1001
然而我们知道,另外3只没死,意味着第一位为1,第二位为1,第三位为1的都没有毒
所以排除掉后面4个
真相只有一个!
0001是有毒!
如果我们对结果,用1代表死,0代表没死
那就是0001
对,兔子的存活编号就直接告诉看我们凶手是谁!
原因理解,其实很简单,这相当于是一个在与不在的二元判断
对于第一位为1的水,如果兔子死了,证明毒水里面第一位是1
依次类推,i号兔子的存亡状态决定了毒水编号二进制的i号是否为1
所以1000瓶水,是2^10次方,我们需要10位去表示,十只兔子去检验