首页 > 代码库 > 7只老鼠测试100个瓶子
7只老鼠测试100个瓶子
起源
今天，休息的时候同事虎哥给我们说了一个很有意思的问题：有100个瓶子，瓶子里面乘着水，其中有一个瓶子里面的水是有毒的。还有七只老鼠，老鼠喝了有毒的水，七天会死掉。现在给你七天的时间，然后让你用这七只老鼠将这些瓶子里面有毒的那个瓶子测试出来，怎么做？
据说这个问题是某个比较大的公司的一个面试题。对这个问题很感兴趣的，于是，下班回家后就开始研究这个问题，想到了现在（除去中间打了一把红警的时间）终于想出来了，跟大家分享下。
思路
思路一：
对于这个问题，我的第一个思路是这样的（这个思路我没有走通，有兴趣的同学可以研究下。不感兴趣的同学可以直接看第二个思路）：七只老鼠，七天死亡，七天出结果。肯定不能一个一个的进行慢慢尝试。否则这个问题就太简单了。那么，解决问题的关键就出在了不同老鼠的组合之上了。比如说：一个老鼠吃一个药，可以检测出来七个瓶子。在数轴上表示为一个x轴。还是比较简单的。
然后我打算试一下让一个老鼠吃两个药，希望可以得出一个二维数组，一个x轴一个y轴那样的坐标轴。然后可以得出49个结果的一个矩阵如图所示；（图解：比如说，12，就代表着1号老鼠和2号老鼠都吃这个瓶子中的溶液。如果有且仅有两个老鼠死亡，并且是1号老鼠和2号老鼠，则表示12对应的这个瓶子中的液体是有毒的。）
但是，很快我就发现一些问题：首先，一个老鼠吃的不是2个瓶子的溶液，而是很多个瓶子。其次，里面的11，22，33等对应的坐标如果有毒的话，只会死掉一个老鼠，那么，就没有办法跟一个老鼠只吃一种药的那7种情况做区别了。还有就是12号和21号，如果一个有毒的话，那么，没有办法确定是12号坐标对应的瓶子有毒还是21号坐标对应的瓶子有毒。两个只能留一个。最终可以用的坐标只有21个图中黄色区域：
加上之前的七个一维数组，总共是28个可能，即可以测试28个瓶子。这时，我就想起了三维数组，再加一个z轴嘛。肯定会有一些重复的不能使用，于是我又画了个三维数组。
于是，这次又发现了三个老鼠死亡的时候，可以出现的可能。总共有35种可能。加上之前的28种可能，总共可以测试63个瓶子。然后就需要四维数组了。最后一直到七维数组，也就是七个老鼠都死亡的情况，但是感觉实施起来太蛋疼了。就想找个简单点的解决方案。于是就有了以下：
思路二：
在思路2开始之前，自己感觉很麻烦，正好小马哥打电话过来，就问了下他有什么解决方法，他给了这个方案：将老鼠弄死，磨成肉泥，放到一百个瓶子里。最后哪个瓶子里面的肉没有长蛆哪个就有毒。让我佩服啊。
好，扯淡完毕。说下思路二，也就是我的现在的解决方案。当时的想法是这样的---为啥不考虑下老鼠的潜力呢？怎么个意思呢？老鼠有两种状态：1.喝了溶液。2.没有溶液。
那么一个老鼠可以测试一个瓶子的状态：喝完了死了表示有毒，没死表示没毒。那么两个老鼠呢？可以测试3个瓶子：1号老鼠喝一个，2号老鼠喝一个，俩老鼠一起喝一个。1号自己死了，表示第一个瓶子有毒；2号老鼠自己死了，表示2号瓶子有毒，哥俩一起死了表示3号瓶子有毒。
以此类推，最后得出一个结论：七只老鼠总共可以测试2的7次方减1个瓶子，也就是说127个瓶子。如果确定肯定有一个瓶子是有毒的，那么可以检测128个瓶子，因为可以留一个瓶子不给老鼠喝，没有老鼠死就表示最后一个是有毒的。
这让我联想到了二进制中的进位的算法。于是就用Java代码模拟了下测试的过程。首先，定义七个integer值表示七只老鼠。对于每个瓶子中的液体，老鼠有两种可能：1.喝了，2.没有喝。
然后，我定义了一个长度为100的数组，表示100个瓶子的集合。在数组中存放了100个瓶子对象，这些对象都有一个属性，那就是是否有毒。true的时候是有毒的。这里随机赋予一个瓶子为有毒的瓶子
然后，我们根据二进制进位的方法开始给这些老鼠喂药：先给1号老鼠喂药，并将老鼠标号变为1.下一个循环的时候，发现1号老鼠标号是1于是给2号老鼠喂药，并将1号的标号设置成0。类似于二进制的0-1进位的感觉。
最后，一星期后，根据死亡的老鼠的标号看都是哪些老鼠死了比如说：4号老鼠和5号老鼠还有7号老鼠死了，那么我们可以得出一个这样的数据：这个瓶子的标号的二进制表示为1011000 为啥呢，因为这三个老鼠死掉了，表示这三个老鼠喝了有毒的那个瓶子中的液体了。喝了液体，我们的标记是1，其他的没有死掉我们标记是0。例如：第一个瓶子只有1号老鼠喝了那么标记号就是0000001，二号瓶子只有2号老鼠喝了那么标记号便是0000010.而它们的10进制表示正好是1和2.
核心的原理就是，用老鼠作为标记位数，去表示瓶子的号码。然后通过死亡的老鼠，得出瓶子的二进制表示法，然后推导出哪个瓶子是有毒的。
代码如下：
代码
1 package test; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Random; 6 7 public class test { 8 9 public static void main(String[] args) { 10 // 七只老鼠 0代表活，1代表死 11 Integer y = 0; 12 Integer e = 0; 13 Integer s = 0; 14 Integer si = 0; 15 Integer w = 0; 16 Integer l = 0; 17 Integer q = 0; 18 // 随机出来一个有毒的瓶子 19 Random random = new Random(); 20 21 Integer youdupingzi = random.nextInt(100) % 100; 22 // 100个瓶子 23 List<Pingzi> listpingziList = new ArrayList<Pingzi>(); 24 for (int i = 0; i < 100; i++) { 25 Pingzi pingzi = new Pingzi(); // 生成瓶子 26 if (i == youdupingzi) { // 产生有毒的瓶子 27 pingzi.isYoudu = true; 28 System.out.println("向第" + youdupingzi + "号瓶子里面投毒"); 29 } 30 listpingziList.add(pingzi); 31 } 32 // =========================得出有毒的瓶子 33 String silaoshuString = ""; 34 int i = 1; 35 while (true) { 36 y++; 37 String chiyaolaoshu = ""; 38 // 模拟给老鼠喂药 39 if (y == 2) { 40 e++; 41 y = 0; 42 if (e == 2) { 43 s++; 44 e = 0; 45 if (s == 2) { 46 si++; 47 s = 0; 48 if (si == 2) { 49 w++; 50 si = 0; 51 if (w == 2) { 52 l++; 53 w = 0; 54 if (l == 2) { 55 q++; 56 l = 0; 57 if (q == 2) { 58 getDuyaoping(silaoshuString); // 全部遍历完成以后，得出死老鼠都有哪些 59 return; 60 } 61 } 62 } 63 } 64 } 65 } 66 } 67 if (y == 1) { 68 if (chiyaolaoshu.length() < 1) { 69 chiyaolaoshu = "1号老鼠"; 70 } else { 71 chiyaolaoshu += " 和1号老鼠"; 72 } 73 } 74 if (e == 1) { 75 if (chiyaolaoshu.length() < 1) { 76 chiyaolaoshu += "2号老鼠"; 77 } else { 78 chiyaolaoshu += " 和2号老鼠"; 79 } 80 } 81 if (s == 1) { 82 if (chiyaolaoshu.length() < 1) { 83 chiyaolaoshu = "3号老鼠"; 84 } else { 85 chiyaolaoshu += " 和3号老鼠"; 86 } 87 } 88 if (si == 1) { 89 if (chiyaolaoshu.length() < 1) { 90 chiyaolaoshu = "4号老鼠"; 91 } else { 92 chiyaolaoshu += " 和4号老鼠"; 93 } 94 } 95 if (w == 1) { 96 if (chiyaolaoshu.length() < 1) { 97 chiyaolaoshu = "5号老鼠"; 98 } else { 99 chiyaolaoshu += " 和5号老鼠"; 100 } 101 } 102 if (l == 1) { 103 if (chiyaolaoshu.length() < 1) { 104 chiyaolaoshu = "6号老鼠"; 105 } else { 106 chiyaolaoshu += " 和6号老鼠"; 107 } 108 } 109 if (q == 1) { 110 if (chiyaolaoshu.length() < 1) { 111 chiyaolaoshu = "7号老鼠"; 112 } else { 113 chiyaolaoshu += " 和7号老鼠"; 114 } 115 } 116 if(i > 99){ // 7个老鼠测试100个瓶子有富余 117 System.out.println("所有瓶子都测试过了"); 118 }else{ 119 System.out.println("第" + i + "瓶子药喂给了第" + chiyaolaoshu); 120 if (listpingziList.get(i).isYoudu) { // 如果这瓶药有毒 121 System.out.println("============= 这瓶药有毒第" + chiyaolaoshu + "老鼠一星期后死亡！"); 122 silaoshuString = q.toString() + l.toString() + w.toString() + si.toString() + s.toString() 123 + e.toString() + y.toString(); // 得到一星期后的死亡老鼠编号 124 } 125 } 126 i++; // 下一瓶药测试 127 } 128 } 129 130 private static void getDuyaoping(String silaoshuString) { 131 132 String duyao = Integer.valueOf(silaoshuString, 2).toString(); 133 System.out.println("经老鼠检测，有毒的瓶子为：" + duyao); 134 } 135 136 public static class Pingzi { 137 public boolean isYoudu = false; 138 } 139 }
得出输出结果如下：
1 向第88号瓶子里面投毒 2 第1瓶子药喂给了第1号老鼠 3 第2瓶子药喂给了第2号老鼠 4 第3瓶子药喂给了第1号老鼠 和2号老鼠 5 第4瓶子药喂给了第3号老鼠 6 第5瓶子药喂给了第1号老鼠 和3号老鼠 7 第6瓶子药喂给了第2号老鼠 和3号老鼠 8 第7瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 9 第8瓶子药喂给了第4号老鼠 10 第9瓶子药喂给了第1号老鼠 和4号老鼠 11 第10瓶子药喂给了第2号老鼠 和4号老鼠 12 第11瓶子药喂给了第1号老鼠 和2号老鼠 和4号老鼠 13 第12瓶子药喂给了第3号老鼠 和4号老鼠 14 第13瓶子药喂给了第1号老鼠 和3号老鼠 和4号老鼠 15 第14瓶子药喂给了第2号老鼠 和3号老鼠 和4号老鼠 16 第15瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和4号老鼠 17 第16瓶子药喂给了第5号老鼠 18 第17瓶子药喂给了第1号老鼠 和5号老鼠 19 第18瓶子药喂给了第2号老鼠 和5号老鼠 20 第19瓶子药喂给了第1号老鼠 和2号老鼠 和5号老鼠 21 第20瓶子药喂给了第3号老鼠 和5号老鼠 22 第21瓶子药喂给了第1号老鼠 和3号老鼠 和5号老鼠 23 第22瓶子药喂给了第2号老鼠 和3号老鼠 和5号老鼠 24 第23瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和5号老鼠 25 第24瓶子药喂给了第4号老鼠 和5号老鼠 26 第25瓶子药喂给了第1号老鼠 和4号老鼠 和5号老鼠 27 第26瓶子药喂给了第2号老鼠 和4号老鼠 和5号老鼠 28 第27瓶子药喂给了第1号老鼠 和2号老鼠 和4号老鼠 和5号老鼠 29 第28瓶子药喂给了第3号老鼠 和4号老鼠 和5号老鼠 30 第29瓶子药喂给了第1号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 31 第30瓶子药喂给了第2号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 32 第31瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 33 第32瓶子药喂给了第6号老鼠 34 第33瓶子药喂给了第1号老鼠 和6号老鼠 35 第34瓶子药喂给了第2号老鼠 和6号老鼠 36 第35瓶子药喂给了第1号老鼠 和2号老鼠 和6号老鼠 37 第36瓶子药喂给了第3号老鼠 和6号老鼠 38 第37瓶子药喂给了第1号老鼠 和3号老鼠 和6号老鼠 39 第38瓶子药喂给了第2号老鼠 和3号老鼠 和6号老鼠 40 第39瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和6号老鼠 41 第40瓶子药喂给了第4号老鼠 和6号老鼠 42 第41瓶子药喂给了第1号老鼠 和4号老鼠 和6号老鼠 43 第42瓶子药喂给了第2号老鼠 和4号老鼠 和6号老鼠 44 第43瓶子药喂给了第1号老鼠 和2号老鼠 和4号老鼠 和6号老鼠 45 第44瓶子药喂给了第3号老鼠 和4号老鼠 和6号老鼠 46 第45瓶子药喂给了第1号老鼠 和3号老鼠 和4号老鼠 和6号老鼠 47 第46瓶子药喂给了第2号老鼠 和3号老鼠 和4号老鼠 和6号老鼠 48 第47瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和4号老鼠 和6号老鼠 49 第48瓶子药喂给了第5号老鼠 和6号老鼠 50 第49瓶子药喂给了第1号老鼠 和5号老鼠 和6号老鼠 51 第50瓶子药喂给了第2号老鼠 和5号老鼠 和6号老鼠 52 第51瓶子药喂给了第1号老鼠 和2号老鼠 和5号老鼠 和6号老鼠 53 第52瓶子药喂给了第3号老鼠 和5号老鼠 和6号老鼠 54 第53瓶子药喂给了第1号老鼠 和3号老鼠 和5号老鼠 和6号老鼠 55 第54瓶子药喂给了第2号老鼠 和3号老鼠 和5号老鼠 和6号老鼠 56 第55瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和5号老鼠 和6号老鼠 57 第56瓶子药喂给了第4号老鼠 和5号老鼠 和6号老鼠 58 第57瓶子药喂给了第1号老鼠 和4号老鼠 和5号老鼠 和6号老鼠 59 第58瓶子药喂给了第2号老鼠 和4号老鼠 和5号老鼠 和6号老鼠 60 第59瓶子药喂给了第1号老鼠 和2号老鼠 和4号老鼠 和5号老鼠 和6号老鼠 61 第60瓶子药喂给了第3号老鼠 和4号老鼠 和5号老鼠 和6号老鼠 62 第61瓶子药喂给了第1号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 和6号老鼠 63 第62瓶子药喂给了第2号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 和6号老鼠 64 第63瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 和6号老鼠 65 第64瓶子药喂给了第7号老鼠 66 第65瓶子药喂给了第1号老鼠 和7号老鼠 67 第66瓶子药喂给了第2号老鼠 和7号老鼠 68 第67瓶子药喂给了第1号老鼠 和2号老鼠 和7号老鼠 69 第68瓶子药喂给了第3号老鼠 和7号老鼠 70 第69瓶子药喂给了第1号老鼠 和3号老鼠 和7号老鼠 71 第70瓶子药喂给了第2号老鼠 和3号老鼠 和7号老鼠 72 第71瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和7号老鼠 73 第72瓶子药喂给了第4号老鼠 和7号老鼠 74 第73瓶子药喂给了第1号老鼠 和4号老鼠 和7号老鼠 75 第74瓶子药喂给了第2号老鼠 和4号老鼠 和7号老鼠 76 第75瓶子药喂给了第1号老鼠 和2号老鼠 和4号老鼠 和7号老鼠 77 第76瓶子药喂给了第3号老鼠 和4号老鼠 和7号老鼠 78 第77瓶子药喂给了第1号老鼠 和3号老鼠 和4号老鼠 和7号老鼠 79 第78瓶子药喂给了第2号老鼠 和3号老鼠 和4号老鼠 和7号老鼠 80 第79瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和4号老鼠 和7号老鼠 81 第80瓶子药喂给了第5号老鼠 和7号老鼠 82 第81瓶子药喂给了第1号老鼠 和5号老鼠 和7号老鼠 83 第82瓶子药喂给了第2号老鼠 和5号老鼠 和7号老鼠 84 第83瓶子药喂给了第1号老鼠 和2号老鼠 和5号老鼠 和7号老鼠 85 第84瓶子药喂给了第3号老鼠 和5号老鼠 和7号老鼠 86 第85瓶子药喂给了第1号老鼠 和3号老鼠 和5号老鼠 和7号老鼠 87 第86瓶子药喂给了第2号老鼠 和3号老鼠 和5号老鼠 和7号老鼠 88 第87瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和5号老鼠 和7号老鼠 89 第88瓶子药喂给了第4号老鼠 和5号老鼠 和7号老鼠 90 ============= 这瓶药有毒第4号老鼠 和5号老鼠 和7号老鼠老鼠一星期后死亡！ 91 第89瓶子药喂给了第1号老鼠 和4号老鼠 和5号老鼠 和7号老鼠 92 第90瓶子药喂给了第2号老鼠 和4号老鼠 和5号老鼠 和7号老鼠 93 第91瓶子药喂给了第1号老鼠 和2号老鼠 和4号老鼠 和5号老鼠 和7号老鼠 94 第92瓶子药喂给了第3号老鼠 和4号老鼠 和5号老鼠 和7号老鼠 95 第93瓶子药喂给了第1号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 和7号老鼠 96 第94瓶子药喂给了第2号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 和7号老鼠 97 第95瓶子药喂给了第1号老鼠 和2号老鼠 和3号老鼠 和4号老鼠 和5号老鼠 和7号老鼠 98 第96瓶子药喂给了第6号老鼠 和7号老鼠 99 第97瓶子药喂给了第1号老鼠 和6号老鼠 和7号老鼠 100 第98瓶子药喂给了第2号老鼠 和6号老鼠 和7号老鼠 101 第99瓶子药喂给了第1号老鼠 和2号老鼠 和6号老鼠 和7号老鼠 102 所有瓶子都测试过了 103 所有瓶子都测试过了 104 所有瓶子都测试过了 105 所有瓶子都测试过了 106 所有瓶子都测试过了 107 所有瓶子都测试过了 108 所有瓶子都测试过了 109 所有瓶子都测试过了 110 所有瓶子都测试过了 111 所有瓶子都测试过了 112 所有瓶子都测试过了 113 所有瓶子都测试过了 114 所有瓶子都测试过了 115 所有瓶子都测试过了 116 所有瓶子都测试过了 117 所有瓶子都测试过了 118 所有瓶子都测试过了 119 所有瓶子都测试过了 120 所有瓶子都测试过了 121 所有瓶子都测试过了 122 所有瓶子都测试过了 123 所有瓶子都测试过了 124 所有瓶子都测试过了 125 所有瓶子都测试过了 126 所有瓶子都测试过了 127 所有瓶子都测试过了 128 所有瓶子都测试过了 129 所有瓶子都测试过了 130 经老鼠检测，有毒的瓶子为：88
7只老鼠测试100个瓶子