与星独白

你们两个无视我

zxoys

原帖由 々风妖々 于 2009-10-8 23:39 发表
求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内.

从计算的角度，你的算法是正确的，开始我也觉得是对的，但不知道为什么老让我有种哪里出错的感觉，后来突然想到，从现实角度就不对了

zxoys

原帖由 々风妖々 于 2009-10-8 23:39 发表
求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内.

我也是突然想到的，你的算法，在最多第99次时，说假话的鬼会被暴露身份，因为人是不会说假话的，因为确定了自己手里的是鬼，那么说他是人的，岂不是都是鬼？
所以鬼只能说真话才能隐藏自己

々风妖々

求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内.

与星独白

答案
3+5+……+49=624


分析

抽出两个人问话  会有3种情况:

1.两者都说对方是人                   推论:两者都是人或两者都是鬼
2.两者都说对方是鬼                   推论:两者都是鬼或一人一鬼
3.一人说对方是人 一人说对方是鬼      推论:同上

由上分析可知:双方都是人的情况只有情况1..

故  将出现情况2和情况3的两人都排除..

此时  人鬼数量都为偶数  并被你的抽取而两两分组

这样便可以采用"拆对造单"的思想来进行排除,进而缩小取值范围


步骤

最差的情况是原100个中52人48鬼

从100人(鬼)中随机舍去一个,然后随机抽取两个问话

抽到的情况最差的是只有一对问话是情况2或3

另外还剩一人  将剩下一人也舍去

此时 问话49次 舍去4者  还剩28组

接下来重复以上步骤

全部最差情况每次只舍去4这计算

最后一次剩3组人  1组鬼

问话3次  舍去2人2鬼  剩下4个全是人


故  根据等差数列求和得: 3+5+...+49=624

-------------------------------------------------------------------------------------

不知道有没错

最近数分和C程学的我头晕..

zxoys

个人分析：
如果抓到的是人，最多说他是鬼49次，之后都是说人
如果抓到的是鬼，最多说他是人48次，之后都是说鬼
如果抓到的是人，最多说他是人50次，第50个说他是人的一定是人
如果抓到的是鬼，最多说他是鬼99次，第50个说他是鬼的一定是鬼，之后的人可以全排除，把剩下的重新排
最坏的情况，第99次听到第50个鬼，说人的都可以排除，突然想到，其实最多100次就能排查出来
在确定自己手里是鬼的前提下，之前说他是人的都可以排除了

如果鬼也说真话来隐藏自己的话
再排查下个
应该是50+49+。。。+2=1274次

zxoys

如果鬼也说真话来隐藏自己的话
再排查下个
应该是50+49+。。。+2=1274次

[ 本帖最后由 zxoys 于 2009-10-8 15:32 编辑 ]

siro

这题目怎么这么象雷顿教授。。。

linjinghui

zxoys

突然想到，其实最多100次就能排查出来
在确定自己手里是鬼的前提下，之前说他是人的都可以排除了

[ 本帖最后由 zxoys 于 2009-10-8 14:49 编辑 ]

々风妖々

原帖由 拽→强 于 2009-10-8 13:13 发表
最糟糕的是其实只有1个鬼 而且只会说假话 你一辈子都找不出

假如只有一个鬼,并且只说假话的话那就好找了..

随便设一个X,出现两种情况.

X为人的话,询问另外的99个而其中只有一个答案不一样(因为鬼只说假话..)

X为鬼的话,询问另外的99个中的2个,那么两个答案都将会是"鬼",因为人只说真话.

那么,最好的情况下X为鬼,只需要问2次.

最坏的情况是把人设为了X,那么需要问99次...




相对的,如果鬼只说真话,就比较麻烦一点,不过因为人也是只说真话的,把他们分成50组,每组两人,互相问就知道了.

所以最好的情况是问1次,最坏的情况是问50次...





本身这道题最难的地方就在于鬼不一定说真话,也不一定说假话..

拽→强

最糟糕的是其实只有1个鬼 而且只会说假话 你一辈子都找不出

zxoys

过来汗一下自己的数学水平，全还给老师了

々风妖々

原帖由 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次...

zxoys

原帖由 天才小猪 于 2009-10-7 23:09 发表
如果是要最快那就是50次就搞掂了

我答案是50~7200次之间，最倒霉，最糟糕的情况下7200次