[color=Red]3+5+……+49=624[/color]
[color=Red]分析[/color]
抽出两个人问话 会有3种情况:
1.两者都说对方是人 推论:两者都是人或两者都是鬼
2.两者都说对方是鬼 推论:两者都是鬼或一人一鬼
3.一人说对方是人 一人说对方是鬼 推论:同上
由上分析可知:双方都是人的情况只有情况1..
故 将出现情况2和情况3的两人都排除..
此时 人鬼数量都为偶数 并被你的抽取而两两分组
这样便可以采用"拆对造单"的思想来进行排除,进而缩小取值范围
[color=Red]步骤[/color]
最差的情况是原100个中52人48鬼
从100人(鬼)中随机舍去一个,然后随机抽取两个问话
抽到的情况最差的是只有一对问话是情况2或3
另外还剩一人 将剩下一人也舍去
此时 问话49次 舍去4者 还剩28组
接下来重复以上步骤
全部最差情况每次只舍去4这计算
最后一次剩3组人 1组鬼
问话3次 舍去2人2鬼 剩下4个全是人
故 根据等差数列求和得: 3+5+...+49=624
-------------------------------------------------------------------------------------
不知道有没错
最近数分和C程学的我头晕.. :ph34r: 求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内. [quote]原帖由 [i]々风妖々[/i] 于 2009-10-8 23:39 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11114528&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内. [/quote]
我也是突然想到的，你的算法，在最多第99次时，说假话的鬼会被暴露身份，因为人是不会说假话的，因为确定了自己手里的是鬼，那么说他是人的，岂不是都是鬼？
所以鬼只能说真话才能隐藏自己 [quote]原帖由 [i]々风妖々[/i] 于 2009-10-8 23:39 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11114528&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内. [/quote]
从计算的角度，你的算法是正确的，开始我也觉得是对的，但不知道为什么老让我有种哪里出错的感觉，后来突然想到，从现实角度就不对了 :ph34r: 你们两个无视我 [quote]原帖由 [i]与星独白[/i] 于 2009-10-9 12:19 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11115969&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
:ph34r: 你们两个无视我 [/quote]
你的算法没看懂，能说的浅显点不？ 如果要算最糟糕的情况就是有49个鬼
而且他们都是在说假话
而你前面49次抽到的都是鬼
所以你最遭要问的次数就是99+98+97+96+……+50=3725次 [quote]原帖由 [i]zxoys[/i] 于 2009-10-9 15:23 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11116709&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
你的算法没看懂，能说的浅显点不？ [/quote]
分组啊.. 两个一组 [quote]原帖由 [i]与星独白[/i] 于 2009-10-9 21:42 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11118107&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
分组啊.. 两个一组 [/quote]
如果是52和48，又偏偏都是人和人配，鬼和鬼配，鬼永远说对方是人，怎么办？ [quote]原帖由 [i]天才小猪[/i] 于 2009-10-9 21:30 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11118058&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
如果要算最糟糕的情况就是有49个鬼
而且他们都是在说假话
而你前面49次抽到的都是鬼
所以你最遭要问的次数就是99+98+97+96+……+50=3725次 [/quote]
这种算法不对，这样在第一轮就可以把说假话的鬼给排除掉了，你的方法只要100次就能把所有鬼排除，所以不是最糟糕的 那就换一下
最糟糕的情况就是有49个鬼
而且他们都是在说真话
而你前面49次抽到的都是鬼
那就是49×50=2450？ [quote]原帖由 [i]天才小猪[/i] 于 2009-10-11 14:21 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11123714&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
那就换一下
最糟糕的情况就是有49个鬼
而且他们都是在说真话
而你前面49次抽到的都是鬼
那就是49×50=2450？ [/quote]
每一轮可以排除一个鬼，所以是50+49+。。。。+2=[color=Red]1724[/color]次
为什么第一个是50呢，因为100个人（鬼）时要排查50次，确定一个鬼，然后去掉这个鬼，又从99个人（鬼）开始 就算剩下51个人（鬼）
但是你还是要问完50次才能确定你问的那个是人还是鬼 问要最快的找出一个人来，至少要多少次？(一定要考虑最坏的情况)
是不是有些矛盾？要最快问的是至少，但又要考虑最坏的情况，那不是至多吗？ [quote]原帖由 [i]zxoys[/i] 于 2009-10-10 20:27 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11121213&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
如果是52和48，又偏偏都是人和人配，鬼和鬼配，鬼永远说对方是人，怎么办？ [/quote]
最坏的情况就是52和48 这种情况一开始就踢掉一个 然后再按组抽 剩下的一个不用管他是人是鬼也都踢掉
鬼永远说对方是人无所谓 只要对方是人就肯定说你是鬼
在抽出的两个中 只要有一者说对方是鬼就把两个都踢掉
这样大胆踢掉不用担心人全部被你踢完 因为人比鬼多 风妖很好很强大，我看完题目已经晕了，数学白痴路过围观:lol: [quote]原帖由 [i]天才小猪[/i] 于 2009-10-12 21:21 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11128887&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
就算剩下51个人（鬼）
但是你还是要问完50次才能确定你问的那个是人还是鬼 [/quote]
人比鬼多，鬼的最大基数最大不会超过49，所以问50次，同理问完一轮去掉一个鬼后，最大基数不会大于48，也就是问49次就能确定 [quote]原帖由 [i]与星独白[/i] 于 2009-10-14 13:18 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11134752&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
最坏的情况就是52和48 这种情况一开始就踢掉一个 然后再按组抽 剩下的一个不用管他是人是鬼也都踢掉
鬼永远说对方是人无所谓 只要对方是人就肯定说你是鬼
在抽出的两个中 只要有一者说对方是鬼就 ... [/quote]
你这方法在人51鬼49这种单数情况下，怎么确定？因为并不能确定人和鬼的确切数字，除了知道人比鬼多外，并不知道确切数字的，所以假设情况下要考虑偶数和奇数都能适用 [quote]原帖由 [i]zxoys[/i] 于 2009-10-14 22:50 发表 [url=http://bbs.rohome.net/redirect.php?goto=findpost&pid=11136658&ptid=1000915][img]http://bbs.rohome.net/images/common/back.gif[/img][/url]
你这方法在人51鬼49这种单数情况下，怎么确定？因为并不能确定人和鬼的确切数字，除了知道人比鬼多外，并不知道确切数字的，所以假设情况下要考虑偶数和奇数都能适用 [/quote]
为什么不能用
用同样的方法
第一轮结束后就自动成对分组了
你自己想想是不是
用我剔除法 可以保证人和鬼的数目都是成对的
而且如果是人人组合的绝对不会被剔 只有人鬼和鬼鬼组合会被剔
这样保证了每次剔除的人的数目不会比鬼多 最多和鬼一样
那样剔到最后肯定只剩人了
页:
1
[2]