问题1
有1000个完全相同的瓶子,其中999瓶是普通水,1瓶是毒药。
任何喝下毒药的生物都会在一星期之后死亡。现在,你只有 10 只小白鼠和一星期的时间,如何检验出哪个瓶子里有毒药?解法
首先将这 1000 个瓶子进行编号:1 , 2 , 3 , 4 , 5 , 6 … 1000
然后将所有的小白鼠进行排列组合,组成一个 二进制 队列的形式:
- 0 代表不喝
- 1 代表喝
比如:
0000000001 代表第 1 瓶水被喝情况
0000000010 代表第 2 瓶水被喝情况
0000000011 代表第 3 瓶水被喝情况
0000000100 代表第 4 瓶水被喝情况
。
。
。
1111101000 代表第 1000 瓶水被喝情况
二进制小老鼠
全部 和瓶子经过这样的安排后,经过一个星期,观察这些小白鼠的存活情况。
队列中死亡的小白鼠记为 1 ,无反应的小白鼠记为 0,将该队列的二进制转为为十进制就是毒药的标号。
比如第 3 只小白鼠死亡,其他小白鼠没死,队列记为 0000000100,转换为 10 机制,表示第 4 瓶水有毒。
比如第 1 ,5 ,6 ,8 小白鼠死亡,队列记为 0010110001,表明是第 177 瓶水有毒。
延伸
下面这道是我面试某大厂第 4 面的题目,我当时并没回答好,感兴趣的小伙伴可以想一想最优解是什么。
有一个小国家,以生产高级葡萄酒闻名,全国的经济命脉也全依仗葡萄酒出口贸易。
某一年,另一大国向这小国下了 1024 瓶最高级红酒的订单,并预付了丰厚的定金。假如交易成功并获得好评,类似生意将滚滚而来,会为全国人民带来很多年富足的生活。于是全国人民同心协力,终于耗尽那一季的所有资源制成了 1026 瓶质量超高的名贵红酒,其中两瓶送交国家博物馆留为纪念,余下1024瓶准备付运。
但是,有一个对这国家极度憎恨的恐怖分子为了破坏这宗交易,不惜偷偷混入生产运输团队中,并在 1024 瓶酒中的其中两瓶酒内下了强力的生化毒药。此毒药药性强烈,只需极少份量(约0.01毫升)便可置人于死,但如混酒饮下则中毒者 24 小时内并无异样,但 24 小时过后的 15 分钟内会立即七孔流血暴毙。
在 1024 瓶酒要运上飞机的 26 小时前,恐怖分子的身份和计划都曝光了,但是因为他及时自杀了,官员们只确定了他在其中两瓶酒里下了生化毒药及其药性,但完全不知道是哪两瓶。
这时全国陷入一片恐慌,假若不把 1024 瓶酒及时运送到目的地,哪怕是少了一瓶,都作违约论,国家要赔偿巨额的违约金,财政上会出现严重赤字,未来好几年的人民生计将会非常艰辛。但是假若把有剧毒的酒售卖出口并造成人命伤亡,将会对全国赖以为生的葡萄酒出产业造成无可挽救的声誉伤害,以后也休想做其他国家的生意了。
就在这危急关头,监狱里有 65 名快将行刑的死囚站了出来,为了他们的亲人和朋友,决定自告奋勇,以身试毒,望能挽回这一笔对全国人民至关重要的生意。国家为了犒赏他们,不论试毒结果生死都会给与其家人一笔优厚奖金。
时间还有 25 小时多一点,官员们已经聚集了全国很多熟手包装工人,花了大半小时把 1024 瓶红酒拆装,从每瓶酒内提取了数毫升份量作试毒用途,然后又把它们全部重新包装。
现在距离最后时限还有 24 小时 30 分钟,65 名自愿试毒的死囚和 1024 杯可能有毒的酒(每杯上都有标贴对照其相应的酒瓶号码)已经准备好了,现在只欠一个完善有系统的试毒程序来解决这难题……