趣味算法:老鼠试毒瓶问题

二进制的巧妙使用
服务器君一共花费了291.819 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

大家应该都听说过这个老题目:有 1000 个一模一样的瓶子,其中有 999 瓶是普通的水,有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?

这个问题的答案也堪称经典:把瓶子从 0 到 999 依次编号,然后全部转换为 10 位二进制数。让第一只老鼠喝掉1到1000所有二进制数右起第一位是 1 的瓶子,让第二只老鼠喝掉所有二进制数右起第二位是 1 的瓶子,等等。一星期后,如果第一只老鼠死了,就知道毒药瓶子的二进制编号中,右起第一位是 1 ;如果第二只老鼠没死,就知道毒药瓶子的二进制编号中,右起第二位是 0 ……每只老鼠的死活都能确定出 10 位二进制数的其中一位,由此便可知道毒药瓶子的编号了。

现在,有意思的问题来了:如果你有两个星期的时间(换句话说你可以做两轮实验),为了从 1000 个瓶子中找出毒药,你最少需要几只老鼠?注意,在第一轮实验中死掉的老鼠,就无法继续参与第二次实验了。

答案:7 只老鼠就足够了。事实上,7 只老鼠足以从 3^7 = 2187 个瓶子中找出毒药来。首先,把所有瓶子从 0 到 2186 编号,然后全部转换为 7 位三进制数。现在,让第一只老鼠喝掉所有三进制数右起第一位是 2 的瓶子,让第二只老鼠喝掉所有三进制数右起第二位是 2 的瓶子,等等。一星期之后,如果第一只老鼠死了,就知道毒药瓶子的三进制编号中,右起第一位是 2 ;如果第二只老鼠没死,就知道毒药瓶子的三进制编号中,右起第二位不是 2,只可能是 0 或者 1 ……也就是说,每只死掉的老鼠都用自己的生命确定出了,三进制编号中自己负责的那一位是 2 ;但每只活着的老鼠都只能确定,它所负责的那一位不是 2 。于是,问题就归约到了只剩一个星期时的情况。在第二轮实验里,让每只活着的老鼠继续自己未完成的任务,喝掉它负责的那一位是 1 的所有瓶子。再过一星期,毒药瓶子的三进制编号便能全部揭晓了。

类似地,我们可以证明, n 只小白鼠 t 周的时间可以从 (t+1)^n 个瓶子中检验出毒药来。

总结:时间换取资源(老鼠)。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1834,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1834

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《敏捷软件开发(原则模式与实践)》 马丁 (作者), 邓辉 (译者)

《敏捷软件开发:原则模式与实践》由享誉全球的软件开发专家和软件工程大师Robert C.Martin将向您展示如何解决软件开发人员、项目经理及软件项目领导们所面临的最棘手的问题。这本综合性、实用性的敏捷开发和极限编程方面的指南,是由敏捷开发的创始人之一所撰写的。1.讲述在预算和实践要求下,软件开发人员和项目经理如何使用敏捷开发完成项目;2.使用真实案例讲解如何用极限编程来设计、测试、重构和结对编程;3.包含了极具价值的可多次使用的C++和JAVA源代码;4.重点讲述了如何使用UML和设计模式解决面向客户系统的问题。

更多计算机宝库...