猜数问题的算法
2004。11。30（二）
问题：1-1000，共1000个自然数，有10000个人来猜，每个人可以猜30次。谁猜的数最小，而且不与其它人重复就获胜。限时2小时。
要求：每个人不能去了解别人猜的数是什么；游戏中每猜一次，主持人就会告诉你，你猜的数有人重复；或者无人重复，但不是无重复的数中最小的‘或者无人重复，且是无重复的数中目前最小的。
如果你猜了一个数，比如56，目前是最小的而且是唯一的，主持人就会告诉你，你猜的56是目前最小的且唯一，但不能保证到游戏结束时还是最小且唯一。
有什么办法取胜？
我觉得有点象博奕论的应用。
我想用二分法，先定一个数，比如500，如果有人重复，取半，猜250，再重复，再向下取半猜125或者向上取半猜375。。。
有一个策略是，游戏准备结束时再去猜，因为前面猜的数在漫长的游戏时间中很容易被人重复。
不能一味猜小数，因为大家都去猜1啊2啊3啊就没意思了。
不知道是数学问题还是计算机算法中的查找问题。
请各位指点，谢谢！
问题点数：0、回复次数：11Top
1 楼xman_df（df）回复于 2004-12-01 11:11:59 得分 0
我觉得你这个问题：很有可能的情况是最后没一个人获胜。
因为共1000个自然数，有10000个人来猜，每个人可以猜30次这样平均覆盖率（10000*30/1000=300）太高了，这样的结果一般都是1000个数没有一个不重复的。
我个人认为如果把问题该为共1000个自然数，有1000个人来猜，每个人可以猜30次，这样获胜的可能性比较大一些，这才涉及到用什么算法可以获胜的问题。
在上面这个前提下，我认为下面这个算法有可行之处：
给定两个参数A和B初始值都为0
你猜的数的公式为：S=A+（2的B次方） S为你猜的数
每猜一次B=B+1，当S>1000时B重新置为0、A=A+1。
这个算法可以变通：比如A和B的初始值可以改变
Top
2 楼J2EE99（）回复于 2004-12-01 13:23:36 得分 0
2004年11月软考试题分析
http://www.ciu.net.cn/Article_Show.asp?ArticleID=1532
CIU 2005精彩软考复习资料下载
http://www.ciu.net.cn/Article_Show.asp?ArticleID=1525
相关内容
http://www.ciu.net.cn/hzzx/kspx.htm
以考带学,始于证书,止于无限,CIU竭诚为广大考生服务!Top
3 楼lovesf（www.lovesf.net）回复于 2004-12-01 14:43:02 得分 0
xman_df
谢谢，我考虑一下Top
4 楼lovesf（www.lovesf.net）回复于 2004-12-02 11:49:15 得分 0
这个公式好象是单调的，不能向另外一个方向调整啊Top
5 楼postage（jh）回复于 2004-12-02 16:07:55 得分 0
哈哈，手机短信常难来骗钱的手段。Top
6 楼qinyidaxia（平凡）回复于 2004-12-02 16:21:22 得分 0
知道了Top
7 楼lovesf（www.lovesf.net）回复于 2004-12-02 16:46:58 得分 0
i seeTop
8 楼iicup（双杯献酒）回复于 2004-12-02 21:41:37 得分 0
在这里，找到最小的数不在重要，
重要的是这个数不会被重复。
我们假设，有个人第一次猜 1
那么，肯定是“最小且不重复的”，
但显然他并没有取得最后胜利，
很快，他就会变成“有重复的”了。
当猜的人足够多，就会完全覆盖，任何数都是有重复的。
好像是手机骗钱的把戏。Top
9 楼lovesf（www.lovesf.net）回复于 2004-12-03 08:28:11 得分 0
大家都说是手机骗钱的把戏,可是如果真有的话,一定有很多人参加,那么如何取胜呢?Top
10 楼xman_df（df）回复于 2004-12-03 08:38:17 得分 0
我个人认为是单调的是正常的啊
因为你要的是最小的数啊。
还有你们大家都说是手机骗钱的把戏是因为：
共1000个自然数，有10000个人来猜，每个人可以猜30次这样平均覆盖率（10000*30/1000=300）太高了，这样的结果一般都是1000个数没有一个不重复的。
所以我上面才说：
把问题改为共1000个自然数，有1000个人来猜，每个人可以猜30次，这样获胜的可能性比较大一些，这才涉及到用什么算法可以获胜的问题。
Top
11 楼lovesf（www.lovesf.net）回复于 2004-12-13 08:49:58 得分 0
单调的意思,只要猜一个方向就可以获胜吗Top
