网上流传着一题淘宝面试题,原题如下:
我们有很多瓶无色的液体,其中有一瓶是毒药,其它都是蒸馏水,实验的小白鼠喝了以后会在5分钟后死亡,而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠,请问一下,我们用这五只小白鼠,5分钟的时间,能够检测多少瓶液体的成分()。A:5,
B:6, C:31, D:32。
+1只小白鼠首先可以想象只有1只小白鼠的情况,毫无疑问,1只小白鼠五分钟只能判断1瓶液体的成分,喝两瓶或以上如果是碰不到毒药,则喝多少瓶也能确定多少瓶;但如果遇到有毒药的瓶子,则不能判断那1瓶是毒药,这样的检测是不合理的。
+2只小白鼠两只小白鼠可以检测3瓶液体成分。从本节开始我们把小白鼠标号N1,N2。首先根据前述结论可知N1,N2小白鼠各喝1瓶液体(N1:1号液体,N2:2号液体)则能够准确判断2瓶液体成分。但是第三瓶的判断可能需要大家稍微转点弯。因为采用的是每个老鼠独立测试液体的方式,每个老鼠的死活并没有任何关联,每个老鼠测试的结果也就无法跟另外的老鼠测试的结果关联。这样做是一般做法,但有没有可能把老鼠联合起来测试来增大测试范围呢?其实是可以的,那就是再拿一瓶3号液体让N1,N2都喝一点。这样有如下
-
喝法(纵向表示液体瓶编号,横向表示小白鼠编号,交叉部分表示小白鼠是否喝了相应的液体):
液体\小白鼠
|
N1
|
N2
|
1
|
喝
|
|
2
|
|
喝
|
3
|
喝
|
喝
|
-
死法(纵向表示N1小白鼠的测试结果,横向表示N2小白鼠的测试结果,交叉部分数值是毒药瓶编号或无毒药。)
+3只小白鼠由上一节的思维方式,我们可以想象3只小白鼠是否能测试远比3瓶或4瓶更多的液体成分呢?思考2只小白鼠的测试方式,大家有没有注意上面采取的方式是N1,N2各喝了1瓶不一样的(N1:1、3号液体,N2:2、3号液体)。我们除了让每只小白鼠单独喝1瓶不一样的液体,另外让N1,N2同时喝了1瓶一样的3号液体。同样,我们可以对3只小白鼠各自喝1瓶不一样的液体后,在3只小白鼠再喝第4瓶一样的液体。测试如下:顺推思维
-
喝法(纵向表示液体瓶编号,横向表示小白鼠编号,交叉部分表示小白鼠是否喝了相应的液体)N1喝1号4号液体;N2喝2号4号液体;N3喝3号4号液体。
液体\小白鼠
|
N1
|
N2
|
N3
|
1
|
喝
|
|
|
2
|
|
喝
|
|
3
|
|
|
喝
|
4
|
喝
|
喝
|
喝
|
-
N1活N2活N3活:1、2、3、4号液体均正常。
-
N1活N2活N3死:1、2、4号液体均正常,3号液体有毒。
-
N1活N2死N3活:1、3、4号液体均正常,2号液体有毒。
-
N1死N2活N3活:2、3、4号液体均正常,1号液体有毒。
-
N1死N2死N3死:1、2、3号液体均正常,4号液体有毒。
-
注意,这里不会出现有2只小白鼠死了另外1只活着的情况,因为只有1瓶液体是毒药,而且我们给3个小白鼠喝的方法只有2种:单独喝某1种液体,集体都喝某种液体。
-
思考:通过如上结论大家有没有觉得怪怪的,或者是不甘心。
-
1只小白鼠测试1瓶液体
-
2只小白鼠测试3瓶液体
-
3只小白鼠测试4瓶液体,根据学数学的增量直觉,是不是太少了?或者如上方法是否有值得发散思维的地方?
发散思维关于上面顺推思维的解决方案,好奇的人就会问可不可以也让3只小白鼠也像2只小白鼠测试的那样两两都再喝1瓶一样的液体呢?这样又增加了3瓶(N1、N2再喝5号液体,N1、N3再喝6号液体,N2、N3再喝7号液体)。是不是就出现如上提到的2只死亡其领外1只活着的情况了?试想如果5号液体是有毒?或者6号液体有毒?7号液体有毒?这样3只小白鼠就能检测7瓶液体成分了。仔细想想之后你会发现这样是可行的。测试情况如下:
-
喝法(纵向表示液体瓶编号,横向表示小白鼠编号,交叉部分表示小白鼠是否喝了相应的液体)
液体\小白鼠
|
N1
|
N2
|
N3
|
1
|
喝
|
|
|
2
|
|
喝
|
|
3
|
|
|
喝
|
4
|
喝
|
喝
|
喝
|
5
|
喝
|
喝
|
|
6
|
喝
|
|
喝
|
7
|
|
喝
|
喝
|
-
N1活N2活N3活:1、2、3、4、5、6、7号液体均正常。
-
N1活N2活N3死:1、2、4、5、6、7号液体均正常,3号液体有毒。
-
N1活N2死N3活:1、3、4、5、6、7号液体均正常,2号液体有毒。
-
N1死N2活N3活:2、3、4、5、6、7号液体均正常,1号液体有毒。
-
N1死N2死N3死:1、2、3、5、6、7号液体均正常,4号液体有毒。
-
N1死N2死N3活:1、2、3、4、6、7号液体均正常,5号液体有毒。
-
N1死N2活N3死:1、2、3、4、5、7号液体均正常,6号液体有毒。
-
N1死N2死N3死:1、2、3、4、5、6号液体均正常,7号液体有毒。至此,所有可能情况已经被枚举完毕。
归纳和发现通过上述分析和思考,想必大家都很想知道这里的原理和推论了。我们把刚刚得到的结论再次贴出:
-
1只小白鼠测试1瓶液体
-
2只小白鼠测试3瓶液体
-
3只小白鼠测试7瓶液体
-
4只小白鼠测试N瓶液体?
-
5只小白鼠呢?
如果你学过数列,你会直接猜出4对应15(24-1=15)。因为前面是
-
1只小白鼠测试21–1瓶液体
-
2只小白鼠测试22–1瓶液体
-
3只小白鼠测试23–1瓶液体
事实上答案就是这样。但是你要怎么证明呢?其实总结起来大家会发现,我们采用了如下策略进行测试:
-
让N只小白鼠每1只喝单独的1瓶
-
让N只小白鼠任意中2只再同时喝1瓶新液体
-
让N只小白鼠任意中3只再同时喝另1瓶新液体
-
。。。
-
让N只小白鼠任意中N只再同时喝1瓶格外新的液体
仔细想想你会发现这样最大限度了利用了联合测试结果,并且刚刚好所有的结果都不冲突。如果你有幸见到老练的实验室工作者,你还会发现这个是他们做这种类型的检测试验的通用方法。
接下来考验你数学功底的时候到了。集合论学习比较过关的人会从上面总结出N个小白鼠可以测试液体瓶数为:Cn1+Cn2 + Cn3+…+ Cnn-1+Cnn如果你集合论的公式不是很熟悉又比较懒,又稍有耐力,那你可以慢慢计算出当小白鼠数量N=10时的结果是1023.但是多了你就不想在浪费时间了。现在想想另外一个问题:一个包含N个不同元素的集合包含的子集合总数是多少(空集合也是集合)?查看高2(2004年)数学书你就知道:总数=Cn0+Cn1+Cn2+
Cn3+…+ Cnn-1+Cnn 。即从中取出0、1、2...3、N-1、N个元素组成的子集合的总数。并且这个问题还有一个很简单的解答方式: 设想其子集合很多,但是每个集合对于元素的包含只有2种可能:包含、不包含。那么N个元素的组合可能即2*2*2*...*2=2n再来对照上面的N个小白鼠测试液体瓶数:Cn1+Cn2+
Cn3+…+ Cnn-1+Cnn= (Cn0+Cn1+Cn2+
Cn3+…+ Cnn-1+Cnn )-Cn0即2n-Cn0。即2n-
1.至此本题答案5只小白鼠能测试的液体瓶数25-
1=31已经解答完毕了。======================================================================================================总结回头想想这个题目,因为只有5小白鼠个,其实可以完全凭着你的发散思维和坚持不用靠集合论等高中以上数学知识搞定的,前提是你足够会发散思维,会总结,推理能力较强。问题的关键处有3个,前2个能帮助你解答本题,后1个能帮助你做出总结和快速算法推论:
-
2个小白鼠能想到同时再喝1瓶新的。
-
3个小白鼠能想到分组在喝,多个小白鼠思考能有条不紊、不乱。
-
N个元素集合子集数量的两种表示法和证明过程
分享到:
相关推荐
提供剑指offer 名企面试官精讲典型编程题和一套编程题的源代码。
剑指offer面试题25:二叉树中和为某一数值的路径。共包含3个文件。 可运行。
剑指offer面试题3(java)
前言2021年1月22日,我从工作超过10年的微软离职,并将于25日入职一家相对而言规模要小很多的初创公司,开始一段新的职业旅程。与所有程序员一样,换公司工作我
请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。输入:每个输入件仅包含一组测试样例。对于每组测试案例,输入一行代表要处理的字符...
《剑指Offer》学习80题,适合面试中提问数据结构和算法,应聘者必备
剑指Offer算法面试题目总结(C、C 实现)
剑指Offer面试题Python实现
因为剑指offer上的面试题有些写的有错误,这是实现了剑指offer中面试题的代码
剑指offer的代码和思路,自己使用python语言实现的。
实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。
《剑指Offer:名企面试官精讲典型编程题》剖析了50个典型的程序员面试题,从基础知识、代码质量、解题思路、优化效率和综合能力五个方面系统整理了影响面试的5个要点。全书分为7章,主要包括面试的流程,讨论面试流程...
剑指Offer名企面试官精讲典型编程题源代码(完整版)
剑指offer刷题笔记(一),大概完成40多道题,语言c++,python,java
剑指offer(C++)1
剑指offer例题代码 不想看书可以直接看代码 学完了找工作、机试、考研都不会有问题 剑指offer例题代码 不想看书可以直接看代码 学完了找工作、机试、考研都不会有问题 剑指offer例题代码 不想看书可以直接看代码 ...
数据结构和算法解析LeetCode解题剑指Offer面试题集.zip
面试题 1:二维数组中的查找(考点: 数组) 1 面试题 2:替换空格(考点: 字符串) 2 面试题 3:从尾到头打印链表(考点: 链表) 2 面试题 4:重建二叉树(考点: 树) 4 面试题 5:用两个栈实现队列(考点: 栈和...
牛客网剑指offer——Java题解.pdf