您的位置：程序门 -> vb -> 基础类

算法题（猜数字)

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

算法题（猜数字)[已结贴,结贴人:ayalicer]

发表于：2007-02-26 10:56:05 楼主

先有0~9十个数字
任意取4个进行排列（数字不重复)
比如说1234
然后让你猜假如你猜
1253 提示 2正1反 1,2 数字正确处理位置也正确处理3 数字正确位置不正确
1256 提示 2正0反
直到你猜 1234 提示 4正0反猜测结束游戏重新开始
--------------
以上应该很简单现在要求人来想不重复的4位数让电脑猜然后根据电脑猜测的结果给电脑相应 n正m反的提示直到电脑猜出答案
当然猜测的次数有限制一般情况为7次以内.
请写一个最优猜测算法

发表于：2007-02-26 11:12:411楼得分:5

既然要最优，那先讨论下如果是人来猜，怎么最快猜出吧。

发表于：2007-02-26 11:28:312楼得分:10

第一次猜肯定是0123
if m正n反，保持m个数字位置不变，调动其他数字位置，求解，递归，if m=0 and n=0，取其他数字

发表于：2007-02-26 11:35:303楼得分:5

这个游戏我玩过，挺好玩的
-----------------------------------
俺兜兜里有糖

发表于：2007-02-26 11:48:414楼得分:10

详细点说：
1.if m=0 and n=0，取其他数字
2.if m正n反，保持m个数字位置不变，调动其他数字位置，求解，递归，直到求出m+n正，即j正0反，取出剩下数字中的4-j个，放入非正的位置（这个好像有点复杂）
3.（调动非正位置数字），求解，递归，直到j=4为止。

发表于：2007-02-26 11:52:225楼得分:5

这个有点象破解密码。呵呵。

发表于：2007-02-26 14:33:496楼得分:0

关键是要最优
人工猜的话一般是7次左右
所以要考虑每次要怎么猜了
不一定n正后 n个数字位置不变才是最优的

发表于：2007-02-26 14:57:007楼得分:5

发表于：2007-02-26 19:15:108楼得分:10

那你就按照你猜的思路去写代码咯。。

发表于：2007-02-26 20:25:139楼得分:0

如果那么容易就把思路理清楚代码早就写出来了

发表于：2007-02-27 10:06:3510楼得分:5

最开始想的时候不要直接想从十个中选四个,要想从四个中选两个,五个中选两之类的,就是先从少的想起

发表于：2007-02-27 10:11:5511楼得分:5

像四个中先两个,开始猜12,如果有正确的最好,再看有没有反的
如果有正确的或反的,就可以确定一个,这就成了三先一
如果两者都没有,就猜34,这肯定会有一个正确的或者是反的,就可以得到一个数正确了,下面就是从三个中选一个了,

发表于：2007-02-27 21:31:3912楼得分:0

楼主搞这个是为了什么,我觉得没有应用的方面

发表于：2007-02-28 06:33:1413楼得分:0

锻炼下思维而已

发表于：2007-02-28 11:16:3414楼得分:0

别沉了顶起来相信真正的算法高手在vb版而不是c版的

发表于：2007-03-02 14:33:0015楼得分:5

mark一下,研究中...

发表于：2007-03-02 14:39:0116楼得分:5

好难

发表于：2007-03-03 22:41:4017楼得分:20

若upperbound（)表示上取整，
lowerbound（)表示下取整；
则从n个数之中随机选择m个进行猜测
用如下算法可保证最坏
lowerbound（n/m) + upperbound（（lowerbound（n/m) + lowerbound（m/2)) / 2 ) * m
+ m - （n - m * lowerbound（ n/m ) ) - 1
次即可成功。
当 n = 10 ,m = 4 时,代入上式,
可得
2 + 2 * 4 + 4 - （10 - 4 * 2) - 1 = 11
每种猜测情况都是等可能的则平均猜测数为：
（1+11)/2 = 6;
因此,楼主题目得解.

（为避免因为编程语言造成理解障碍用中文描述，我用c++编码测试过。）
方法如下：

零，特殊情况的处理：
若 n < m; 则退出程序。
若 n = m; 则输出n为结果，退出程序。

一,初始化阶段:
1 建立一个大小为n的表（以下简称为t1,最简单用数组表示），
每一表项有如下属性（1) belong （有4个状态：yes，relevant，no，unknow（初始态）)
（2) relevant （记录与某数相关）
（3) 一个数组position
（为一大小为m的3状态（true,false,relevant)数组，
初始状态为每一项都是true,
表示所有位置都有可能）

因为每一表项的index与n个数一一对应,
所以可以由以上属性和index确定哪个数为选定的数,并确定是否在正确位置上;

2 建立一个队列（以下简称为q),把t的index以随机方式入队;

3 建立lowerbound（n/m)个大小为m的数组
（对于每一个数组简称为m[n] 0 <= n < lowerbound（n/m) （在c/c++ 中数组从0开始)
,用来存放从q中出队的index);

4 建立一个大小为lowerbound（n/m)的数组
（以下简称为guess[n]，0 <= n < lowerbound（n/m)用来与m[n]对应），
数组的每一项由如下属性：（1）allright （2）positionerror

5 建立一个大小为lowerbound（n/m)的int数组（以下简称为isrepresentative[n],
0 <= n < lowerbound（n/m))
初始值为-1，用来与m[n]对应,表示没有成为代表；

6 建立一个大小为lowerbound（n/m)的bool数组（以下简称为empty[n],0 <= n < lowerbound（n/m)
用来与m[n]对应,表示是否为空）初始值为false;

7 建立一个队列（以下简称为q2,用于存放配对后形成的代表。）

二执行:

1 用q中的index数据分别填满设置为空的m[n],
填满一次猜测一次，把猜测的结果存入guess，其中allright存放完全正确的项数，
positionerror存放位置错误的项数。若有allright+positionerror==m的项，则转到6；

2 置那些与guess中 allright + positionerror == 0的项相对应的m[e]为空
（设置empty[e] is true）,
累加guess中的所有项的（allright+positionerror），若和为m，则删除q；
否则若q中的数据数大于m且存在空的m[n]则（最多大于m,且小于2m）转到1；

3 对于剩下的m[n]，依照每一项的（allright+positionerror）值的大小，
把（allright+positionerror）值最大的与（allright+positionerror）值最小的配对
（如：m[k]m[j]为一对），
对于每一对m[n]选出（allright+positionerror）值较小者作代表，
（m[k]与m[j]为一对，可令m[k]为代表,置其对应isrepresentative[k] 为j）
若剩下的m[n]为奇数则随便用一个配对过的且没有为代表的m[a]
与没配上对的m[z]按以上原则再配出一组；
把已经是代表的m[n]放入q2中；

4 对于从q2中出队一个代表m[n]
把它和它所代表的另一个m[k]之间
对于每对m[n][i] 与m[k][i] （0 <= i <= m-1）如下
操作（设这些操作为一函数judgeanddo（m[n][i],m[k][i]))：

judgeanddo（m[n][i],m[k][i]){
m[n][i],m[k][i]
进行对调，然后让人对m[n]猜测,
将猜测的结果（以下简称为result 类型与guess[n]相同)
与guess[n]中的allright和positionerror
进行比较；结果无非以下所示：
（1)result.allright > guess[n].allright
（2)result.positionerror > guess[n].positionerror
（3)result.allright < guess[n].allright
（4)result.positionerror < guess[n].positionerror
（5)result.allright > guess[n].allright
且 result.positionerror > guess[n].positionerror

根据以上情况更新表t1:

对于（1）
t1[ m[n][i] ].belong = yes;
除 t1[ m[n][i] ].position[ m[n][i] ]外的所有位置都为false.
t1[ m[k][i] ].belong = no;
更新所有与这两项相关的项目；
检查t1中是否有m个条目已知，
且位置确定（包括为单一和互相约束可判断的两种情况）
若有则输出结果结束程序。

对于（2）t1[ m[n][i] ].belong = yes;
t1[ m[n][i] ].position[ m[n][i] ] = false;
t1[ m[k][i] ].belong = no;
更新所有与这两项相关的项目；
检查t1中是否有m个条目已知，
且位置确定（包括为单一和互相约束可判断的两种情况）
若有则输出结果结束程序。

对于（3）t1[ m[n][i] ].belong = yes;
除 t1[ m[n][i] ].position[ m[n][i] ]外的所有位置都为false.
t1[ m[k][i] ].belong = no;
更新所有与这两项相关的项目；
检查t1中是否有m个条目已知，
且位置确定（包括为单一和互相约束可判断的两种情况）
若有则输出结果结束程序。

对于（4）t1[ m[n][i] ].belong = yes;
t1[ m[n][i] ].position[ m[k][i] ] = false;
t1[ m[k][i] ].belong = no;
更新所有与这两项相关的项目；
检查t1中是否有m个条目已知，
且位置确定（包括为单一和互相约束可判断的两种情况）
若有则输出结果结束程序。

对于（5）t1[ m[n][i] ].belong = relevant;
t1[ m[n][i] ].relevant = m[k][i];
t1[ m[n][i] ].position[ m[n][i] ] = relevant;

t1[ m[k][i] ].belong = relevant;
t1[ m[k][i] ].relevant = m[n][i];
t1[ m[k][i] ].position[ m[k][i] ] = relevant;

judgeanddo（m[n][i],m[k][i+1])
}

5 检索t1,找出答案，若不能得出答案，则说明猜测人有欺骗行为，给出提示，退出。

6 把该项重复调用（0 <= i <（m+1）/2) judgeanddo（m[n][i],m[n][m - i])。

发表于：2007-03-04 11:53:3118楼得分:5

引用楼上
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
2 + 2 * 4 + 4 - （10 - 4 * 2) - 1 = 11
每种猜测情况都是等可能的则平均猜测数为：
（1+11)/2 = 6;
因此,楼主题目得解.
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
说明一下～这个11和1猜策的可能绝对不是等可能的～！
1次猜中的机率很小，1/（9*8*7*6) 这样还是没有0的情况

这个早有人写出了整个树的情况。。。。。

发表于：2007-03-04 12:21:0119楼得分:0

等我明天慢慢看了
先谢谢楼上两位

发表于：2007-03-04 14:00:4120楼得分:0

修正（5)result.allright == guess[n].allright
且 result.positionerror == guess[n].positionerror
引用楼上
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
2 + 2 * 4 + 4 - （10 - 4 * 2) - 1 = 11
每种猜测情况都是等可能的则平均猜测数为：
（1+11)/2 = 6;
因此,楼主题目得解.
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
说明一下～这个11和1猜策的可能绝对不是等可能的～！
1次猜中的机率很小，1/（9*8*7*6) 这样还是没有0的情况

这个早有人写出了整个树的情况。。。。。

算法中随机入队就是让每种情况等可能。

发表于：2007-03-04 14:04:4721楼得分:5

错误是copy and paste 造成的，
晚上酒喝多了，眼花了，
中文算法没有编译器纠错。

下一篇：急救：一个伊朗黑客写给我的信，搞不定了，请大家来帮忙为国争光！！！
上一篇：vb中access运行问题请高手指教