算法思考题-三只老鼠找8瓶毒药思路(个人思考+收集)

有8瓶药,其中只有一瓶是毒药,我们有三只老鼠,能被毒药很快毒死。请问最少几次能把毒药试出来?

这类题目,首先要明确的是,一只老鼠可以同时喝不止一瓶药水,否则就只能一瓶一瓶的试下去了。明确了这件事,问题就变成了三只老鼠分别喝了几瓶药水之后,有多少种状态的问题,三只老鼠每一只都对应着死或者不死两种状态,而且是独立的,总的状态是2的3次方等于8。这道题中,药水的数量正好是8。

1,二分法

第一步:将8瓶药对半分,将其中的一半,也就是4瓶分别倒出一点,混合后喂小白鼠。小白鼠亡,说明毒药就在这4瓶里面。没死,说明毒药在另外的4瓶里面。这里我们假定小白鼠一命呜呼了。

第二步:将那4瓶药剂对半分,将其中的一半,也就是两瓶混合后喂第二只小白鼠。第二只小白鼠亡,说明毒药就在这两瓶里面的其中一瓶。没死,说明毒药在另外的2瓶里面。这里我们假定小白鼠也一命呜呼。

第三步:有嫌疑的那两瓶药剂,将其中一瓶倒出一点喂最后一只老鼠,亡,这瓶有毒药,没亡,另一瓶有毒药。

备注:采用此法,最多牺牲3只小白鼠就能找到答案。运气最好时,就是每一次试验,小白鼠都没死,此时,一只小白鼠都不用牺牲。不是最优。

2.

由于老鼠有两种状态生或死
对毒药瓶编号
利用集合的交与差和并的逻辑关系,故意设置好对应的条件,三个老鼠都活下来就是1号。
a鼠喝5678,b鼠喝3478,c鼠喝2468。

3

二进制

让3只小白鼠列队站成一线。将8瓶药,按照0到7一一标出来。
为什么要这么标,因为一个3位的二进制能表示出8种状态,转换为十进制的话就是0到7。

二进制十进制

000 0

001 1

010 2

011 3

100 4

101 5

110 6

111 7

到这里,很多人就清楚了,3只小白鼠,可以当成一个3位的二进制。
  现在,我要把编号为1、3、5、7的药剂分别倒出一点,混合后给小灰喝。”生物学家说,“接着,我把编号为2、3、6、7中的药剂分别倒出一点,混合后给小白喝。最后,我把编号为4、5、6、7中的药剂分别倒出一点,混合后给小棕喝。

综上所述,方案2最优

原文地址:https://www.cnblogs.com/AmosAlbert/p/12832269.html