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

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

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

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

可以的话，说出你的算法

zxoys

浆糊会员

Rank: 1

UID: 301632
帖子: 1354
精华: 0
威望: 64
阅读权限: 100
性别: 男
注册时间: 2005-7-23

2^#

发表于 2009-10-7 21:43 | 显示全部帖子

我之前也在计算中，分析到一个结论，随机的挑选出其中一个,并设其为"X"
第一次筛选中，第50个说他是人的，他一定是人，第50个说他是鬼的，一定是鬼
如果选中的是鬼，那么下次筛选可以去掉一个鬼
个人分析：
如果抓到的是人，最多说他是鬼49次，之后都是说人
如果抓到的是鬼，最多说他是人48次，之后都是说鬼
如果抓到的是人，最多说他是人50次，第50个说他是人的一定是人
如果抓到的是鬼，最多说他是鬼99次，第50个说他是鬼的一定是鬼，之后的人可以全排除，把剩下的重新排
最坏的情况，第99次听到第50个鬼，说人的都可以排除，突然想到，其实最多100次就能排查出来
在确定自己手里是鬼的前提下，之前说他是人的都可以排除了

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

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

TOP

zxoys

浆糊会员

Rank: 1

UID: 301632
帖子: 1354
精华: 0
威望: 64
阅读权限: 100
性别: 男
注册时间: 2005-7-23

3^#

发表于 2009-10-7 22:17 | 显示全部帖子

个人分析：
如果抓到的是人，最多说他是鬼49次，之后都是说人
如果抓到的是鬼，最多说他是人48次，之后都是说鬼
如果抓到的是人，最多说他是人50次，第50个说他是人的一定是人
如果抓到的是鬼，最多说他是鬼99次，第50个说他是鬼的一定是鬼，之后的人可以全排除，把剩下的重新排
最坏的情况，第99次听到第50个鬼，说人的都可以排除，再算

从99个开始，这时鬼最多48个，又很不幸，又只排除了他，本次筛选98次
从98个开始，这时鬼最多47个，又很不幸，又只排除了他，本次筛选97次
从97个开始，这时鬼最多46个，又很不幸，又只排除了他，本次筛选96次
从96个开始，这时鬼最多45个，又很不幸，又只排除了他，本次筛选95次
从95个开始，这时鬼最多44个，又很不幸，又只排除了他，本次筛选94次
。。。。。

如果每次都是鬼，其他都未知道

再算算

[ 本帖最后由 zxoys 于 2009-10-7 22:45 编辑 ]

TOP

zxoys