关于猜数字游戏的讨论
本帖最后由 hillchencgs 于 2011-4-27 16:23 编辑这个想法来自海外复活节彩蛋活动戳这里
于是这是个扯淡，不知道适不适合发在案发。。。。。。。。。
游戏很简单，就是猜0到5000里的一个数，可以跟帖询问答案是不是某个数，或者某个范围，斑竹回答是或者不是
比如你问1000-2000，法官说错，意味着答案在0-999，或者2001-5000
这个游戏跟传统的猜数字游戏不大一样，传统的猜数字是问一个数字，法官告诉你高了还是低了
比如说你说2500，法官说高了，意味着答案是在0-2499这个范围
也就是说，猜数字游戏是通过猜分界点来缩小答案范围
对比上面两个游戏可以看出，第一个游戏相当于第二个游戏的加强版，一次可以问两个分界点。
于是就涉及到如何一次提问能得到最大信息的问题，拿猜1-6做例子
传统的二分法问法，问1-3，无论答案是什么，一次提问能缩小一半范围。
但这是不是最优算法呢，这样提问1这个分界点已知，相当于浪费了一个信息
换一种问法，问3-4，这样无论反馈如何，能将范围分为三部分
一次提问后，第一种问法范围缩小到3个，第二种问法能缩小的范围的期望是2*1/3+4*2/3=3.3
就一次提问，2分法更有效率
（额，这里想简单了，有空再想想）
然后再讨论个问题，因为版主并不是随时在，所以不能迅速对你的提问做出回答
这就涉及到在无反馈的情况下如何缩小范围的问题
一般的思路是几个人分别问，0-1000，1000-2000。。。。。。。。。
但是跟上面一样的思路可以得到更优的方法，一次提问能获得2个分界点信息，所以比较好的问法是
0-2500
1250-3750
依此类推，这样等法官回来对上诉提问做出反馈时，n个人就能将范围缩小到5000/（2n+1）个
扯淡也扯完了，有点罗嗦了
看着有点晕。。。
这游戏难道考验的是团队合作能力么。。。。。 b.p.bravo 发表于 2011-4-26 16:31 static/image/common/back.gif
怎么就是都缩小到1/3
猜对是缩小到1/3
猜错就是缩小到2/3
恩，这是我想错了
在有反馈的情况下，的确还是2分法快
本帖最后由 yylxxch 于 2011-4-27 16:16 编辑
依此类推，这样等法官回来对上诉提问做出反馈时，n个人就能将范围缩小到5000除以2的n次方个
这里缩小范围应该是5000/2n。
更精确一点说应该是5000/（2n+1）。
yylxxch 发表于 2011-4-27 16:13 static/image/common/back.gif
这里缩小范围应该是5000/2n。
更精确一点说应该是5000/（2n+1）。
想了下，貌似比2n的效率更低。。。。。。。。 hillchencgs 发表于 2011-4-27 16:19 static/image/common/back.gif
想了下，貌似比2n的效率更低。。。。。。。。
在无迅速反馈的前提下这样就挺好。
不过想组团刷怪难度不小==
yylxxch 发表于 2011-4-27 16:21 static/image/common/back.gif
在无迅速反馈的前提下这样就挺好。
不过想组团刷怪难度不小==
哈哈哈，这已经比预期要快多了，海外的斑竹一轮本来是2天时间的
页:
[1]