关于猜数字游戏的讨论

hillchencgs

这个想法来自海外复活节彩蛋活动戳这里
于是这是个扯淡，不知道适不适合发在案发。。。。。。。。。

游戏很简单，就是猜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）个



扯淡也扯完了，有点罗嗦了

工藤美希子

看着有点晕。。。
这游戏难道考验的是团队合作能力么。。。。。

hillchencgs

b.p.bravo 发表于 2011-4-26 16:31
怎么就是都缩小到1/3
猜对是缩小到1/3
猜错就是缩小到2/3

恩，这是我想错了
在有反馈的情况下，的确还是2分法快

yylxxch

依此类推，这样等法官回来对上诉提问做出反馈时，n个人就能将范围缩小到5000除以2的n次方个

这里缩小范围应该是5000/2n。
更精确一点说应该是5000/（2n+1）。

hillchencgs

yylxxch 发表于 2011-4-27 16:13
这里缩小范围应该是5000/2n。
更精确一点说应该是5000/（2n+1）。

想了下，貌似比2n的效率更低。。。。。。。。

yylxxch

hillchencgs 发表于 2011-4-27 16:19
想了下，貌似比2n的效率更低。。。。。。。。

在无迅速反馈的前提下这样就挺好。
不过想组团刷怪难度不小==

hillchencgs

yylxxch 发表于 2011-4-27 16:21
在无迅速反馈的前提下这样就挺好。
不过想组团刷怪难度不小==

哈哈哈，这已经比预期要快多了，海外的斑竹一轮本来是2天时间的