求猜数字问题的数学证明!!!!
猜数字问题这里讨论过很多次,我也用筛法变了个程序,一般计算机5,6次就可以猜出来(不重复的四位数).
所以我现在更感兴趣他的数学证明,我试着证了一下,发现咋看挺简单的问题实际上,证明起来挺困难,据说可以证明四部之内一定可以猜出来,谁有数学证明!??
谢了先!
问题点数：100、回复次数：23Top
1 楼jlandzpa（jlandzpa）回复于 2002-04-14 19:59:22 得分 0
猜数字问题是什么问题?Top
2 楼Kusk（Kusk）回复于 2002-04-14 21:26:01 得分 0
构造最坏的情况，证明它为四步。Top
3 楼gzpbx（郭半仙）回复于 2002-04-14 22:02:59 得分 0
猜数字问题都不知道？即类似文曲星上的游戏（不过，我现在讨论的问题是人机角色对换的）
4个数字.你猜一次之后,它会给出提示:xAyB.A表示位置和值都对,x表示这样的数字的个数;B表示你猜的数字答案中有但是位置不对,y表示这样的数字的个数.
例如,假设答案是1234,当我猜1243时,提示为:2A2B;猜1678,提示为:1A0B;猜4321,提示为:0A4B;猜5678,提示为:0A0B.
Top
4 楼zhoudi2000（不怕输）回复于 2002-04-14 23:59:26 得分 0
四步是解不出来的，我们先假设这个数是4321，如果我们第一次猜7890，得的结果会是0A0B，这时只有123456可能选择，下一步如果猜3456，得的结果是0A2B，我们可知，12是其中的两个数，剩下的就要从3456中选择了，如果我们继续猜5612，不幸又得了一个结果是0A2B，到这步，我们只猜出了这四个数是多少，可是位置一个也没中，这四个数的排法共有4*3*2*1=24种，我们只能排除3412一种。这就是最坏的情况。Top
5 楼gzpbx（郭半仙）回复于 2002-04-15 09:34:31 得分 0
各位大哥这个问题不是那么简单的，我现在已经可以编程证明至多八次之内一定可以猜出来，但我现在无法在进一步减小次数，谁能？Top
6 楼down2（down2）回复于 2002-04-17 18:44:53 得分 10
我也认为 4 步之内不可能，有 7 步之内出结果的程序：
http://llf.my.west163.com/studio/ComGuess3.rar
不过据说 6 步可以完成，不知道谁有这样的程序？Top
7 楼Elminster（）回复于 2002-04-17 19:56:57 得分 10
这个问题能否从信息量和熵的角度来考虑？首先考虑完全随机的四个数的排列带有多少信息，然后每次猜测最少能够得到多少信息？Top
8 楼starfish（海星）回复于 2002-04-19 14:27:39 得分 0
4步是不可能的，除非运气特别好
从信息论的角度看
最多只需要6步，就可以猜出来Top
9 楼down2（down2）回复于 2002-04-19 23:31:26 得分 10
请问“从信息论的角度看最多只需要6步”是怎么推出来的呢？
有没有这样的程序？我找到的这一类问题的程序都是只能在 8 步之内猜出的。
或者，这个问题本身就是“信息论”的一个例题？ :)Top
10 楼down2（down2）回复于 2002-04-20 23:39:34 得分 10
请教“Elminster()”和“starfish(海星)”两位大侠，关于猜数字信息量的问题。
因为开始，这一个数是 5040 中任何一个数的可能性都是 1/5040，所以熵应该是 12.2992080183867；
而第一次猜测之后，尚未评分之前，有 14 种可能性：
4A0B：1
2A2B：6
1A3B：8
0A4B：9
3A0B：24
2A1B：72
0A0B：360
2A0B：180
1A2B：216
0A3B：264
1A0B：480
1A1B：720
0A2B：1260
0A1B：1440
所以第一步猜测所携带的熵为 2.77115216575502；
如果评分是 0A1B 的话，则有 1440 种可能性，现在的熵应该是 10.4918530963298；
不过 12.2992080183867 - 2.77115216575502 = 9.52805585263168 ，
这其中相差的 10.4918530963298 - 9.52805585263168 = 0.96379724369812 该怎么解释呢？
如果是因为它们不属于完全独立的两个实验的话，则用 12.2992080183867 / 2.77115216575502 = 4.4
而求出的总共需要 6 步就可以猜出来的结论不也就失效了吗？
Top
11 楼steedhorse（晨星）回复于 2002-06-03 23:15:15 得分 0
高手就是高手，一点办法都没有，:(Top
12 楼leopro（漫漫人生路，与你同行）回复于 2002-06-04 00:40:53 得分 0
我用大脑猜，七步之内，百发百中：）
但要形成算法，还真不容易Top
13 楼makefriend7（小顽童）回复于 2002-06-04 17:22:14 得分 0
我也是，感觉7步要技巧，8步就容易多了。Top
14 楼Xcoder（流浪狗）回复于 2002-06-05 14:44:58 得分 0
这其实是一个很难的问题，先正规表述一下，应该是：存在一个算法，使得对任意可能的数字组合，能再n步内猜出来，求n的最小值。
Top
15 楼Xcoder（流浪狗）回复于 2002-06-05 14:56:24 得分 10
接上文，
现在是要求N的最小值，不是证明。想到信息论是很自然的，但这里确有一个很重要的问题:每一部猜测所能得到的信息是和所采用的算法相关的!
举个极端的例子，某步猜0123得到2A2B，得到很多信息吗？如果我告诉你，之前已有一步猜0123，则这步实际得到的信息为0。
所以要解决这个问题，首先应该找到一个猜测的算法，然后证明这个算法是在步数上最优的算法，在找出这个步数。
Top
16 楼down2（down2）回复于 2002-06-09 13:33:35 得分 20
Xcoder 兄说的有道理。不过如何证明一个算法是“在步数上最优的算法”，恐怕也是很困难的。反过来说，如果可以证明某个算法是“在步数上最优的算法”，大概也可以根据这种证明的方法来构造出一种在步数上最优的算法吧。
使用信息论的算法我试过了，结果如下：
共进行了 5040 次猜测
1 次就猜中的有 1 次
2 次就猜中的有 4 次
3 次就猜中的有 44 次
4 次就猜中的有 459 次
5 次就猜中的有 2375 次
6 次就猜中的有 2048 次
7 次就猜中的有 108 次
8 次就猜中的有 1 次
9 次就猜中的有 0 次
10 次就猜中的有 0 次
而另外那种“真正完全统计”的算法，结果如下：
共进行了 5040 次猜测
1 次就猜中的有 1 次
2 次就猜中的有 2 次
3 次就猜中的有 30 次
4 次就猜中的有 377 次
5 次就猜中的有 2124 次
6 次就猜中的有 2315 次
7 次就猜中的有 191 次
8 次就猜中的有 0 次
9 次就猜中的有 0 次
10 次就猜中的有 0 次
我想也许是因为携带信息量的大小并不是决定最小步数的关键吧，因为虽然使用熵的算法并没有做到最大猜测次数最小，但是的确做到了总猜测次数最少。Top
17 楼down2（down2）回复于 2002-06-09 13:42:52 得分 10
我想，也许使用一种野蛮的办法可以做到吧：每一步都进行一次全面的深搜，找到使所有可能情况的最大猜测次数最小的那个猜法……
不过这种算法真的会非常慢，可能都是无法想象的。Top
18 楼school（求学）回复于 2002-06-10 20:19:25 得分 10
我目前最快用5步猜出。Top
19 楼school（求学）回复于 2002-06-10 20:22:29 得分 10
第3步可得大量信息，将数字组合的可能性缩小为4种。Top
20 楼down2（down2）回复于 2002-06-13 19:13:21 得分 0
school 兄有程序么？我很想看一看。是否有源代码都可以。Top
21 楼gzpbx（郭半仙）回复于 2002-07-11 22:04:51 得分 0
rtTop
22 楼quicmous（快鼠）回复于 2002-07-12 11:40:53 得分 0
呵呵，争来争去的，有人对源代码赶兴趣吗？Top
23 楼down2（down2）回复于 2002-09-03 15:28:52 得分 0
关于“猜数字”算法“5 步不能”的证明（不完美篇）……
熵电脑猜数字
共进行了 5040 次猜测
1 次就猜中的有 1 次
2 次就猜中的有 4 次
3 次就猜中的有 44 次
4 次就猜中的有 459 次
5 次就猜中的有 2375 次
6 次就猜中的有 2048 次
7 次就猜中的有 108 次
8 次就猜中的有 1 次
9 次就猜中的有 0 次
10 次就猜中的有 0 次
1、基于“熵电脑猜数字”的每一步都是选取的可取的信息量最大的方式进行的猜测，所以这种方式必定是使总猜测次数最少的方法。其总次数为 1 + 2*4 + 3*44 + 4*459 + 5*2375 + 6*2048 + 7*108 + 8 = 26904 ，也就是说任何一种算法都不可能得到最猜测次数少于此数的结果。（这一步证明似乎缺少一些中间环节，所以称之为“不完美”）
2、假设有一种算法 5 步之内可以得到结果，则其总猜测次数最少为 5040 次，最多为 5040*5 = 25200 次，因为即使其最多总猜测次数也未达到 26904 ，而 26904 是总猜测次数的最小值，所以这种假设的算法不可能存在，也就是说任何算法都无法在 5 步之内得到结果。
Top
