|
- UID
- 62447
- 帖子
- 13053
- 精华
- 6
- 威望
- 57
- 阅读权限
- 100
- 来自
- 这里
- 注册时间
- 2004-2-21
|
22#
发表于 2009-10-7 23:51
| 只看该作者
原帖由 zxoys 于 2009-10-7 23:22 发表 
我答案是50~7200次之间，最倒霉，最糟糕的情况下7200次
仔细想了想,我的答案有误..更新一下..
最多需要询问的次数为:当有超过50个回答X为"鬼"时,则确认X为鬼.因为是最坏的情况,考虑到需要询问99次才能够得到这个结论.于是将X排除,在余下的99个之中重新设一个"X",按照步骤继续询问,需要98次询问得到X为"鬼"的结论.按照这个方法持续下去.因为鬼最终的数量只有49个,当排除了49个鬼之后余下的51个便都是人了.
于是询问的次数为:
99+98+97+96+95+94........+53+2
=(100*10+90*10+80*10+70*10+60*7)-[4(1+2+3+4+5+6+7+8+9+10)+(1+2+3+4+5+6+7)]+2
=(1000+900+800+700+420)-[4*55+28]+2
=3820-[220+28]+2
=3820-248+2
=3572+2
=3574
至于为什么算式最后是+2而不是+52呢,因为当剩下最后1个鬼和51个人总数为52时,从中设一个X.只需要询问其中两个关于X的身份,而只可能出现如下几种情况:
1、两个都回答"人",那么X必定是人,因为只剩下一个鬼,不论他的答案真话还是假话,第二个答案必定是真的.
2、两个都回答"鬼",那么X必定是鬼,而因为唯一剩下的鬼被设为了X,于是剩下的51人必定全都是人,就不用再问了.
3、一个答"鬼",一个答"人",因为人必定说真话,而会说假话的只有鬼,所以出现不同答案的话必定有一个是假话,也就是说他们两个之中有一个是鬼,而鬼只剩下了一个,所以X必定是人.
于是,最多的询问次数应该为3574次... |
|
