1.老鼠试毒问题
此题有三种方式,第一种是给定老鼠和试毒药剂数量,问如何找到毒药,第二种是给定药剂数量,问最少需要多少只老鼠就可以试出毒药;第三种是给定老鼠数量,问最多能试出多少瓶毒药。这里以第一种方式来问问题。
问:有1000瓶药剂和10只老鼠,药剂中有1瓶毒药,喝了一周内死亡(有的题目改成了五分钟,五分钟真亏他能喂完),如何在一周内找到这瓶毒药。
答:将这1000瓶药剂编号0~999,并转换为二进制 就是0000000001~1111101000,从右向左开始,让第一只老鼠喝所有右起第一位编号为1的药剂,第二只老鼠喝所有右起第二位编号为1的药剂,依次类推,10只老鼠喝完10位的药剂,一周后,如果第一只老鼠死亡,那么毒药的从右起第一位为1,未死亡的话就为0,所以根据死亡状态就可以知道该瓶毒药的二进制。
例如状态是:死亡,存活,死亡,存活,存活,存活,死亡,存活,死亡,存活 = 010111010=186
从上面例子就可以知道第二种和第三种问题的解法了吧
扩展:
假如测试时间提升到两周,那么测试特定数量的药剂需要的老鼠数量是多少?
测试时间提升为两周就说明第一周测试不死的老鼠可以拿来继续第二周的测试 ,所以老鼠的状态就变成了三种:存活(未实验),死亡,实验后存活。
将全部药剂编号后转为三进制数,老鼠右起依次喝0编号的药剂,如果死亡,那么该位编号为0,如果未死亡,那么可能为1和2,第二周把存活的老鼠继续喝该位1编号的药剂,如果死亡就为1,存活就为2,这样就找到了毒药的三进制编号,然后转换成下标即可。
总结:有 n 只小白鼠 m周的时间可以从 (m+1)^n 个瓶子中检验出毒药来。