本文主要是介绍有1000个一模一样的瓶子,其中有999瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有10只小白鼠和一星期的时间,如何检验出那个瓶子里有毒药?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
浅谈一下1000瓶水有关思路(图解)与用java代码具体解决方案
1,原题
面试题:有1000个一模一样的瓶子,其中有999瓶是普通的水,有1瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有10只小白鼠和一星期的时间,如何检验出那个瓶子里有毒药?(1000瓶水,1瓶毒药,1星期死亡,10只老鼠)
2,四种思路
今天老师说了如上这道题。自己感觉比较有趣。网上有各种奇思妙想,现在我把其中自己感觉最好的四种摘抄放在这里(主要参考网址链接:http://www.zhihu.com/question/19676641),最后附自己根据他们的想法用Java代码写的具体实现。
①决策树法:
可能有人觉得,这多简单啊,用0.2秒联想一下卡诺图(或者3-8译码器),打个响指,答案不就出来了吗?但是我想说,这是需要天才的。可我认为好的解题思路,是不需要天才便可解答的思路。换句话说,依赖于天才的解题方法不是个好的方法。再者,即便对于天才,我想剥清那灵机一闪的背后,意识的水面下庞大的无意识洪流,是以什么为根据运行的。再延伸下去就要到很多大师都谈到过的知识与灵感的大问题了,不展开了。
说得简单点,我想回答的是,我没想到这个方法,凭什么他就想到。现在就来谈谈这个凭什么。
首先,题目做了个巧妙的障眼,把1024改成1000。但根据经验,还是不难想到,要用这么少的老鼠分出这么大的任务量,肯定有指数爆炸的功劳。或者说,把问题对数分解。从而不难想到2^10=1024这个数量关系。
为了问题更容易理解,不妨把问题做一个变形:
问题2:把原问题中的1000个瓶子改成8个瓶子,10只老鼠改成3只老鼠。其它一样。
这样,问题2肯定有了个解法。下面的问题是,这背后的数量关系的本质是什么?
按照职业和个人知识背景的不同,不同的人可能有不同的联想。如果你学过算法,不难从原问题的2^10=1024数量关系中想到二分查找算法思想。问题是这里只有单步(一个单位时间,或一个指令周期)计算时间。没错,老鼠负责做测试,就是一个处理机,符合计算的本质。于是,为了问题易于理解,不妨进一步做一次变形:
问题3:把问题2中的3只老鼠改成1只老鼠,但是老鼠有3条命,并且时间限制从一个星期改成3个星期。其它一样。
于是,成了一个典型的二分查找问题,2^10=1024这个数量关系依然适用。这是按照程序员的思维走到二分查找的。但如果你不是程序员呢?或者说,自然而然想到变换到二分查找,这和一步联想卡诺图(或3-8译码器)有什么区别呢?更甚,二分查找的本质又是什么?为什么不是三分?
首先,因为老鼠只能通过活蹦乱跳,或死翘翘,来报出编码为0或1的实验结果,所以查找中的“二分”,可以说是直接的。
再者,为什么不是三分?
二分的本质在于,每次处理,都把问题规模降解为原来的1/2,这才是问题得以解决的关键!为何不是1/3?
杨振宁说:“对称支配宇宙力量。”有一本科普书叫《可畏的对称》。有一种世界通行的说法叫“一枚硬币的两面”。有一种学说叫辩证法。再说,连阴阳和谐都要出来了,打住。暂时还不用这么玄乎。
为什么不是1/3?因为如果是1/3,那么在老鼠给出0或1的不同答案的时候,你如果幸运,就是把问题规模降为了1/3;如果不幸,就只降为了2/3。我们说,依赖于运气的方法不是足够理想的方法。如果可以依赖于幸运,那你为何不说原题的解法,靠纯蒙就能做到?在命运之神的全力狙击下,依然肯定能按期交付的方法,才是可控的方法,才是够理想的方法。如果你学过算法,可以知道这也是一种叫“随机化算法思想”的奥妙。而且和算法研究中,关注于“最坏情况运行时间”的研究原则一致。所以二分。
那么在二分查找的背后,又是怎样的规律?
基于测试(比较)的查找背后,是决策树模型。如图:
二分查找是以时间迭代来下降到决策树的叶子;而在这里的原题中只有单步的运行时间,却有多个处理机,明显是以空间迭代的方式下降到决策树的叶子。学过算法的又要说“Aha”了,“时间换空间,或者空间换时间”。事实上,这也是并行计算的思想。可以把这个看作是二分查找的并行实现。
如果你一开始想到的是逻辑门电路,那么我想提醒数字电路的运行方式就是并行的。数字电路某种程度上就是并行机。
同时,这也是“量子计算机无法完成算法之外的任务,却可以把串行算法,并行地实现”的真谛所在。
现在,问题2中,三只老鼠同时单步内吐出0或1的答案。解的组合便是2^3=8,正好解决问题。
剩下的便是编码了。0或1各代表什么可以自定。因为只有0或1,二进制编码是自然的,也是直接的。吐出0或1的是老鼠,所以明显老鼠对应于一个二进制位(或称一个bit处理单元)。3只老鼠,3个二进制位。老鼠从低位到高位,编码为:0, 1, 2。
3位二进制数够简单,所以先把所有数枚举出来再说:
000=0
001=1
010=2
011=3
100=4
101=5
110=6
111=7
然后我实在抑制不住直接下一步跳入3-8译码电路类比的冲动。但是我们再来问几个为什么。
注意到每个位,0和1各占一半(这也是自然,穷举了3位二进制数嘛),这和为了均等吐出0和1的可能性,需要的对老鼠的输入是一致的。
(先烂尾到这里,未完待续)
总之,10只老鼠就像10根地址线,可以寻址1024个瓶子(内存单元)。至于理由根据,笔者也暂时不清。笔者也无暇查看编址译址电路的早期思想萌芽,产生于哪些论文中。笔者也隐约觉得应用信息熵的理论, 就可以理想地、“无需想象力”地、坚实地,一步解决。但其实信息熵的理论是什么样的,我也不太清楚,只是猜想。你问我为什么不去学信息熵?也是因为懒啊。
②网图法
从1000个瓶子跟10个老鼠这里直觉就是会跟2的10次方有关系
也学是学计算机的对二进制比较熟悉吧
联想到要用10这个数字来构造1000种可能而 2的10次方=1024>1000,而且每条老鼠的结果就两种可能被毒死而没被毒死
这个问题就把十个老鼠当作十个二进制的位,十位二进制能表示的数字个数是1024个,所以即使瓶子数量是1024也是可以找出来结果的,具体办法就是把一千个瓶子标上序号(先拿出来一瓶,剩下的瓶子从1开始编号),假设 是编号为n的有毒 比如n是 512那么 写成二进制就是1000000000,现在让你找这个序号是多少,相当于让你确定这个十位的二进制数每一位的数字是什么,so 我们先来确定第一位,我们使用正向确定法,就是确定这位是不是1(反向推测就是确定这位是不是0),怎么确定呢,我们先找到这一位是1的所有的数值,然后把这些数值对应的瓶子里面的液体取出来混合,让第一个老鼠喝掉,然后第二位,第三位.....依次类推到最后一位。最后十个老鼠都喝了512个瓶子的液体,一周后,哪个老鼠死了那一位就是1,得到一个十位的二进制数字,转换成十进制就搞定了,比如我们之前举的例子是编号512这瓶,那么肯定就是只有第一个老鼠死了,得到结果是1000000000
③数学归纳法
备注:跟题解无关,不过证明了2^n次方之所以产生结果的严密数学论证
问题可以描述为:有2的n次方个瓶子和n只老鼠,瓶子里装的是水,有一个瓶子的水有毒,老鼠喝了后第7天会死,那么在第7天能识别出这瓶毒药吗?
证明:
当n=1时,把其中一个瓶子的水给老鼠喝第7天能识别出毒药。
假设当n=k时,第7天也能识别这瓶毒药。
当n=k+1时,
假设瓶子的编号为1,2,3 ...直到 2的(k+1)次方。
将每两个瓶子分为一组,刚好可分为2的k次方个组(其中编号为 i 的瓶子和编号为 (2的k次方)+i 的瓶子是一组)。
那么用k只老鼠第7天就能确定是那一组瓶子里有毒药。假设最后结果是第m组有毒(即编号为 m 和 (2的k次方)+m 的两个瓶子)。
同时将编号从 2的k次方+1 到 2的(k+1)次方 的瓶子(共2的k次方个瓶子)的水给第 k+1只老鼠喝。(关键步骤)
如果第7天第k+1只老鼠没死,可以得知毒药在编号为 1 到 2的k次方 的瓶子中,由此可知是编号为m的瓶子有毒。
如果第7天第k+1只老鼠死了,可以得知毒药在编号为 2的k次方+1 到 2的(k+1)次方 的瓶子中,由此可知是编号为 (2的k次方)+m 的瓶子有毒。
因此n为自然数时,都能识别出这瓶毒药。
④化学法
备注:此想法因时间限制,不对,不过想法独特
取每100瓶药水滴少许进1个瓶子,得10瓶混合药水分给10只老鼠,1只老鼠死;再将死老鼠这100瓶平均分成10组,取每10瓶药水滴少许进1个瓶子,得10瓶混合药水,其中9瓶给9只老鼠喝,能得到混有毒药的10瓶药水;然后这10瓶平均分成5组,取每2瓶药水滴少许进1个瓶子,得5瓶混合药水,分给5只老鼠喝,1只老鼠死,得到混有毒药的2瓶药水;再取出给2只老鼠喝,得到毒药。
3,具体Java代码实现
①具体代码
import java.util.Scanner;
/*** to search the one with poison from bottles* @author Sunkun* Date: 2013.09.26*/
public class MousePoison {public static void main(String[] args) {int bottle, tester; // bottle为瓶子数,tester为实验者个数Scanner input = new Scanner(System.in);// 判断保证输入能得到实验结果while(true){System.out.println("请分别输入瓶数和实验者(如老鼠)数");bottle = input.nextInt();tester = input.nextInt();if(Math.pow(2, tester) < bottle){System.out.println("此方案不能实现实验要求!\n请重新输入");continue;}else{break;}}// 要求用户,按要求输入1星期后,实验的观察结果System.out.println("系统已经自动给实验者,按从1至" + tester + "的顺序依次排序,并贴上标签");System.out.println("已按实验要求(思想为二进制)实验,已经过了1星期");System.out.println("请用户依次输入1星期后死亡的实验者编号");System.out.println("请用户输入总共死亡的个数:");int dead = input.nextInt(); // dead用于储存死亡的个数System.out.println("它们的编号从小到大依次为:");int[] number = new int[dead]; // number数组用于储存死亡试验品的标签序号for(int i = 0; i < dead; i++){number[i] = input.nextInt();}char a[] = new char[tester];char b[] = new char[tester];for(int i = 0; i < tester; i++){a[i] = '0';}for(int i = 0; i < dead; i++){a[number[i]-1] = '1';}// 把实验结果逆序for(int i = 0; i < tester; i++){b[tester-i-1] = a[i];}// 把逆序后的实验结果(二进制)转换为十进制double result1 = 0;for(int i = 0; i < tester; i++){if(b[i] == '1'){result1 = result1 + Math.pow(2, tester-i-1);}}// 根据实验结果判断有毒的是哪一瓶for(int i = 0; i < bottle; i++){if(result1 == i){System.out.println("得出有毒的是第" + (i+1) + "瓶");break;}else{continue;}}}
}
②测试结果
4,备注:
因为时间原因,暂时就写成这样,如果您有更好的想法,代码建议或算法,欢迎留言,大家相互学习,共同进步
这篇关于有1000个一模一样的瓶子,其中有999瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有10只小白鼠和一星期的时间,如何检验出那个瓶子里有毒药?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!