最近一个朋友在用计算机模拟人來玩文曲星上的
也邀我一起讨论。我以前没有玩过不过发现这个还是蛮有趣的,于是也想写一个能猜数据的小程序
通过几日思考,終于实现了一个稍微有点聪明的以下是C++代码()。
首先函数头的定义部分其中一个重要的数据结构是各个排列之间的关系矩阵。
判断兩个排列之间关系的函数:
为了方便这里有一些打印信息的函数:
便于扩展,使用抽象类以下是裁判与玩家双方的接口:
现在让玩家玩一次游戏,直到猜成功:
有了裁判还要找一个玩家。我们先找一个头脑简单点的玩家:
用Factory工厂制造裁判和玩家(哈哈批量生产):
雖然头脑简单,但是还都能猜出来只是次数多了点。
好了现在整个框架搭起来了。现在的任务是寻找更聪明的玩家让猜测次数降下來。
还真找到了一个贪婪的玩家(算法原理见代码注释)且叫他 Clever1Player 吧:
好了,Clever1Player 也来玩了看看他的成绩:
成绩还不错,不过最差情况下要猜8次嘛
有人说最多7次就可以猜出来,我们再找找
不错,果然在7次之内都能猜出来只是为什么平均成绩还不如 Clever1Player 呢?
这个问题我得找時间问问他。
我曾经做过优化即使用一个数组保存可行排列序号,这样在 Clever1Player 的 36 和 45 行就只需要扫描数组而不需要每次都扫描 M 次了。当然总嘚时间复杂度依然是 (M^2)
假设正确结果是 0124
但是Clever2Player 则有可能会猜 4567 得到 0A1B,直观上说猜测范围就缩小到 中了,搜索空间减小很多实际上我们人脑使用逻辑推理的时候通常就是这么考虑的,而且我们肯定是不会使用这种搜索算法的
至于逻辑推理法与搜索法之间有什么联系,我也不清楚
另外,该算法的关注点在于猜测次数即在于效果而不是效率。所以为了使算法看起来清晰我没有过多优化。
但是我没有编程实現因为担心复杂度太高运行不完。
而贪心算法得到的应当不是最优解但是近似最优解,而且从次数和执行效率上来说都是可以接受的
一边是聪明的玩家,一边是狡猾的裁判哈哈,有好戏看了
究竟鹿死谁手,请听下回分解
最后感谢,让我有机会接触这么好玩的游戲
90年代电子词典文曲星上的怀旧经典推理小游戏需要猜测4个数字及其排列顺序,一共有10次机会若猜不对会提示[?A?B] ?A数字和位置都正确的个数,B代表数字正确但位置不正确的個数
例如正确答案1234,若猜测 1354的话会返回2A1B,因为"1","4"数值和位置正确,"3"数值正确位置不正确
根据热心网友的反馈修改了生成随机数字的算法,4个数字不重复