上帝请你救救我：猜数问题！
2004。11。30（二）
问题：1-1000，共1000个自然数，有10000个人来猜，每个人可以猜30次。谁猜的数最小，而且不与其它人重复就获胜。限时2小时。
要求：每个人不能去了解别人猜的数是什么；游戏中每猜一次，主持人就会告诉你，你猜的数有人重复；或者无人重复，但不是无重复的数中最小的‘或者无人重复，且是无重复的数中目前最小的。
如果你猜了一个数，比如56，目前是最小的而且是唯一的，主持人就会告诉你，你猜的56是目前最小的且唯一，但不能保证到游戏结束时还是最小且唯一。
有什么办法取胜？
我觉得有点象博奕论的应用。
我想用二分法，先定一个数，比如500，如果有人重复，取半，猜250，再重复，再向下取半猜125或者向上取半猜375。。。
有一个策略是，游戏准备结束时再去猜，因为前面猜的数在漫长的游戏时间中很容易被人重复。
不能一味猜小数，因为大家都去猜1啊2啊3啊就没意思了。
不知道是数学问题还是计算机算法中的查找问题。
请各位指点，谢谢！
问题点数：56、回复次数：34Top
1 楼jp1984（mathfrog）回复于 2004-12-01 10:15:53 得分 0
不太明白题目的意思，什么叫猜的最小？ 万一猜中了怎么办？？？
能不能给出形式化的描述？Top
2 楼mathe（）回复于 2004-12-01 11:02:46 得分 0
人太多，而且每个人有30次机会，几乎不会出现有数据不会被人重复的情况。Top
3 楼mathe（）回复于 2004-12-01 11:07:45 得分 0
换成我，就弃权，增加人家获胜的机会:)不然大部分情况根本没有人能够胜出:)Top
4 楼lovesf（www.lovesf.net）回复于 2004-12-01 11:30:36 得分 0
比如：
4
5
5
6
6
6
6
6
6
7
9
9
9
9
10
10
10
5和6和9和10都有人重复，4和7没有人重复，而4是没有重复的数中最小者，所以猜4的人获胜。Top
5 楼NowCan（城市浪人）回复于 2004-12-01 13:05:15 得分 0
见过这个题目。一共才1000个数，不重复的概率太小了。
还有一个问题，如果先前猜的一个数是无重复的最小值，在后来的游戏过程中出现了重复是否能得到通知？还有，如果我先前猜了一个数是无重复的最小值，而后来我猜的很多次都不是无重复的最小值，并且，先前的那个的却是游戏结束时的无重复的最小值，这种情况下我算不算胜出？
如果大家都像 mathe那样弃权策略，那我就胜出了。Top
6 楼mathe（）回复于 2004-12-01 13:38:46 得分 0
呵呵，那也是我成全你。所以最好的方法是大家联合Top
7 楼lovesf（www.lovesf.net）回复于 2004-12-01 14:39:03 得分 0
回复人： NowCan(((((( ★ )))))) ( ) 信誉：100 2004-12-01 13:05:00 得分: 0
见过这个题目。一共才1000个数，不重复的概率太小了。
还有一个问题，如果先前猜的一个数是无重复的最小值，在后来的游戏过程中出现了重复是否能得到通知？还有，如果我先前猜了一个数是无重复的最小值，而后来我猜的很多次都不是无重复的最小值，并且，先前的那个的却是游戏结束时的无重复的最小值，这种情况下我算不算胜出？
如果大家都像 mathe那样弃权策略，那我就胜出了。
***********************
1）如果先前猜的一个数是无重复的最小值，在后来的游戏过程中出现了重复是否能得到通知？----->>能得到通知。
2）如果我先前猜了一个数是无重复的最小值，而后来我猜的很多次都不是无重复的最小值，并且，先前的那个的却是游戏结束时的无重复的最小值----》》胜出
Top
8 楼Fortress（观察使）回复于 2004-12-01 14:41:25 得分 0
这个题目要这样改一下才能比较好的讨论：大家猜数是按轮次进行的，当某一轮所有的数都出来后，主持人搜集所有结果，然后针对每个人出的数，给出“你的数”又无重复，是否最小等信息。每一轮也可以弃权。
对nowcan的问题，我想比较合理的规则是每个人出的数一直都是有效的，目前市面上所有的此类游戏都是按此规则进行的。
另外还可以加入的变化是，每一轮都宣布目前无重复且最小的数是几，这种玩法更刺激。
我感觉这种游戏没有通用“好”策略，只有针对某种策略的好策略。
nowcan，能不能写个AI通用测试程序，大家自己设计AI比拼一下？我想这种AI还是很好设计的，纯粹娱乐。Top
9 楼sutra（一生一世与C相约）回复于 2004-12-01 14:44:28 得分 0
我看这玩意怎么那么像金山剑侠情缘搞的猜数赢黄金装备的东西呢？Top
10 楼huhuhu5（）回复于 2004-12-01 15:00:25 得分 0
哦 懂了
to:NowCan(((((( ★ ))))))
如果猜到过目前无重复最小值后 如果有人猜到相同值 应该是没有人通知的.而后猜得人却可以知道这个是重复的.
现在的状况是如果猜到了无重复值 但不是最小 这个值还很有可能是最后的结果 也就是游戏结束时的无重复最小值!!
看这个题目是10000人 猜 应该属于概率范畴了吧 我不是很懂 是不是还涉及到心理学啊? 呵呵
我好像第一次看到mathe()这么无奈啊 哈哈哈Top
11 楼huhuhu5（）回复于 2004-12-01 15:06:54 得分 0
哦 是这样 呵呵 猜错了 :PTop
12 楼huhuhu5（）回复于 2004-12-01 15:11:11 得分 0
== 现在的规则有些乱
又加了一些规则 原题的可没有轮的说法
不过 我认为 Fortress(观察使)的规则加的不错啊
to: Fortress(观察使)
能不能把完整的规则说明一下 大家都看看 写些小东西玩玩挺有去的啊Top
13 楼mathe（）回复于 2004-12-01 15:29:56 得分 0
呵呵，还是要先将规则弄好，至少大家都猜完后要有一个赢的人呀。按现在这个策略，
只能最后大家都赢不了。Top
14 楼Fortress（观察使）回复于 2004-12-01 15:41:57 得分 15
楼主的要求是任何人随时都可以出数，这是没法讨论的。规定轮次后，题目变成离散数学范畴了，这才好讨论。我定一下规则吧：
1。游戏有一个主持人和n个玩家。
2。主持人给出一个自然数N和游戏轮次T。
3。每个玩家秘密报给主持人一个[1，N]之间的自然数，也可以不报。
4。主持人搜集所有玩家报上来的数，包括以前轮次的，然后分析每个数是否有两个或两个以上玩家报出，并且找出目前最小且无重复的那个数。
5。主持人报给每个玩家你本轮报的数是否重复和你本轮报的数大于还是小于目前最小且无重复的那个数。
6。重复步骤3-5，共T次。
7。报出那个最小且无重复数的那个玩家获胜。若每个数都重复，则全输。
大家看看这个规则行不行，行的话，我写个java程序，供大家比拼策略。我想这应该不是很难，而且这种游戏也没必要算法保密吧。Top
15 楼huhuhu5（）回复于 2004-12-01 15:51:31 得分 0
关于 5。主持人报给每个玩家你本轮报的数是否重复和你本轮报的数大于还是小于目前最小且无重复的那个数。
中的"你本轮报的数大于还是小于目前最小且无重复的那个数。" 我认为不说的好 这样更有趣些
而且应该没有"小于"吧
Top
16 楼huhuhu5（）回复于 2004-12-01 15:53:33 得分 0
o 我真本 后一句不用说得 通过这轮报的是否重复及是否值无重复最小就可知道状态了Top
17 楼huhuhu5（）回复于 2004-12-01 15:55:18 得分 5
主持人的报告 应该只有:
1 重复
2 不重复但不是最小
3 不重复且最小
不再有别的提示了Top
18 楼Fortress（观察使）回复于 2004-12-01 15:55:38 得分 0
有“小于”啊，“小于”就表示你报的数重复了。我加这个条件是给每个玩家报下一个数稍微有点方向，否则跟瞎猜无异。Top
19 楼Fortress（观察使）回复于 2004-12-01 15:57:31 得分 0
主持人的报告 应该只有:
1 重复
2 不重复但不是最小
3 不重复且最小
不再有别的提示了
这个不错，先按你这个规定来吧。Top
20 楼mathe（）回复于 2004-12-01 16:04:52 得分 0
最后全输不好，在人数比较多时太容易全输了。
这样吧，如果最后一轮没有人单独拥有一个数字，我们就看前一轮的结果。
如果前一轮也没有，那么再前一轮。
也就是说，是最后一个拥有最小的单独数字的人赢:)Top
21 楼huhuhu5（）回复于 2004-12-01 16:17:37 得分 0
恩 8错8错!!
那谁来把具体的数定下来
咱么好动手啊!!(我可不一定参加啊 嘻嘻)Top
22 楼Fortress（观察使）回复于 2004-12-01 16:32:36 得分 0
mathe的想法不错，那这个规则就是目前版本：
1。游戏有一个主持人和n个玩家。
2。主持人给出一个自然数N和游戏轮次T。
3。每个玩家秘密报给主持人一个[1，N]之间的自然数，也可以不报。
4。主持人搜集所有玩家报上来的数，包括以前轮次的，然后分析每个数是否有两个或两个以上玩家报出，并且找出目前最小且无重复的那个数。
5。主持人的单独给每个玩家报告，有:
1 重复
2 不重复但不是最小
3 不重复且最小
不再有别的提示了
6。重复步骤3-5，共T次。
7。最近一轮报出那个最小且无重复数的那个玩家获胜。若每一轮都没有这样的数，则全输（玩家够倒霉的）。
我想里面n,N和T都是参数，不用确定下来的。
我想每个AI的接口java函数原型可以这样写：
abstract class player{
abstract int guessNumber(boolean isDuplicated,boolean isMinium);
}
isDuplicated表示你最近一次报的数是否重复，isMinium表示是否最小，仅当isDuplicated=false是有效。返回值为你下一次猜的数，返回0表示弃权。
你只要继承player，写你的函数就可以了。n,N,T都是全局变量（java中就是某个类的静态变量）。我已经想动手了。Top
23 楼Fortress（观察使）回复于 2004-12-01 17:11:11 得分 0
还需增加一条，当你上一轮弃权时或比赛是第一轮时，系统给玩家：isDuplicated=true.Top
24 楼lovesf（www.lovesf.net）回复于 2004-12-01 19:36:56 得分 0
好象忘记说了一条规则：如果你出的数最小且唯一，但是很不幸，后来有人和你的重复，那么主持人会告诉你。Top
25 楼Fortress（观察使）回复于 2004-12-02 12:36:40 得分 0
应该还不够，还有一条：如果你的某个数曾经是唯一，但不是最小，但后来便成唯一且最小的数了，你应该得到通知。所以类原型应该是：
abstract class player{
void LoseWinPosition(int number){}
void GetWinPostion(int number){}
abstract int guessNumber(boolean isDuplicated,boolean isMinium);
}
LoseWinPostion在你的某个最小且唯一的数被别人重复了以后，由系统调用。参数number就是这个数。
GetWinPostion在你的某个最小但不唯一的数变成最小且唯一以后，由系统调用。参数number就是你目前能取胜的这个数。Top
26 楼hualiu6688（）回复于 2004-12-02 21:31:36 得分 0
清华大学计算机课程(教授讲课录像)
快到www.8cd.cn
Top
27 楼Fortress（观察使）回复于 2004-12-09 09:43:45 得分 11
一个粗糙的Java程序有了：http://venusd.mofile.com/9139121897816019/2997664213896980/2/AF21F54726D85FB39D80A8754C16A0E0/numberguess.zip
你要做的就是继承player类，写自己的策略。然后在Main函数中，设定参加比赛的玩家。
我写了两个Sample Player，一个叫RandomPlayer，就是每次在1到(玩家人数*轮次）之间随机猜数。另一个叫GreedyPlayer，就是“贪心”策略，就是每次从1开始从小到大猜数。
显然，当一个GreedyPlayer和一个RandomPlayer对阵时，GreedyPlayer总能取胜。但比赛中如果有两个或以上的GreedyPlayer，他们就会两败俱伤。
程序详细说明我有空会写到blog，希望你能看懂。Top
28 楼Fortress（观察使）回复于 2004-12-09 09:48:45 得分 5
哦，应该用这个地址下载：http://venusd.mofile.com/9139121897816019/0258274579515756/2/652B89C053DA861C87FB370304B915A7/numberguess.zip，三天内有效。Top
29 楼bamboo2000（龙的传人）回复于 2004-12-11 17:44:04 得分 5
网易好像弄过一个什么什么低价拍卖了，就是这个规则吧
我选择的是弃权，^_^Top
30 楼icansaymyabc（学习与进步）回复于 2004-12-11 20:09:06 得分 0
1000 个数 要被猜 300000 次，平均每个书会被猜 300 次。
要找一个数除了你，没人猜过，不可能。Top
31 楼qrlvls（ 空 气 ）回复于 2004-12-11 22:48:53 得分 0
佛曰：...Top
32 楼lovesf（www.lovesf.net）回复于 2004-12-13 08:51:13 得分 0
我还是不太明白如何能够获胜Top
33 楼mathe（）回复于 2004-12-13 09:18:15 得分 15
没有获胜的方法，不同的人采取的策略都会不同，所以我们采用的应对方法也会不同。
最好的办法是去统计历史数据，比如大家过去都选择了什么，最少选择的是什么。
选择最不容易被大家选择的数据。
如果没有统计数据，只能猜测大家的心理（好像要用心理学了:) )
我估计大部分人会偏向选择比较小的数据，还有一些特别大的数据如1000等也会容易被人选择。
还有些特别的数如888,666，100等比较被人喜欢的数据也会容易被大家使用。
反正选择越平淡无奇的数字越好。
Top
34 楼mathe（）回复于 2004-12-13 09:21:39 得分 0
其实还和对手都是哪些人有关系，如果大家都很聪明，那么你就是随机选择都一样，
反正大家都赢不了。Top
