作业帮求一道简单题目的算法伪代码
来源：学生作业帮 编辑：作业帮 分类：综合作业 时间：2024/04/25 09:57:22
求一道简单题目的算法伪代码
在n个人中,只有一个人是名人（Celeberty）,所有人都认识他而他不认识任何其他n-1个人,其他n-1个人相互是否认识是随机的,现在要一个算法来找出这个名人.
要求是：只能问某个人“你认识他吗”,或者说是问A认识B吗,答案只有Yes 或 No,不能问A和B是否相互认识,最重要的一点,大O符号要是O(n).
PS：我已经有一个算法,可是大O符号是O(n log (n)),求高手给个更好的算法.
在n个人中,只有一个人是名人（Celeberty）,所有人都认识他而他不认识任何其他n-1个人,其他n-1个人相互是否认识是随机的,现在要一个算法来找出这个名人.
要求是：只能问某个人“你认识他吗”,或者说是问A认识B吗,答案只有Yes 或 No,不能问A和B是否相互认识,最重要的一点,大O符号要是O(n).
PS：我已经有一个算法,可是大O符号是O(n log (n)),求高手给个更好的算法.
可能的人k=第1人；
for（i=第二人;i不是最后一个人;i=下一个人)
{
if(k认识i==yes）
k=i
}
最后保留下来的一定是那个名人.
因为只有遇到名人,才能保证之后一定不会再碰见认识的人.
而在碰到名人之前,一定会遇到名人（假定你那随机之后一定有一个名人）,
那么k就会指向名人.
有点像脑经急转弯.
你的方法应该是两两相比较,然后比较结果再比较的算法吧.
再问：
文字太多了，还是发图片吧。。。。
再答： 恩。你的解法就是我说的那种两两比较后，再把结果拿来比较。 我的直觉告诉我好像是nlog n的复杂度，符合T（N）=2T(n/2)+k的模型。 但你这么算也是对的，这算是O(n)的 算法。 但是你n的系数比我的大，而且应该还有很多数据交换。 其实完全可以向我那样只向一个方向问，那么你的最后询问次数也是n，而不是2n。 我还谈不上大神。。。不过确实晚上做事效率高些。 干扰少点，可以安心写代码~
for（i=第二人;i不是最后一个人;i=下一个人)
{
if(k认识i==yes）
k=i
}
最后保留下来的一定是那个名人.
因为只有遇到名人,才能保证之后一定不会再碰见认识的人.
而在碰到名人之前,一定会遇到名人（假定你那随机之后一定有一个名人）,
那么k就会指向名人.
有点像脑经急转弯.
你的方法应该是两两相比较,然后比较结果再比较的算法吧.
再问：
文字太多了，还是发图片吧。。。。再答： 恩。你的解法就是我说的那种两两比较后，再把结果拿来比较。 我的直觉告诉我好像是nlog n的复杂度，符合T（N）=2T(n/2)+k的模型。 但你这么算也是对的，这算是O(n)的 算法。 但是你n的系数比我的大，而且应该还有很多数据交换。 其实完全可以向我那样只向一个方向问，那么你的最后询问次数也是n，而不是2n。 我还谈不上大神。。。不过确实晚上做事效率高些。 干扰少点，可以安心写代码~