面试智力题,1000瓶水,其中一瓶有毒,而且毒性无敌,稀释一亿倍毒性都不减,毒性的发作时间最长为1小时,请问怎样可以在两个小时之内找出哪瓶水有毒

您所在的位置:网站首页 给老鼠喝什么水能死掉 面试智力题,1000瓶水,其中一瓶有毒,而且毒性无敌,稀释一亿倍毒性都不减,毒性的发作时间最长为1小时,请问怎样可以在两个小时之内找出哪瓶水有毒

面试智力题,1000瓶水,其中一瓶有毒,而且毒性无敌,稀释一亿倍毒性都不减,毒性的发作时间最长为1小时,请问怎样可以在两个小时之内找出哪瓶水有毒

2024-07-12 20:32| 来源: 网络整理| 查看: 265

面试遇到的一道智力题 1000瓶水,其中一瓶有毒,而且毒性无敌,稀释一亿倍毒性都不减,毒性的发作时间最长为1小时,其中可能会在一小时内的任意时刻发作,但是最长时间是一小时,请问怎样可以在两个小时之内找出哪瓶水有毒。

解法1、 当时我的想法是二分法,1000瓶水先分成两份,一份500瓶,然后左右两个一半的500瓶水中每瓶取一滴混合起来喂给一只老鼠,如果左边的老鼠死了,就说明左边500瓶水中有一瓶是有毒的,反之,就是右边500瓶,然后再对其中500瓶水继续分成两半混合。如此下去,由于2^10 = 1024,也就是最多只需要10只老鼠就可以试出来有毒的水。这样的话虽然能用的小白鼠是10只,但是时间太长了,每次喂老鼠的过程是有一个先后顺序的,不能同时进行,所以是不通过的。

以下是其他大佬给的解答,利用布隆过滤器的思想

解法2、

方法很巧妙,一个小时就能找出有毒的那瓶水。 因为每只老鼠有生死2种状态,利用2进制,10只老鼠可以有2^10=1024中状态,可以判断出1000瓶水中有毒的那瓶。 将问题域缩小来分析,例如:有7瓶水,其中1瓶有毒,小白鼠只要尝一点带毒 的水1小时后就会死亡,由上可知2^3=8 > 7所以3只就够了.

下面将7瓶水以2进制编号: 001 第一瓶,010 第二瓶,011 第三瓶,100 第四瓶,101 第五瓶,110 第六瓶,111 第七瓶 将3位2进制数第一位为1的瓶子中取出1滴放在一起分给老鼠A,即4,5,6,7瓶 将3位2进制数第二位为1的瓶子中取出1滴放在一起分给老鼠B,即2,3,6,7瓶 将3位2进制数最后三位二进制为1的瓶子中取出1滴放在一起分给老鼠C,即1,3,5,7瓶 然后等1个小时,按ABC顺序给死了的老鼠标号为1,没死的为0这个2进制的十进制数就是有毒的瓶子标号 例如第三瓶有毒:则BC老鼠会死,为011=3

同理,可以给1000瓶水按上述方法打上如下的二进制标签(10位长度,2^10 = 1024 ): 0000000001 (第1瓶) 0000000010 (第2瓶) 0000000011 (第3瓶) … 1111101000 (第1000瓶)

从编号最后1位是1的所有的瓶子里面取出1滴混在一起(比如从第一瓶,第三瓶,…里分别取出一滴混在一起)并标上记号为1。以此类推,从编号第一位是1的所有的瓶子里面取出1滴混在一起并标上记号为10。现在得到有10个编号的混合液,小白鼠排排站,分别标上10,9,…1号,并分别给它们灌上对应号码的混合液。1个小时过去了,看看老鼠的死亡情况: 从左到右,死了的小白鼠贴上标签1,没死的贴上0,最后得到一个序号,把这个序号换成10进制的数字,就是有毒的那瓶水的编号。



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3