计算机科学导论实验报告_老鼠喂药问题探索
中国科学院大学 计算机科学导论 课程实验报告
国科大级计算机第六组关于算法实验的报告
第一题
规则:2小鼠1毒瓶,你可以喂老鼠1与一些瓶子。老鼠喝毒瓶时将立
即死亡。
目标:用最少的步骤。
要求:
试图找到唯一的毒瓶最少的步骤。如果你的策略涵盖所有情况,你赢
了,否则,你输了。最好的结果将是统计。
你和你的伙伴将一共有3次机会提交
问题分析：这是一个与博弈有关的问题。电脑的目的在于使你的步骤
尽可能地多，而你的目的是使步骤尽可能的少。这样就存在一个纳什
均衡问题。我们考虑子博弈精炼纳什均衡，使参与者的决策在任何时
点上都是最优的，决策者要 “随机应变”，“向前看”，而不是固守旧
略。这样就有一个动态的问题。值得注意的是，必须将毒药瓶喂给老
鼠，老鼠死亡，游戏才结束。问题初解：构造函数F (n,m)表示在有
n个老鼠，m个瓶子时所需要的最少步数。对于两只老鼠的情况，假
设第一次把k个瓶子为给老鼠一，此时电脑有两种选择，老鼠一死或
者不死。若老鼠一不死，则剩余2只老鼠和 (m-k)个瓶子，接下来
会需要F(2，(m-k))步骤检测出毒老鼠。这样一共需要(1+F(2，(m-k)))
步。若老鼠死亡，这样毒药瓶一定在k个瓶子中，一共需要 (1+k)
步，这样电脑与你博弈，他会选择max{(1+F (2，(m-k))),(1+k)}
All rights reserved. 转载引用请注明出处。
中国科学院大学 计算机科学导论 课程实验报告
的事件发生，而我们与电脑博弈，我们则需要选择min{max{(1+F (2，
(m-k))),(1+k)}}的事件发生。
对问题初解的评价：是最直接的想法，也是最有难度的想法。如果会
编程的话，只要编一个程序，这个问题完全可以推广到n个老鼠，m
个瓶子时所需要的最少步数。当n>m 时，显然，需要m步即可。当
n
k)}}即可。但我们组对编程没达到那种要求，所以我们另寻思路。
最终解答：
·基本思想：博弈论，由特殊到一般，归纳法
下面的表格为1到29个瓶子数，2个老鼠时，最优步骤数。计算时
的技巧这里仅给出当8个瓶子时，如何求解最优步骤数。其余同理。
当取1瓶给老鼠，不可能死，为7瓶最优值加1,5步；取2瓶给老鼠，
死，3步，活，为六瓶最优值加1,5步；如此地推下去……
1 2 3 4 5 6 7 8 9 10 瓶子
All rights reserved. 转载引用请注明出处。
中国科学院大学 计算机科学导论 课程实验报告
数
1 2 3 3 4 4 4 5 5 5 最优
步骤
数
11 12 13 14 15 16 17 18 19 20 瓶子
数
5 6 6 6 6 6 7 7 7 7 最优
步骤
数
21 22 23 24 25 26 2
