认真对待每一道算法题 之 找明星问题 - 淘宇瀚 - 淘宇瀚 - 博客园
n个人中只有一个明星，明星不认识其他所有的人，而其他人都认识明星，不是明星的人可能认识也可能不认识。你每次只可以问一个人是否认识另一个人这样的问题，问最少问多少次可以找出明星。
做法1：
将所有人站队，按照顺序（假如编号分别为1、2、3.。n），首先问1，2互相认识，有四种情况出现：
（1）1 认识 2，2不认识1， 认识别人的肯定不是明星，排除1；
（2）1 不认识2，2认识1， 根据（1）的道理，同样可以排除2；
（3）1与2 互相认识，可以断定，两个人都不是明星，随机删除一个就好；
（4）1与2 相互认识，同（3），随机删除一个就好；
接下来，将3号与之前1与2比较之后的剩余者进行同样方式的比较，依次类推，最后还剩余的那个就是明星了；
Read full article from 认真对待每一道算法题 之 找明星问题 - 淘宇瀚 - 淘宇瀚 - 博客园
No comments:
Post a Comment