当前位置: 代码迷 >> 综合 >> JAVA算法:聚会找人问题
  详细解决方案

JAVA算法:聚会找人问题

热度:20   发布时间:2024-01-15 19:16:52.0

JAVA算法:聚会找人问题

在一个房间里有 N 个人,其中一个是名人(Celebrity),所谓名人就是大家都认识他,但是他不认识任何人。其它人可能认识房间里面另外的一部分人。你可以问任何人问题,但是问题只能是:你认识 X 吗,对方回答: “Yes“ 或者  “No“。 请问最少要问多少个问题才能把名人(Celebrity)找出来?

我们可以将问题描述为表示参与方人员的数字/字符数组。我们还有一个假设函数haveknown(a,b),如果a知道b,返回true,否则返回false。


问题分析

  • 如果A认识B,那么A就不能成为名人。丢弃A,B可能是名人。
  • 如果A不认识B,那么B就不能成为名人。丢弃B,A可能是名人。
  • 重复以上两步,直到我们只剩下一个人。
  • 可以确定最后剩下的人就是我们要找的人,名人(Celebrity)。(为什么我们需要这个步骤?)

我们可以用Stack来验证名人。

  • 把所有名人都压入堆栈
  • 从栈顶弹出两人,根据HaveAcquaintance(A,B)的返回状态丢弃一人。
  • 把剩下的人压入堆栈
  • 重复以上步骤2和3,直到最后只有一个人留在堆栈中。
  • 检查Stack中的剩余人是否与其他人不认识/认识。

算法设计

package com.bean.algorithm.b