| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2721 人关注过本帖, 1 人收藏
标题:数学归纳法经典问题
只看楼主 加入收藏
轮椅之星
Rank: 2
等 级:论坛游民
帖 子:18
专家分:42
注 册:2012-8-16
收藏
得分:2 
回复 10楼 beyondyf
题目有一点貌似说的不清楚。
1.如果不能排除“ 确定不是名人的客人” ,您说的好像有点问题,如果两个人中间有一个名人的话,只用询问一次就行了,假如A认识B,那么B就是名人,如果A不认识B,那么A就是名人。
    所以,当n=2时,只询问一次,就能确定谁是名人,您推导的公式不适用n=2的情况。

2.如果可以排除  的客人的话,我认为只要n-1次就够了。
    每次挑两个人,询问后可以排除一个客人,还剩下n-1个人。这是询问了一次。
    接下来的就能按以上逻辑,最后确定答案,是n-1次。
2012-10-11 10:17
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
最后一次强调。把题意看清楚再发言。不要跟非诚勿扰上的部分女嘉宾一样看了一两个词就下定论,把话看全了再说。

我的结论中说的是最多,不是必须。

每一组询问不一定只能排除一个人,也可能将两个人都排除。如果两个人都排除了他下一轮询问中这两人都不必要参与。

如果第一轮询问中就将n - 1个人都排除了,那可以直接判断第n个人是名人,无需继续询问。

所以,2*(n-1)是询问次数的上限,而下限是n-1。对于具体的一次聚会情况,实际询问次数将介于n-1与2*(n-1)之间。

重剑无锋,大巧不工
2012-10-11 11:56
冰冻零点
Rank: 3Rank: 3
来 自:西安电子科技大学
等 级:论坛游侠
帖 子:81
专家分:136
注 册:2012-9-18
收藏
得分:2 
回复 22楼 beyondyf
两个问题可以充分地排除一个人。按你的思路我们要排除n-1个人,所以最多是2(n-1)次。但是请这样考虑,我们先排除n-2个人,最多需要问2(n-2)。剩下两个人,只需问一次既可,即剩下最后AB两人,问A是否认识B,回答是则B为名人,否则A为名人。所以最多需要2n-3次。

好好学习,天天向上
2012-10-11 14:50
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:2 
回复 23楼 冰冻零点
这才是认真思考后的质疑。

你说的是对的,当只剩两人时,并肯定其中一人是名人(因为聚会中一定有一个名人),那只需问一次即可。我的结论是在配合原来那个3*(n-1)的形式。

有兴趣的话不妨就改变一下命题,如果聚会中可能没有名人,那最多需要询问多少次可以确定其中是否有名人及谁是名人。

重剑无锋,大巧不工
2012-10-11 15:54
zanzan1986
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:100
专家分:140
注 册:2011-2-22
收藏
得分:2 
回复 5楼 pangding
这个方法真的很妙啊!!!!!!!!!用二维矩阵来搞定了!!!!!!!!!!
2012-10-12 12:16
快速回复:数学归纳法经典问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020203 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved