问一个智力题，网上找不到确切答案的

zxoys

有100个人与鬼，从外表很难区分开来。
只知道其中人的个数超过半数，剩下的都是鬼，而人只说真话，鬼可能说真话也可能说假话。
这100个人（鬼）互相都知道彼此是人还是鬼。
现在要你从这100个人（鬼）当中找出一个人来，只能通过以下方式：
每次挑出两位，让这两位互相说出对方的身份，你根据两位的话进行判断。
问要最快的找出一个人来，至少要多少次？(一定要考虑最坏的情况)

100个人与鬼，说的是人的数+鬼的数一共等于100。此题非脑急题~~。

ps：这题有点难度，大家弄清题意后，再好好想想

可以的话，说出你的算法

与星独白

原帖由 zxoys 于 2009-10-14 22:50 发表

你这方法在人51鬼49这种单数情况下，怎么确定？因为并不能确定人和鬼的确切数字，除了知道人比鬼多外，并不知道确切数字的，所以假设情况下要考虑偶数和奇数都能适用

为什么不能用

用同样的方法

第一轮结束后就自动成对分组了  

你自己想想是不是

用我剔除法  可以保证人和鬼的数目都是成对的

而且如果是人人组合的绝对不会被剔   只有人鬼和鬼鬼组合会被剔

这样保证了每次剔除的人的数目不会比鬼多  最多和鬼一样

那样剔到最后肯定只剩人了

zxoys

原帖由 与星独白 于 2009-10-14 13:18 发表

最坏的情况就是52和48  这种情况一开始就踢掉一个  然后再按组抽  剩下的一个不用管他是人是鬼也都踢掉

鬼永远说对方是人无所谓  只要对方是人就肯定说你是鬼

在抽出的两个中  只要有一者说对方是鬼就 ...

你这方法在人51鬼49这种单数情况下，怎么确定？因为并不能确定人和鬼的确切数字，除了知道人比鬼多外，并不知道确切数字的，所以假设情况下要考虑偶数和奇数都能适用

zxoys

原帖由 天才小猪 于 2009-10-12 21:21 发表
就算剩下51个人（鬼）
但是你还是要问完50次才能确定你问的那个是人还是鬼

人比鬼多，鬼的最大基数最大不会超过49，所以问50次，同理问完一轮去掉一个鬼后，最大基数不会大于48，也就是问49次就能确定

人生若只如初见

风妖很好很强大，我看完题目已经晕了，数学白痴路过围观

与星独白

原帖由 zxoys 于 2009-10-10 20:27 发表

如果是52和48，又偏偏都是人和人配，鬼和鬼配，鬼永远说对方是人，怎么办？

最坏的情况就是52和48  这种情况一开始就踢掉一个  然后再按组抽  剩下的一个不用管他是人是鬼也都踢掉

鬼永远说对方是人无所谓  只要对方是人就肯定说你是鬼

在抽出的两个中  只要有一者说对方是鬼就把两个都踢掉

这样大胆踢掉不用担心人全部被你踢完  因为人比鬼多

yinyin8023

问要最快的找出一个人来，至少要多少次？(一定要考虑最坏的情况)


是不是有些矛盾？要最快问的是至少，但又要考虑最坏的情况，那不是至多吗？

天才小猪

就算剩下51个人（鬼）
但是你还是要问完50次才能确定你问的那个是人还是鬼

zxoys

原帖由 天才小猪 于 2009-10-11 14:21 发表
那就换一下
最糟糕的情况就是有49个鬼
而且他们都是在说真话
而你前面49次抽到的都是鬼
那就是49×50=2450？

每一轮可以排除一个鬼，所以是50+49+。。。。+2=1724次
为什么第一个是50呢，因为100个人（鬼）时要排查50次，确定一个鬼，然后去掉这个鬼，又从99个人（鬼）开始

天才小猪

那就换一下
最糟糕的情况就是有49个鬼
而且他们都是在说真话
而你前面49次抽到的都是鬼
那就是49×50=2450？

zxoys

原帖由 天才小猪 于 2009-10-9 21:30 发表
如果要算最糟糕的情况就是有49个鬼
而且他们都是在说假话
而你前面49次抽到的都是鬼
所以你最遭要问的次数就是99+98+97+96+……+50=3725次

这种算法不对，这样在第一轮就可以把说假话的鬼给排除掉了，你的方法只要100次就能把所有鬼排除，所以不是最糟糕的

zxoys

原帖由 与星独白 于 2009-10-9 21:42 发表

分组啊.. 两个一组

如果是52和48，又偏偏都是人和人配，鬼和鬼配，鬼永远说对方是人，怎么办？

与星独白

原帖由 zxoys 于 2009-10-9 15:23 发表

你的算法没看懂，能说的浅显点不？

分组啊.. 两个一组

天才小猪

如果要算最糟糕的情况就是有49个鬼
而且他们都是在说假话
而你前面49次抽到的都是鬼
所以你最遭要问的次数就是99+98+97+96+……+50=3725次

zxoys

原帖由 与星独白 于 2009-10-9 12:19 发表
你们两个无视我

你的算法没看懂，能说的浅显点不？