猜数游戏算法代码

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《猜数游戏算法代码》，欢迎阅读！

1 2005-06-08, 15:13 【讨论】一个有趣的小游戏

--------------------------------------------------------------------------------

文曲星上的经典猜数游戏，电脑随机出一个四位数（没有重复数字）让你来猜，每次你说出猜的数后，返回信息告诉你有几个数位置对了数字也对了，有几个数数字对了但位置不对。比方说原数是5678,你猜了一个3658，那么返回2A 1B,表示有两个数（6和8）位置和数字都对了，还有一个数（5）对了但位置不对。当最后返回4A 0B时表示你猜中了这个数。

在我们学校的BBS上有这个，做成了一个赌博游戏，1次猜出赢100倍，2次猜出赢50倍，3次赢20倍，4次赢5倍，5次赢3倍，6次不输不赢，6次以上的就会把押的钱输掉。我们ACM队里的闲着没事在研究怎么写一个程序帮人来猜数，能挣到更多的钱。

我的初步想法是第一次猜0123，然后根据返回值，去掉不符合条件的数，再在所有符合条件的数里面猜最小的，直到猜出来为止。后来做了一些改进，不是在所有符合条件的数里猜最小的，而是把所有可猜的数都试一遍，看猜哪个数时能去掉更多的数，就选这个数来猜，算法慢了一些 O(N^2) ，但结果更好了一些。

下面我的程序的统计结果：（四位不重复的数共5040个）

1次 1 2次 13 3次 108 4次 619 5次 2004 6次 1932 7次 360 8次 3

失败的概率是0.07，平均期望大概是2.6左右，也就是说用这个程序去玩，能赢回2.6倍的钱。

还有一位也写了一个程序（算法我记不太清了），结果是：

1 次 1 2 次 4 3 次 44 4 次 459 5 次 2375 6 次 2048 7 次 108 8 次 1

这个算法虽然失败概率很低，只有0.02，但大部分的数都集中在6上，平均期望只有2.0左右。




请大家可以想想还有没有更好的办法，我听说有人用哈夫曼树可以保证在6步之内猜到，不知道是怎么做的。

本文来源：https://www.wddqxz.cn/83d846c06529647d2628521b.html