找毒药问题

发布时间 2023-09-11 23:52:42作者: WW爆米花

找毒药问题

题意:

1000瓶药水,有一瓶有毒,小老鼠喝下去之后会在1小时死亡。问给你一小时你需要多少只老鼠
才能检测出那瓶是毒药?

分析:

先常规考虑,最简单要1000只,因为这样我们可以一一对应知道哪一瓶是毒药。

考虑十进制数的二进制表示也是唯一的。
让一只小鼠表示一个数位,那么所需小鼠数量可大幅减少,2^10=1024>1000。

设毒药二进制表示为0001011010

让第一只小鼠喝下最高位为0的所有药水,
若小鼠死亡,那么答案最高位为0,
若小鼠活着,那么答案最高位为1(因为小鼠只有两种状态)
比如这个例子,第一只小鼠会死,因为毒药的最高位是0

10只小鼠喝完后,那么我们就确定了唯一的数,
将它转化成十进制数即得到毒药编号。

变式

问题:

100瓶药水,有一瓶有毒,小老鼠喝下去之后会在1小时死亡。假设现在给你两个小时你需要至少需要多少只老鼠能检测出那瓶是毒药?

分析

此时老鼠有三种状态:死、生死、生生
(1小时后若老鼠死亡,则死亡老鼠没有后续情况,
若1小时后小鼠活着,则2小时后有可能还活着或死亡)

确定每一只小鼠的最终状态,并唯一表示出来。
例如,原题0、1状态表示小鼠生、死

用三进制0、1、2表示小鼠在1小时后死亡,在2小时后死亡和不死。

例如毒药三进制表示12002

给第一只小鼠喝下所有最高位为0的药水,若小鼠死亡,则答案最高位为0,
若不死,则让其喝下最高位为1的药水,若小鼠死亡,则答案最高位为1,
若还活着,则答案最高位为2.

5只老鼠后将答案转化为10进制数即为编号。