【春节特辑】神奇的二进制

问题一

有 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 杯可能有毒的酒(每杯上都有标贴对照其相应的酒瓶号码)已经准备好了,现在只欠一个完善有系统的试毒程序来解决这难题……

有奖红包问题

【春节特辑】神奇的二进制
2019的二进制是多少

我用马赛克遮挡了口令的数字,只需要将答案数字填入进去即可获取红包。

红包数量有限,先到先得:)

掏空小吴

【春节特辑】神奇的二进制

 / 今日问题 / 


今天是大年初二,你出门去玩耍了么?



【春节特辑】神奇的二进制

欢迎关注这个会做动画的程序员👆

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 【春节特辑】神奇的二进制

我还会在以下平台发布内容

GitHub 哔哩哔哩