猜数游戏

zed

在http://topic.csdn.net/u/20080926 ... 8-4885a0f86f9a.html 有一个猜数字游戏：

猜数游戏如下：
人随意想一个四位数，四位数两两不相同，首位可为0，由计算机猜。
猜的步骤如下：
计算机给出一个四位数，人来回答这计算机的四位数中，有多少个是数字猜对，且位置也猜对的，有多少个是数字猜对，但位置为未猜对的。多次重复此步骤，直至计算机猜对为止。
例如：人产生的四位数为：1234，计算机第一次猜2534，这时人应给出回答：有2个数字猜对了，且位置也对（3和4），有1个数字猜对了，但位置不对（2），简记为2A1B。（A表示数字对且位置对，B表示数字对但位置不对）。第二次计算机猜2789，这时人应回答0A1B（因为没有一个数字是数字对且位置也对，所以写0A，数字2猜对但位置不对，写作1B）。直至计算机猜中1234.

我们可以有下面等一系列问题：
i)计算机该如何猜测使得最差情况的猜测次数最小,这个最小次数是多少？
ii)计算机如何猜测使得4次以内能够猜出正确答案的概率最大，这个概率是多少？
iii)计算机如何猜测使得5次以内能够猜出正确答案的概率最大，这个概率是多少？
iv)计算机如何猜测使得平均猜测次数最少，这个平均值是多少？

sunwukong

下面的这个链接，已求出平均猜测次数最小的最优搜索树

http://www.javaworld.com.tw/jute ... amp;tpg=1&age=0


1 次猜中次数：  1
2 次猜中次数：  7
3 次猜中次数：  62
4 次猜中次数： 691
5 次猜中次数：2444
6 次猜中次数：1756
7 次猜中次数：  79

总猜测次数：    26274
平均猜测次数： 5.213095

由此可以回答最后一个问题：

iv)计算机如何猜测使得平均猜测次数最少，这个平均值是多少

平均值 = 26274 / 5040 = 5.213095



另外，这个链接也解决了第一个问题：

i)计算机该如何猜测使得最差情况的猜测次数最小,这个最小次数是多少？

答案： 7

无心人

想起来某个泡菜网络游戏中的小游戏
就是这个
不过对手的位置交换了

shshsh_0510

上边的链接中，讨论的很精彩，但那个最小次数7应该不对

〇〇

bookmark

qianyb

先收藏，等有空时弄一个看看

keeya0416

围观 学习
题目都很有意思啊
就是我没说话的份了  哎
努力学习了