名人问题 (Celebrity problem) - Yuwen's Hero - 博客频道 - CSDN.NET
问题：
在一个房间里有 N 个人，其中一个是名人，所谓名人就是大家都认识他，但是他不认识任何人。其它人可能认识房间里面另外的一部分人。你可以问任何人问题，但是问题只能是：你认识 X 吗，对方回答 Yes or No. 请问最少要问多少个问题才能把名人找出来？
分析：
我们把人编号，比如从1 到 N。
我们考虑最坏情况：你问每一个人是否认识 X ，如果大家都认识，那么 X 一定是名人，如果其中一个人说不认识，那么那个人一定不是名人。因为 X 的范围是 1 到 N， 所以，在最坏情况下，我们 要问 （N - 1）* N 个问题。
但是，有一种更好的方法。我们从1开始，依次问他是否认识他的下一个，比如 2， 如果 1 说认识，那么 1 一定不是名人，2 有可能是名人； 如果1 说不认识，2 一定不是名人，1 却有可能是名人。这是这个方法巧的地方。所以，不管1 回答是还是不是，我们都可以确定其中一个不是名人，然后，我们继续问 可能是名人那一位 是否认识 3， 然后依次下去，直到第 N 个人。这样我们就可以只要问 （N - 1） 个问题就可以把名人找出来。
Read full article from 名人问题 (Celebrity problem) - Yuwen's Hero - 博客频道 - CSDN.NET
No comments:
Post a Comment