求猜数字游戏的策略

Question

猜数字游戏介绍：
电脑随机产生一个数字不重复的四位数。电脑会将您提交的数与它自动产生的数进行比较，结果显示成"*A*B"。A代表位置正确数字也正确，B代表数字正确但位置不正确，比如："2A2B"表示您有2个数字的位置正确且数值也正确，除此以外，您还猜对了2个数字，但位置不对。

问：在最坏情况下最少几次猜中，策略如何？

另外，如果是二人游戏，即一人猜，一人给出*A*B，且数字可以变动（但必须符合先前给出的*A*B），问出题人采用怎样的策略能让对手不易猜中

貌似两个问题等价 =。=
不管了，答得好有加分
请给出详细的严谨的策略和分析，谢谢

请8楼给出具体策略

to9楼:我需要完整的严谨的最佳策略，无论多烦，只求最佳，并且请你注意审题

Answer 1

你好！

先来一个比较简单的
第一步先猜0001，2223，4445，6667，8889。既可判断是那四个数比如1、3、5、0
第二步选一个没有出现的数比如9，将它与前面四个中的一个组合，判断其位置
比如1999，9199，9919可判断1（前三个都不是就是第四个，下同）
第二个数需两次，第三个需一次，剩下的是最后一个
这样，最坏的情况只需11次，有点多，最大的优点是不需要动脑子

关于上述策略的改进
在第二步用两个确定出现的数，比如0和1，以0001的方式输入，有以下3种情况：
1A3B，0和1一定都不在第四位(因为这“1A”一定是0，如果是1，则0一定在前三位，会有2A，故1不在第四位，同样因为“1A”是0，0也不是第四位。)，这样剩下两个数一定有一个在第四位，剩下两个数，比如2、3，以2232的方式输入，如果3是第三位，则会显示2A2B，否则是4B，这样三四两位就定下来了，再猜一次可以确定一二两位的顺序，9次一定可以猜对
2A2B，1一定是第四位，0一定不是第四位
4B，0一定是第四位，1一定不是第四位
上面两种情况是等价的，第一次就可以确定一个数的位置，假设第四位是1，下一次猜0021，结果可能是3A1B，则结果是0321或3021，只需要再猜一次；或者2A2B，这是两个0里一定有一个是对的，2一定是错的，所以第三位一定是3，结果是2031或0231，也只需要再猜一次；或者1A3B，这时0一定在第三位，结果是2301或3201，仍然只需要再猜一次
综上所述，这种策略下，最坏的情况需要9次

进一步提高效率需要对各次的结果进行综合，情况太多了，失去作为一种策略的意义
这个问题,研究一下的确蛮有意思,下面是我的想法,不一定能解决问题,看可能可以给别人以启发.我主要研究的是<在最坏情况下最少几次猜中，策略如何？>
第一步,因为各个数都是一样的,所以第一次输入0123,现在轮到出题者,我相信没人会给他A,顶多给他B,但是给他几个B合理呢?
0B,下次猜到B的期望E=4*4/6=8/3
1B,E=1*1/4+3*3/6=7/4
2B,E=2*2/4+2*2/6=5/3
3B,E=3*3/4+1*1/6=29/12
4B,E=4作为出题人,希望对手猜对B的期望为最小,所以,选择给他2B.
第二步,输入4501,再次轮到出题者,现在问题开始复杂了.
我觉得可以把4501分为两部分,45和01,其中45是新的,按上题的方法继续做,
0B,E=2*2/4=1;
1B,E=1*1/2+1*1/4=3/4;
2B,E=2*2/2=2;所以出题者会在45中给1B.
其实复杂的是01部分,因为他涉及到A的部分,我只能假设,出题人在不得不给A时才给A这种情况,如果算期望的话,我已经搞不清了,所以从简了，而且这假设我觉得不一定不合理.从给B部分,我们可以同样按照开始的思路
0B,E=2*2/2=2
1B,E=1*1/2+1*1/2=1
2B,E=2*2/2=2
所以01中会给一个B,现在猜题者知道的东西有0,1中有1个;2,3中有一个;4,5中有一个;6,7,8,9中有一个.综上,第2步,出题者给的是0A2B.
第三步,猜题者这一步,稍微聪明点,从4组数中分别去4个数,最起码可以确定,3个数字.但是我们想,作为出题人,在6,7,8,9中,如果是一个数一个数猜,他肯定,会将最后一次猜的设为正确的以增加你猜题次数,也就是说,即使你从现在起,4步后,将6,7,8,9中正确数字的位置确定下来,也需要4步才能,将4个数字都确定.所以这种假设下,最少需要猜加上前面的两步,共6步.如果第三步猜2046.
出题人可以不给A就不给A的前提下,理智出题者给的应该是,0A1B为什么给1B不给0B呢,如果给0B,那么,猜题人就知道前三组数字中1,3,5是必对了,除了在确定A是比3B有优势,其他地方没优势.而给1B而不给2B的原因也就在于,确定A的时候1B比2B更有优势(猜题者更难猜)这样对猜题者来说,是很麻烦的,因为,他不知道1B是哪个,这次作答几乎对确定B没有任何贡献,所以,猜题者不应该出这些数字.如果前三组数字只出现1个,那么不仅可以唯一确定这个数字所在组的B,而且对6,7,8,9中选B也有积极意义
现在总猜题情况为0123,4501所以第三步,出6078.
问题越来越复杂了,对于0可以给B也可以不给,对于6,7,8可以给B也可以不给,0B,1,9肯定是B;2B,1肯定是B,而且6,7,8之间肯定有B,但如果给1B,猜题折还需要猜测,这个B来自哪里,增加了猜题难度,所以出题者给0A1B.
第四步,现在总猜题情况为0123,4501,6078.后面在像前面一样分析,我已经吃不消了,我就说我的猜题策略吧.第四步7890
如果第三步中,B是0的话,那么,出题者该给答案1A1B
(沿着这个假设,往下,总猜题情况为0123,4501,6078,7890.现在知道的是0位置已经确定,9确定为B.第五步9240,如果9位置对了,那么,如果给2A0B那么结果必然是9350.如果给2A1B结果必然是9430,如果给3A0B,结果可能是9250和9340也需要两步,最不好的情况就是要7步;如果9位置没对,我相信,在两步也能解出来.)只考虑这中情况,出题人就可以将你的步数限制到最少7步
如果第三步中,B是6,7,8中的一个,那么,0肯定不是B了,1肯定是B,而出题者只用考虑B是在7,8中,还是6,很显然,出题者会让B在7,8中,所以给的答案是0A1B.总猜题情况为0123,4501,6078,7890
第五步8215,出题者0A2B
第六步5381,出题者
1A0B===>2741,
1A2B===>3751,5731
2A1B===>3481
3A0B===>4381.只有这四种情况,是由于受到前面的限制.这中结果也需要7步
我不保证自己证明的都很严密,但作为一个解题者,我的感觉是,解这个题目可以步数更少些(虽然我也不知道能不能再少),如果有人能以更少的步数解出,我也会崇拜之,但如果说解这题目要比七步多,我就不同意了,我是完全站在出题者的立场,为难猜题者的思路的假设下去,这也是最糟糕的情况,这也应该是步数最多的情况.

各位有高招欢迎指正~

你想玩可以用我的QuickBasic程序。

Randomize Timer '随机化
Cls '清屏
Dim a(4),b(4) '定义数组
10 a = Int(Rnd * 9000)+1000 '产生一个数
aa = a '替身变量
a$ = Mid$(Str$(a),2) '去首部空格
For i = 4 To 1 Step -1 '此循环截位
a(i) = a Mod 10
a = a \ 10
Next
For i = 1 To 3 ’此循环判断是否有数字重复
For j = i + 1 To 4
If a(i) = a(j) Then 10 '若有数字重复，重新产生
Next j, i
For i = 10 To 1 Step -1 '有十次机会
s = 0 '"A"次数清零
v = 0 '"B"次数清零
Print i '打印还剩几次机会
20 Input"Input a number ", b '输入你的数
If b = 0 Then Print "The answer is";aa: End '若直接敲回车显示答案，同时游戏结束
For j = 4 To 1 Step -1 '截位
b(j) = b mod 10
b = b \ 10
Next
For j = 1 To 3
For k = j + 1 To 4
If b(j) = b(k) Then 20 '若有数字重复，重新输入
Next k, j
For j = 1 To 4
If a(j) = b(j) Then s = s + 1 '若条件满足，"A"加1
Next
For j = 1 To 4 '找"B"的个数
b$ ＝ Mid$(Str$(b(j)), 2) '去首位的"0"
z = Instr(a$, b$) '寻找在你的数中和它的数相同的数字
If z <> 0 And a(z) <> b(z) Then v = v + 1 '找"B"
的个数
Next
If s = 4 Then Print "You are right!":End '如"A"＝4表明全对，结束游戏
Print s;"A";v;"B" '打印"A"以及"B"的个数
Next
Print "Sorry, you are lost!" '没猜出来，结束
End

若没有QB去www.iteroom.cn下载

谢谢！

Answer 2

首先强烈谴责"帝之魔王"的抄袭行为
这个问题,研究一下的确蛮有意思,下面是我的想法,不一定能解决问题,看可能可以给别人以启发.我主要研究的是<在最坏情况下最少几次猜中，策略如何？>
第一步,因为各个数都是一样的,所以第一次输入0123,现在轮到出题者,我相信没人会给他A,顶多给他B,但是给他几个B合理呢?
0B,下次猜到B的期望E=4*4/6=8/3
1B,E=1*1/4+3*3/6=7/4
2B,E=2*2/4+2*2/6=5/3
3B,E=3*3/4+1*1/6=29/12
4B,E=4作为出题人,希望对手猜对B的期望为最小,所以,选择给他2B.
第二步,输入4501,再次轮到出题者,现在问题开始复杂了.
我觉得可以把4501分为两部分,45和01,其中45是新的,按上题的方法继续做,
0B,E=2*2/4=1;
1B,E=1*1/2+1*1/4=3/4;
2B,E=2*2/2=2;所以出题者会在45中给1B.
其实复杂的是01部分,因为他涉及到A的部分,我只能假设,出题人在不得不给A时才给A这种情况,如果算期望的话,我已经搞不清了,所以从简了，而且这假设我觉得不一定不合理.从给B部分,我们可以同样按照开始的思路
0B,E=2*2/2=2
1B,E=1*1/2+1*1/2=1
2B,E=2*2/2=2
所以01中会给一个B,现在猜题者知道的东西有0,1中有1个;2,3中有一个;4,5中有一个;6,7,8,9中有一个.综上,第2步,出题者给的是0A2B.
第三步,猜题者这一步,稍微聪明点,从4组数中分别去4个数,最起码可以确定,3个数字.但是我们想,作为出题人,在6,7,8,9中,如果是一个数一个数猜,他肯定,会将最后一次猜的设为正确的以增加你猜题次数,也就是说,即使你从现在起,4步后,将6,7,8,9中正确数字的位置确定下来,也需要4步才能,将4个数字都确定.所以这种假设下,最少需要猜加上前面的两步,共6步.如果第三步猜2046.
出题人可以不给A就不给A的前提下,理智出题者给的应该是,0A1B为什么给1B不给0B呢,如果给0B,那么,猜题人就知道前三组数字中1,3,5是必对了,除了在确定A是比3B有优势,其他地方没优势.而给1B而不给2B的原因也就在于,确定A的时候1B比2B更有优势(猜题者更难猜)这样对猜题者来说,是很麻烦的,因为,他不知道1B是哪个,这次作答几乎对确定B没有任何贡献,所以,猜题者不应该出这些数字.如果前三组数字只出现1个,那么不仅可以唯一确定这个数字所在组的B,而且对6,7,8,9中选B也有积极意义
现在总猜题情况为0123,4501所以第三步,出6078.
问题越来越复杂了,对于0可以给B也可以不给,对于6,7,8可以给B也可以不给,0B,1,9肯定是B;2B,1肯定是B,而且6,7,8之间肯定有B,但如果给1B,猜题折还需要猜测,这个B来自哪里,增加了猜题难度,所以出题者给0A1B.
第四步,现在总猜题情况为0123,4501,6078.后面在像前面一样分析,我已经吃不消了,我就说我的猜题策略吧.第四步7890
如果第三步中,B是0的话,那么,出题者该给答案1A1B
(沿着这个假设,往下,总猜题情况为0123,4501,6078,7890.现在知道的是0位置已经确定,9确定为B.第五步9240,如果9位置对了,那么,如果给2A0B那么结果必然是9350.如果给2A1B结果必然是9430,如果给3A0B,结果可能是9250和9340也需要两步,最不好的情况就是要7步;如果9位置没对,我相信,在两步也能解出来.)只考虑这中情况,出题人就可以将你的步数限制到最少7步
如果第三步中,B是6,7,8中的一个,那么,0肯定不是B了,1肯定是B,而出题者只用考虑B是在7,8中,还是6,很显然,出题者会让B在7,8中,所以给的答案是0A1B.总猜题情况为0123,4501,6078,7890
第五步8215,出题者0A2B
第六步5381,出题者
1A0B===>2741,
1A2B===>3751,5731
2A1B===>3481
3A0B===>4381.只有这四种情况,是由于受到前面的限制.这中结果也需要7步
我不保证自己证明的都很严密,但作为一个解题者,我的感觉是,解这个题目可以步数更少些(虽然我也不知道能不能再少),如果有人能以更少的步数解出,我也会崇拜之,但如果说解这题目要比七步多,我就不同意了,我是完全站在出题者的立场,为难猜题者的思路的假设下去,这也是最糟糕的情况,这也应该是步数最多的情况,如果哪里不清楚可以问我,或者你认为自己可以让我7步内猜不出,可以找我试试本回答被提问者采纳

Answer 3

先来一个比较简单的
第一步先猜0001，2223，4445，6667，8889。既可判断是那四个数比如1、3、5、0
第二步选一个没有出现的数比如9，将它与前面四个中的一个组合，判断其位置
比如1999，9199，9919可判断1（前三个都不是就是第四个，下同）
第二个数需两次，第三个需一次，剩下的是最后一个
这样，最坏的情况只需11次，有点多，最大的优点是不需要动脑子

关于上述策略的改进
在第二步用两个确定出现的数，比如0和1，以0001的方式输入，有以下3种情况：
1A3B，0和1一定都不在第四位(因为这“1A”一定是0，如果是1，则0一定在前三位，会有2A，故1不在第四位，同样因为“1A”是0，0也不是第四位。)，这样剩下两个数一定有一个在第四位，剩下两个数，比如2、3，以2232的方式输入，如果3是第三位，则会显示2A2B，否则是4B，这样三四两位就定下来了，再猜一次可以确定一二两位的顺序，9次一定可以猜对
2A2B，1一定是第四位，0一定不是第四位
4B，0一定是第四位，1一定不是第四位
上面两种情况是等价的，第一次就可以确定一个数的位置，假设第四位是1，下一次猜0021，结果可能是3A1B，则结果是0321或3021，只需要再猜一次；或者2A2B，这是两个0里一定有一个是对的，2一定是错的，所以第三位一定是3，结果是2031或0231，也只需要再猜一次；或者1A3B，这时0一定在第三位，结果是2301或3201，仍然只需要再猜一次
综上所述，这种策略下，最坏的情况需要9次

进一步提高效率需要对各次的结果进行综合，情况太多了，失去作为一种策略的意义
这个问题,研究一下的确蛮有意思,下面是我的想法,不一定能解决问题,看可能可以给别人以启发.我主要研究的是<在最坏情况下最少几次猜中，策略如何？>
第一步,因为各个数都是一样的,所以第一次输入0123,现在轮到出题者,我相信没人会给他A,顶多给他B,但是给他几个B合理呢?
0B,下次猜到B的期望E=4*4/6=8/3
1B,E=1*1/4+3*3/6=7/4
2B,E=2*2/4+2*2/6=5/3
3B,E=3*3/4+1*1/6=29/12
4B,E=4作为出题人,希望对手猜对B的期望为最小,所以,选择给他2B.
第二步,输入4501,再次轮到出题者,现在问题开始复杂了.
我觉得可以把4501分为两部分,45和01,其中45是新的,按上题的方法继续做,
0B,E=2*2/4=1;
1B,E=1*1/2+1*1/4=3/4;
2B,E=2*2/2=2;所以出题者会在45中给1B.
其实复杂的是01部分,因为他涉及到A的部分,我只能假设,出题人在不得不给A时才给A这种情况,如果算期望的话,我已经搞不清了,所以从简了，而且这假设我觉得不一定不合理.从给B部分,我们可以同样按照开始的思路
0B,E=2*2/2=2
1B,E=1*1/2+1*1/2=1
2B,E=2*2/2=2
所以01中会给一个B,现在猜题者知道的东西有0,1中有1个;2,3中有一个;4,5中有一个;6,7,8,9中有一个.综上,第2步,出题者给的是0A2B.
第三步,猜题者这一步,稍微聪明点,从4组数中分别去4个数,最起码可以确定,3个数字.但是我们想,作为出题人,在6,7,8,9中,如果是一个数一个数猜,他肯定,会将最后一次猜的设为正确的以增加你猜题次数,也就是说,即使你从现在起,4步后,将6,7,8,9中正确数字的位置确定下来,也需要4步才能,将4个数字都确定.所以这种假设下,最少需要猜加上前面的两步,共6步.如果第三步猜2046.
出题人可以不给A就不给A的前提下,理智出题者给的应该是,0A1B为什么给1B不给0B呢,如果给0B,那么,猜题人就知道前三组数字中1,3,5是必对了,除了在确定A是比3B有优势,其他地方没优势.而给1B而不给2B的原因也就在于,确定A的时候1B比2B更有优势(猜题者更难猜)这样对猜题者来说,是很麻烦的,因为,他不知道1B是哪个,这次作答几乎对确定B没有任何贡献,所以,猜题者不应该出这些数字.如果前三组数字只出现1个,那么不仅可以唯一确定这个数字所在组的B,而且对6,7,8,9中选B也有积极意义
现在总猜题情况为0123,4501所以第三步,出6078.
问题越来越复杂了,对于0可以给B也可以不给,对于6,7,8可以给B也可以不给,0B,1,9肯定是B;2B,1肯定是B,而且6,7,8之间肯定有B,但如果给1B,猜题折还需要猜测,这个B来自哪里,增加了猜题难度,所以出题者给0A1B.
第四步,现在总猜题情况为0123,4501,6078.后面在像前面一样分析,我已经吃不消了,我就说我的猜题策略吧.第四步7890
如果第三步中,B是0的话,那么,出题者该给答案1A1B
(沿着这个假设,往下,总猜题情况为0123,4501,6078,7890.现在知道的是0位置已经确定,9确定为B.第五步9240,如果9位置对了,那么,如果给2A0B那么结果必然是9350.如果给2A1B结果必然是9430,如果给3A0B,结果可能是9250和9340也需要两步,最不好的情况就是要7步;如果9位置没对,我相信,在两步也能解出来.)只考虑这中情况,出题人就可以将你的步数限制到最少7步
如果第三步中,B是6,7,8中的一个,那么,0肯定不是B了,1肯定是B,而出题者只用考虑B是在7,8中,还是6,很显然,出题者会让B在7,8中,所以给的答案是0A1B.总猜题情况为0123,4501,6078,7890
第五步8215,出题者0A2B
第六步5381,出题者
1A0B===>2741,
1A2B===>3751,5731
2A1B===>3481
3A0B===>4381.只有这四种情况,是由于受到前面的限制.这中结果也需要7步
我不保证自己证明的都很严密,但作为一个解题者,我的感觉是,解这个题目可以步数更少些(虽然我也不知道能不能再少),如果有人能以更少的步数解出,我也会崇拜之,但如果说解这题目要比七步多,我就不同意了,我是完全站在出题者的立场,为难猜题者的思路的假设下去,这也是最糟糕的情况,这也应该是步数最多的情况.
分，快给我分（谢谢楼主让我练打字，一个小时呢）

Answer 4

先来一个比较简单的
第一步先猜0001，2223，4445，6667，8889。既可判断是那四个数比如1、3、5、0
第二步选一个没有出现的数比如9，将它与前面四个中的一个组合，判断其位置
比如1999，9199，9919可判断1（前三个都不是就是第四个，下同）
第二个数需两次，第三个需一次，剩下的是最后一个
这样，最坏的情况只需11次，有点多，最大的优点是不需要动脑子

关于上述策略的改进
在第二步用两个确定出现的数，比如0和1，以0001的方式输入，有以下3种情况：
1A3B，0和1一定都不在第四位(因为这“1A”一定是0，如果是1，则0一定在前三位，会有2A，故1不在第四位，同样因为“1A”是0，0也不是第四位。)，这样剩下两个数一定有一个在第四位，剩下两个数，比如2、3，以2232的方式输入，如果3是第三位，则会显示2A2B，否则是4B，这样三四两位就定下来了，再猜一次可以确定一二两位的顺序，9次一定可以猜对
2A2B，1一定是第四位，0一定不是第四位
4B，0一定是第四位，1一定不是第四位
上面两种情况是等价的，第一次就可以确定一个数的位置，假设第四位是1，下一次猜0021，结果可能是3A1B，则结果是0321或3021，只需要再猜一次；或者2A2B，这是两个0里一定有一个是对的，2一定是错的，所以第三位一定是3，结果是2031或0231，也只需要再猜一次；或者1A3B，这时0一定在第三位，结果是2301或3201，仍然只需要再猜一次
综上所述，这种策略下，最坏的情况需要9次

进一步提高效率需要对各次的结果进行综合，情况太多了，失去作为一种策略的意义

各位有高招欢迎指正~

Answer 5

第一步先猜0001，2223，4445，6667，8889。既可判断是那四个数比如1、3、5、0
第二步选一个没有出现的数比如9，将它与前面四个中的一个组合，判断其位置
比如1999，9199，9919可判断1（前三个都不是就是第四个，下同）
第二个数需两次，第三个需一次，剩下的是最后一个
这样，最坏的情况只需11次，有点多，最大的优点是不需要动脑子

关于上述策略的改进
在第二步用两个确定出现的数，比如0和1，以0001的方式输入，有以下3种情况：
1A3B，0和1一定都不在第四位(因为这“1A”一定是0，如果是1，则0一定在前三位，会有2A，故1不在第四位，同样因为“1A”是0，0也不是第四位。)，这样剩下两个数一定有一个在第四位，剩下两个数，比如2、3，以2232的方式输入，如果3是第三位，则会显示2A2B，否则是4B，这样三四两位就定下来了，再猜一次可以确定一二两位的顺序，9次一定可以猜对
2A2B，1一定是第四位，0一定不是第四位
4B，0一定是第四位，1一定不是第四位
上面两种情况是等价的，第一次就可以确定一个数的位置，假设第四位是1，下一次猜0021，结果可能是3A1B，则结果是0321或3021，只需要再猜一次；或者2A2B，这是两个0里一定有一个是对的，2一定是错的，所以第三位一定是3，结果是2031或0231，也只需要再猜一次；或者1A3B，这时0一定在第三位，结果是2301或3201，仍然只需要再猜一次
综上所述，这种策略下，最坏的情况需要9次