1000桶酒中寻找一桶毒酒算法

题目:
有1000桶酒,其中1桶有毒。而一旦吃了,毒性会在1周后发作。现在我们用小老鼠做实验,要在1周后找出那桶毒酒,问最少需要多少老鼠,如何检测(老鼠的使用量越少越好,注意,毒性1周后才会发作,而且一周后必须出结果,所以时间紧迫)

思路:
为何需要老鼠做实验,显然是根据老鼠的死活来判断酒的毒性,每一只老鼠只有2种状态,死和活,n只老鼠就是这n个死或活的状态,应该由此敏感的联想到二进制,隐约去感知1000这个数量与n的关系,2^n 能表示多少的信息量呢?2^10 = 1024,想到这里我们可以试着去用10个老鼠去做一下实验。

步骤:
把1000桶酒分别以10位二进制数标号,从0000000001至1111101000,从这1000个二进制数中寻找毒酒,毒酒也一定是0和1的某种组合,所以问题转化为如何得出这个组合的每一位都是多少,我们先思考如何得出第一位(从右到左)是0还是1,结论是只要把所有第一位是1的酒给一只老鼠喝,如果这只老鼠最终死了,可知毒酒的第一位一定是1,如果这只老鼠还活着,可知毒酒第一位一定是0.依次类推,我们使用10只老鼠便可判断毒酒的每一位是多少。从而得到毒酒的二进制数,转化成10进制便只是第几桶。

注:算法非原创,只是换着法表述外加记录

Published: February 06 2013