-
-
[原创]最近微博里很热的1000瓶子10小白鼠找毒药问题
-
发表于: 2012-3-29 22:27
-
有 1000 个一模一样的瓶子，
其中有 999 瓶是普通的水，有一瓶是毒药。
任何喝下毒药的生物都会在一星期之后死亡。
现在，你只有 10 只小白鼠和一星期的时间，
如何检验出哪个瓶子里有毒药？
原帖地址
http://www.zhihu.com/question/19676641
提示：使用伟大的二进制
从1000个瓶子跟10个老鼠这里直觉就是会跟2的10次方有关系
也学是学计算机的对二进制比较熟悉吧
联想到要用10这个数字来构造1000种可能而 2的10次方=1024>1000
而且每条老鼠的结果就两种可能被毒死而没被毒死
这个问题就把十个老鼠当作十个二进制的位，十位二进制能表示的数字个数是1024个，所以即使瓶子数量是1024也是可以找出来结果的，具体办法就是把一千个瓶子标上序号（先拿出来一瓶，剩下的瓶子从1开始编号），假设 是编号为n的有毒 比如n是 512那么 写成二进制就是1000000000，现在让你找这个序号是多少，相当于让你确定这个十位的二进制数每一位的数字是什么（此时你并不知道是512），so 我们先来确定第一位，我们使用正向确定法，就是确定这位是不是1（反向推测就是确定这位是不是0），怎么确定呢，我们先找到这一位是1的所有的数值，然后把这些数值对应的瓶子里面的液体取出来混合，（此时一就是512一直到99）让第一个老鼠喝掉，然后第二位，第三位.....依次类推到最后一位。最后十个老鼠都喝了瓶子的液体，一周后，哪个老鼠死了那一位就是1，得到一个十位的二进制数字，转换成十进制就搞定了，比如我们之前举的例子是编号512这瓶，那么肯定就是只有第一个老鼠死了，得到结果是1000000000
（如果任何老鼠都没有死即结果是0000000000 ,就是说明我们拿出来的那瓶是毒药）
附上1000苹果问题的一点解答的想法
题目】 1000个苹果放入10个箱子。客户如果要获得1~1000个苹果中的任意个数，都可以整箱搬，而不用拆开箱子。问是否有这样的装箱方法？
你说的1000苹果是这个问题吧？
这个题目直观多了
其实这个跟我们学的那个什么信息安全里面的某些问题到时有异曲同工之妙，也跟之前那个金条分三段发七天工资的问题差不多
这个相对于找毒药问题比较简单，首先即使你不懂也能有思路，首先1肯定得有因为它不可能得于任何自然数的和之后你发现2也不能如果你分两个箱子为1岂不是很浪费so 你有了1 2 你就有了 3 so 你应该发现点规律了吧 不行的话你继续 分一个4 1 2 4 你能组合小于8的任何数
so 你应该明白了吧 其实 1 2 4 8 16 这种数是可以构造任意数值的 因为 你首先知道 二进制 是可以表示任何整数的
二进制每一位都是对应前面的1 2 4 8 所以你有了1 2 4 8 16 就相当于 你有了 这几位的二进制 当客户提出一个整数的时候你就把他转化成
二进制比如客户想要127个 也就是 1111111 那你就取 1 2 4 8 16 32 64的箱子给他 就行了
其中有 999 瓶是普通的水，有一瓶是毒药。
任何喝下毒药的生物都会在一星期之后死亡。
现在，你只有 10 只小白鼠和一星期的时间，
如何检验出哪个瓶子里有毒药？
原帖地址
http://www.zhihu.com/question/19676641
提示：使用伟大的二进制
从1000个瓶子跟10个老鼠这里直觉就是会跟2的10次方有关系
也学是学计算机的对二进制比较熟悉吧
联想到要用10这个数字来构造1000种可能而 2的10次方=1024>1000
而且每条老鼠的结果就两种可能被毒死而没被毒死
这个问题就把十个老鼠当作十个二进制的位，十位二进制能表示的数字个数是1024个，所以即使瓶子数量是1024也是可以找出来结果的，具体办法就是把一千个瓶子标上序号（先拿出来一瓶，剩下的瓶子从1开始编号），假设 是编号为n的有毒 比如n是 512那么 写成二进制就是1000000000，现在让你找这个序号是多少，相当于让你确定这个十位的二进制数每一位的数字是什么（此时你并不知道是512），so 我们先来确定第一位，我们使用正向确定法，就是确定这位是不是1（反向推测就是确定这位是不是0），怎么确定呢，我们先找到这一位是1的所有的数值，然后把这些数值对应的瓶子里面的液体取出来混合，（此时一就是512一直到99）让第一个老鼠喝掉，然后第二位，第三位.....依次类推到最后一位。最后十个老鼠都喝了瓶子的液体，一周后，哪个老鼠死了那一位就是1，得到一个十位的二进制数字，转换成十进制就搞定了，比如我们之前举的例子是编号512这瓶，那么肯定就是只有第一个老鼠死了，得到结果是1000000000
（如果任何老鼠都没有死即结果是0000000000 ,就是说明我们拿出来的那瓶是毒药）
附上1000苹果问题的一点解答的想法
题目】 1000个苹果放入10个箱子。客户如果要获得1~1000个苹果中的任意个数，都可以整箱搬，而不用拆开箱子。问是否有这样的装箱方法？
你说的1000苹果是这个问题吧？
这个题目直观多了
其实这个跟我们学的那个什么信息安全里面的某些问题到时有异曲同工之妙，也跟之前那个金条分三段发七天工资的问题差不多
这个相对于找毒药问题比较简单，首先即使你不懂也能有思路，首先1肯定得有因为它不可能得于任何自然数的和之后你发现2也不能如果你分两个箱子为1岂不是很浪费so 你有了1 2 你就有了 3 so 你应该发现点规律了吧 不行的话你继续 分一个4 1 2 4 你能组合小于8的任何数
so 你应该明白了吧 其实 1 2 4 8 16 这种数是可以构造任意数值的 因为 你首先知道 二进制 是可以表示任何整数的
二进制每一位都是对应前面的1 2 4 8 所以你有了1 2 4 8 16 就相当于 你有了 这几位的二进制 当客户提出一个整数的时候你就把他转化成
二进制比如客户想要127个 也就是 1111111 那你就取 1 2 4 8 16 32 64的箱子给他 就行了
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
思路可以发散出来。
|
|
|
|
|
|
|
|
|
|
|
|
个人认为这个应该是大学数字电路的译码器的一个变通的灵活运用。
在这个例子中，3-8译码器正向的情况是3输入A3-A2-A1，将产生8输出。 受A3控制的是1XX即是(4、5、6、7)，受A2控制的是X1X即是(2、3、6、7），受A1控制的是XX1即是(1、3、5、7)。 显然可以得出一个结论， (4、5、6、7)有效则A3肯定是1，否则A3是0； (2、3、6、7)有效则A2肯定是1，否则A2是0； (1、3、5、7)有效则A1肯定是1，否则A1是0； 因此这3组集合肯定可以唯一确定，A3-A2-A1，即是可以唯一确定是哪个编号有问题！ 以下是数电的内容： 一. 译码器 译码器的功能是对具有特定含义的输入代码进行"翻译"，将其转换成相应的输出信号。 译码器的种类很多，常见的有二进制译码器、二-十进制译码器和数字显示译码器。 1．二进制译码器 (1) 定义 二进制译码器:能将n个输入变量变换成2n个输出函数，且输出函数与输入变量构成的最小项具有对应关系的一种多输出组合逻辑电路。 (2) 特点 ● 二进制译码器一般具有n个输入端、2n个输出端和一个(或多个)使能输入端。 ● 在使能输入端为有效电平时，对应每一组输入代码，仅一个输出端为有效电平，其余输出端为无效电平(与有效电平相反)。 ● 有效电平可以是高电平(称为高电平译码)，也可以是低电平(称为低电平译码)。 (3) 典型芯片 常见的MSI二进制译码器有2-4线(2输入4输出)译码器、3-8线(3输入8输出)译码器和4-16线(4输入16输出)译码器等。图7.7(a)、(b)所示分别是T4138型3-8线译码器的管脚排列图和逻辑符号。 
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
 使用的是二进制 二进制每一位就两种可能 0 或者 1 虽然说有毒的瓶子的编号知道之前是有1000中可能的 但是二进制的表示方式就两种可能要么正常的1 就代表 1 要么反向的 0 代表 1 看起来是十位但是十位肯定使用的是同样的表示方式了 所以冗余并不能被利用 也就无法扩展其他的表示方式 比如 你想使用冗余的输出可能 假设你想使用 是 1111111111 =1023 这个结果 那么 按照之前我说的 1111111111 要么表示 1111111111 要么表示0000000000 因为在你结果的十位二进制数中0代表 1 还是代表0 必须是固定的 不能你的十位二进制数中 第一位代表0 第二位又代表1去了 除非你的瓶子数低于1024的一半 那你就能使用相反的表示方式了 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
我 同学有人拿 PHP 实现了 用户输入瓶子个数
它就能输出 需要的老鼠个数 以及每个老鼠 要喝的任务 最后你提交一种老鼠死亡的结果 就可以判定哪瓶是有毒的 
|
|
|
好像看看代码的逻辑。。。1000瓶那得多少判断啊。。。如果代码要写的很精炼，那还真不简单。
|
|
|
|
