| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2721 人关注过本帖, 1 人收藏
标题:数学归纳法经典问题
只看楼主 加入收藏
luckyning
Rank: 1
等 级:等待验证会员
帖 子:2
专家分:0
注 册:2012-10-3
结帖率:0
收藏(1)
已结贴  问题点数:20 回复次数:24 
数学归纳法经典问题
问题:
在一个聚会上,如果所有的客人都认识其中的一位客人,而这位客人却不认识其他任何一个人,则这个人就称为名人,在一个聚会上,最多只有一个名人,一位若有两个名人,则他们必然相互认识,某个特定的聚会上也可能没有名人,你的任务是在一个聚会上去找一个名人,如果该聚会确实有名人的话,而你只允许向每个客人提问一种类型的问题---询问他是否认识灵位一名客人,每个客人必须如实回答你的问题。利用数学归纳法证明:若聚会上有n位客人,且有一位名人,那么你只需询问3*(n-1)次客人,你就能找到这位名人。
那位高手有思路呀,多谢了

[ 本帖最后由 luckyning 于 2012-10-3 14:02 编辑 ]
搜索更多相关主题的帖子: 数学归纳法 聚会 
2012-10-03 14:01
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
你确信没打错字是3 * (n - 1) ?

我分析了一下,应该最多只需要 2 * (n - 1) 次就够了。

重剑无锋,大巧不工
2012-10-04 11:42
luckyning
Rank: 1
等 级:等待验证会员
帖 子:2
专家分:0
注 册:2012-10-3
收藏
得分:0 
回复 2楼 beyondyf
恩,是3*(n-1),能否说下思路?谢啦
2012-10-05 11:03
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
我可以证明它是2*(n-1)。

如果相信我的结论并想看证明过程,20分全加到这个帖子上。

如果你坚持它是3*(n-1),请告诉我这道题的出处。

如果出自某本书,告诉我书名 书号(ISBN) 作者,以及这道题在书中的位置。

如果是你们老师布置的作业,请转达我的意见。

如果他依旧坚持,请告诉他我很鄙视他。

当然,最大的可能性还是你把题搞错了。你帖子里还有4个错别字。

[ 本帖最后由 beyondyf 于 2012-10-5 15:42 编辑 ]

重剑无锋,大巧不工
2012-10-05 15:40
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
楼主可以这么考虑这个问题。

把所有人的相互认识关系搞清楚,是不是可以用一个表格来描述。比如:
  A B C
A 1 1 0
B 0 1 0
C 0 0 1
表示 A B C 三个人中,只有 A 认识 B,而且其它人都互相不认识了。至于主对角线上的点,你写什么都无所谓。
如果有名人,那么所有人都认识它,它所在的那一列就都为1;又它谁也不认识,所在它所在的行全为 0。

现在问楼主你有好的方法能在表中把满足条件的人找出来吗?
2012-10-07 07:21
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
和pangding交流也很久了,还不知道该怎么称呼?

楼主在这里钓鱼呢。这也是我卖关子不回答的原因,不想浪费激情。

版主如果对这个问题有兴趣的话可以把贴子转到C区,毕竟那里人多些。

刚意识到任多版版主的一个好处,可以在这些版块间任意转移贴子。

我开始想争取一下这里的版主了

可以将这里有趣的贴子移到C区讨论——那里人多,便于集思广益。

可以将C区有价值的算法类贴子移到这里保存——这里人少的一个好处是灌水混分的也少。

重剑无锋,大巧不工
2012-10-07 09:51
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
哦?移过来了,那得顶一下。

重剑无锋,大巧不工
2012-10-07 18:03
姻脂梦
Rank: 6Rank: 6
等 级:侠之大者
帖 子:264
专家分:424
注 册:2012-7-3
收藏
得分:2 
学习学习
2012-10-08 21:37
ly2222
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:217
专家分:618
注 册:2012-6-15
收藏
得分:2 
学习了
2012-10-08 21:55
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
呵呵,今天从小曹那里学到了新东西,非常愉悦。

这个题目转到这里也两天了,不卖关子了,说说我的想法。

在聚会上随机选两个人,问两人是否认识对方。这是问了两次。

设这两人为A和B。

如果A认识B,B不认识A,那么A不是名人,B可能是名人。

如果A不认识B,B认识A,那么B不是名人,A可能是名人。

如果A认识B,B也认识A,那么A、B都不是名人。

如果A不认识B,B也不认识A,那么A、B都不是名人(这里解释一下,如果他们中有一个是名人,那么另一个肯定认识他)。

由此,经过两次提问,我们至少可以排除其中一人肯定不是名人。

这样,我们将N位客人两两一组如上提问,问过N个问题之后,我们可以排除N/2不是名人的人。

各位先不要纠结N是奇数的情况,或者说实际操作时多出的一个不问问题。

之后,对剩下的N/2人再两两一组如上提问。

这样每一轮问的问题数构成一个等比数列 N、N/2、N/4...

直到最后问到只剩两个人,再如上提问,即可确认谁是名人(或者没有名人也是可以确认的)。

如此,这个数列的长度为logN(注意,这里logN的底是2,它可能是个小数,先不要纠结在这里,听我慢慢道来)

那么这数列的前logN项的和为

S = N * (1 - (1/2)^logN) / (1 - 1/2)
  = 2 * (N - N/(2^logN))
  = 2 * (N - N/N)
  = 2 * (N - 1)

写这个罗嗦是会了让大家看到2^logN这一步变化,虽然logN可能是小数,但2^logN是个精确的整数,即 N。

由此,得到结论,对于有N位客人的聚会,最多只需2 * (N - 1) 次提问即可确定名人是谁。

我想可能有人还在为logN而困惑。好,现在再用数学归纳法证明一下这个结论。

当N = 1时,聚会就一个人,一个人的聚会还有什么名人不名人的? 也不需要问,所以 f(0) = 2 * (1 - 1) = 0,结论成立

当N = 2时,f(2) = 2 * (2 - 1) = 2,即问两次可以确定名人。根据上文开头的论述可知,结论成立

现在假设当N = k时,结论也成立,即 f(k) = 2 * (k - 1)

那么当 N = k + 1时

我们可以通过f(k)次提问,排除其中k - 1个人,将剩下这位可能是名人的人与还未参与问答的第k + 1人组成一组问是否认识对方,这样可以确定他们中谁是名人



f(k + 1) = f(k) + 2
         = 2 * (k - 1) + 2
         = 2 * ((k + 1) - 1)

由此,当N = k + 1时,结论仍成立

综上所述 f(N) = 2 * (N - 1) 对于任意的N(N > 0)都成立

证毕。

重剑无锋,大巧不工
2012-10-09 00:51
快速回复:数学归纳法经典问题
数据加载中...
 
   



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

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