内容举报
请慎重选择举报原因
1000分10组,每组100个试管混合,然后分别喂10个小白鼠
被毒死的那一组,100个再分10组,每组10个,分别喂给剩下的9只
如果都没事,那就是最后一组有毒,如果毒死了,那就是毒死那组
这个时候就只剩下10个试管需要确认了,还剩8或者9只老鼠
直接挨个灌吧,懒得分组了,毒死了就确认了,毒不死就是剩下的那个
看到题目,工程师们立刻开始研究算法,怎么解题,这很好。
然而如果是产品经理的话就不能只为了解题,还要明白问题背后的含义,目的,就本题而言,既然确定了毒药在1000瓶水之间,那么必然有确定这个的依据,请问是谁,通过什么方法判定的?是不是投毒者?如果有判定依据可不可以继续缩小范围?费这个力找出毒药的目的是什么,为了让剩下的999瓶水重回市场吗?怎么确认不会有其它问题?为了产品的安全性以及口碑,可以建议,不用找,直接无害化处理这剩下的1000瓶水,将责任人移交公安机关。
没有时间限制,也没有实验次数限制,难道就是为了考验面试者对问题条件的分析能力和思维拓展的广度?不明白。。。
最少实验次数的话,我选择让小白鼠先繁殖,养着呗,养到1000只,再找1000个人,大家一起测,一次实验出结果。
最少时间的话,分10组,每组1个人、1只小白鼠,同时依次喂水,直到一组小白鼠死了。
最省人,最省小白鼠的话,一个人拿着1只小白鼠依次滴喂这1000瓶水。
干净的试管就是干扰项,每只小白鼠可以重复饮水。
以下为百度搜索
①决策树法: 可能有人觉得,这多简单啊,用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=0001=1010=2011=3100=4101=5110=6111=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只老鼠喝,得到毒药。
有三种方式:
第一种:分组法,将1000瓶分10组,每组的100瓶取样放到同一个试管里,测试9组数据(只需要9只小白鼠,不需要10只),就可判断出有毒的那一组,再将100瓶分成10组,每组的10瓶取样放到同一个试管里,测试9组数据,就可以判断出有毒的那一组还剩10瓶,用同一只小鼠测试就好,最好的情况时小鼠一只不死,最差的情况时死三只;
第二种:中分法,将1000瓶分2组,每组的500瓶取样放到同一个试管里,并喂一只小鼠,小鼠若死亡,则表示在该组中,再将500瓶分2组,每组250瓶取样放到同一个试管里,并喂一只小鼠,接着时125瓶,一组62,一组63,如此重复;最好的情况是小鼠一只不死,最差的情况是死9只
第三种:一瓶一瓶的喂,死一只老鼠;
还有一种是取巧的方式:将1000瓶液体倒在一个瓶子中,这瓶液体就是有毒的,小鼠一只不死
我只有一个想法,小白鼠也是珍贵的生命,作为微软这样的企业,基本的社会责任感和正确的价值观是必备的,毒药我会全部倒掉,再把小白鼠放生,无限多的干净试管捐赠给医院或者研发机构。
如果你们不认同我的做法,我也不屑在这样的企业就职。
1000瓶分10组,每组的10瓶取样放到同一个试管里,并喂小鼠。
毙鼠的那一组重复以上操作,直至筛选出来毒药。
一共消耗试管30支,毙鼠3只,运气最烂的情况下需要喂鼠30次。
这问题不完整
1、瓶子液体数量:是不是带滴管的瓶子?瓶子液体数量能最小化取多少次?
2、毒效:老鼠如何中毒(喂食/注射)?多少浓度才中毒?毒药起效时间要多长?中毒的表现是什么?
1000个瓶子,其中有1瓶毒药。
10只小白鼠可用于测试。
目标是找出含有毒药的那一瓶。
问题转换:我们可以将这个问题看作是二进制编码问题。给每个瓶子编号,从0到999(总共1000个)。每个编号都可以转换为二进制数,最多需要10位(因为2^10 = 1024 > 1000)。例如,瓶子编号999可以转换为二进制数1111100111。
小白鼠与二进制位对应:我们可以使用10只小白鼠,每只对应二进制编号中的一位。每只小白鼠将喝下所有在其代表的二进制位上为1的瓶子中的液体。例如,小白鼠1将喝下所有二进制编号第1位为1的瓶子中的液体,小白鼠2将喝下所有二进制编号第2位为1的瓶子中的液体,以此类推。
实验结果分析:
若某只小白鼠死亡,说明它喝下的液体中含有毒药,即毒药瓶的二进制编号在该小白鼠对应的位置上必定是1。
若小白鼠存活,说明它没喝到毒药,毒药瓶的二进制编号在该小白鼠对应的位置上必定是0。
确定毒药瓶:通过组合10只小白鼠的实验结果,我们可以得到一个10位的二进制数,这个二进制数转换为十进制后,就是含有毒药的瓶子的编号。
讲真的,人家这题目一没说让你用最快的办法,二没说让你用最秀的办法,只说要找出毒药。请注意目标是找到有毒的那瓶水。那就一瓶瓶的给老鼠喂水就行了啊。又是分组又是分析的。你这是面试还是来走秀哦。
那些分组混合的,你怎么知道毒药稀释到何种程度会失效?如果混合失效的话,那你就找不出来有毒的,这和你要找出有毒的那一瓶是目标背离的啊。
把1000个试管分成2组,每组500个,500个在分10组,也就是50个倒在同一试管,如果老鼠没中毒则换第2组,如果老鼠中毒了,剩9只老鼠,那就在老鼠中毒的组再测试,50个试管分9组,6个试管倒入同一试管,老鼠中毒剩8只,中毒的组再用剩下的八只测试就能找到有毒的试管,最多测试4次,至少死3只老鼠就能知道答案
先是第一轮死掉的小鼠不能被replace的情况,小鼠有三种状态,第一轮死,第二轮死,和两轮都没死,那么三种状态可以类比为3进制,小鼠的量程为3^10即59049瓶,具体操作方式为对编码为2的位数,第二轮混合喂。然后是第一轮死掉的小鼠可以被replace的情况,将每1024瓶混合为1滴做第一轮,选定组别后第二轮确定瓶子编码,量程为2^10 * 2^10即1048576瓶。对不能replace的N轮,量程为(N+1)^10,能replace的N轮,量程为2^(10*N)。第二种变体,如果1000瓶里有2瓶毒药,需要多少只小鼠?1000瓶里1瓶毒药有1000种可能性,而1000瓶2瓶毒药则有C(1000,2),即499500种可能性,那么log2(499500) 为18.93,即需要19只小鼠。具体实现方式为以两两混合法将1000瓶拆成499500滴,并用题目1中的方法测得。那么对1000瓶中的N瓶毒药,则需要log2(C(1000,N))只小鼠,若N>=500,则取C(1000,1000-N)。第三种变体,有16瓶水1瓶有毒,用多少只小白鼠能测出14瓶无毒的水?将16瓶药水用二进制XXXX表示,取3只小白鼠来测,测出的状态为XXX,那么毒在XXX0或XXX1中,剩下14瓶无毒。
还有4个有趣回答,继续看^-^
暂时还没回答,等你发挥
本问题来源于【圈子】
产品面试100问
面试官问如何看待加班,该如何巧妙地去回答?
17人次参与讨论
如果不能通过最终轮面试,你希望自己在哪一轮被淘汰?
35人次参与讨论
作为面试官,你觉得新人产品最重要的品质是什么?
8人次参与讨论
面试题:音乐包单个购买或VIP通用,哪个模式对平台更有利?
9人次参与讨论
扫码即可下载app
内容举报
请慎重选择举报原因
邀请回答
想要更快获得答案?试试邀请回答吧~ 今日已邀请0/5
给问题加标签后,可根据标签推荐更专业的用户来回答
微信扫码即可分享
删除后将不会展示在回答列表中
沉底后问题将从推荐列表中移除,此为
智囊团成员特殊权限,请谨慎使用
问题已沉底
用户将无法在列表查看到该问题
沉底操作已达上限,建议联系天天问管理员
处理违规内容
请重新尝试
©2016-2024 - 深圳聚力创想信息科技有限公司 - 粤ICP备14037330号 粤公网安备 44030502002255号
广播电视节目制作经营许可证(粤)字第03109号 增值电信业务经营许可证粤B2-20190788 版权所有 © 深圳聚力创想信息科技有限公司