计算机科学导论实验报告_给鼠问题探索
中国科学院大学计算机科学入门课程实验报告
关于国科大2014级计算机第六组算法实验的报告
第一题
规则：2老鼠1毒瓶，你可以给老鼠1和一些瓶子。 老鼠在喝毒瓶的时候会站起来
也就是说是死。
目标：以最小限度的步骤进行。
请求：
唯一的毒瓶试图找到最少的步骤。 如果你的战略涵盖所有情况，你就会赢
否则，你就输了。 最好的结果就是统计。
你和你的伙伴一共提出三次机会
问题分析：这是一个与游戏相关的问题。 电脑的目的是让你的步骤
尽可能多，你的目的是尽量少走步骤。 有纳什
均衡问题。 我们考虑子博弈，精炼纳什均衡，让参与者随时做出决策
一切都是最好的，决策者必须“随机应变”、“积极向上”，而不是固守旧的
有点。 这有一个动态问题。 值得注意的是，必须给老人喝毒瓶
老鼠，老鼠死了，游戏结束了。 问题的初解：表示构造函数f(n，m )在
老鼠为n个、瓶子为m个时所需的最低步数。 如果是两只老鼠，是假的
假设你第一次给老鼠k个瓶子。 此时，计算机有两种选择。 老鼠会死吗
人不会死。 如果老鼠不死，剩下的两只老鼠和(m-k )个瓶子，其次
f(2，) m-k () ) ) ) ) ) ) ) ) ) ) )的步骤检测毒鼠强。 要这样做，(1f ) 2，(m-k ) ) )
舞步。 如果老鼠死亡，这样的毒瓶一定在k个瓶子里，一共需要(1 k )
步，这样电脑和你玩游戏，他会选择max((1f ) ) 2，() m-k ) )，(1 k ) )
All rights reserved .转载引用请注明出处。
中国科学院大学计算机科学入门课程实验报告
的事件发生，我们和电脑玩游戏时，我们需要选择min{max}(1f ) 2。
发生了(m-k )、(1 k ) }的事件。
对问题初解的评价：既是最直接的想法，也是最困难的想法。 如果可以的话
如果是编程的话，只要编写一个程序，这个问题就会完全扩散到n只老鼠身上，m
瓶子所需的最低步骤数。 nm的情况下，显然需要m步。 时光流逝
n
(k ) )就可以了。 但是我们小组对编程没有满足那样的要求，所以我们在寻找别的想法。
最终答案：
基本思想：博弈论，从特殊到一般，归纳法
下表是1到29个瓶子的数量，对于2只老鼠，是最佳的步骤数。 计算时
的技巧这里只展示了在有8瓶的情况下，如何求出最佳的步骤数。 剩下的都一样。
被老鼠拿走一根的时候，不能死。 7条最佳值加1，5步。老鼠取2条，
死，三步，活，六条最佳值加一五步； 像这样按下去的话……
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瓶
我来数
56666777最好
步骤
我来数
21 22 23 24 25 26 2