【名人问题】有 n 个人他们之间是否认识用邻接矩阵表示(1表示认识,0表示不认识),并且 A 认识 B 并不意味着 B 认识 A,名人定义为他不是认识任何人且所有人都认识他的人。求出所有名人。
题目
n个人中的名人是指这样一个人:他不认识别人,但是每个人都认识他。任务就是找出这样一个名人,但只能通过询问“你认识他/她吗?”这种问是来完成。设计一个高效算法,找出该名人或者确定这群人中没有名人。你的算法在最坏情况下需要问多少个问题?
一、思路
根据题目知道,所有人都要认识名人,名人所有人都不认识。所以只能有一个名人。
用二维数组arr[i][j] 表示 i 是否认识 j
------arr[i][j] =1表示 i 认识 j
------arr[i][j] =0表示 i 不认识 j
所以思路就是:
------arr[i][j] =1时,i 一定不会是名人,j暂时无法判断。
------arr[i][j] =0时,j 一定不会是名人,i 暂时确定不了。
即if(arr[i][j] ==1)我就可以把编号为 i 的人丢掉了,反之丢掉j。
我没有写不存在名人的情况,名人的位置为输入的编号。其他人对应的------arr[i][j] 随机取的值。
按照上面的思路,如果名人不存在的情况不能确定栈中最后的人是不是名人,还需遍历判断一下。
二、题解代码
public static int select(int arr[][],int n) {
/*
* 查找名人
* arr[i][j]=1表示i认识j
* arr[i][j]=0表示i不认识j
* */
if (n<=1)
return 0;
int count = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) stack.push(i);
while (stack.size() > 1) {
int a = stack.pop();
int b = stack.pop();
count++;
if (arr[a][b] == 1) {
stack.push(b);
} else stack.push(a);
}
id = stack.pop();
return count;
}
测试数据
4
请输入名人所在编号:2
1 0 1 1
0 1 1 0
0 0 0 0
0 0 1 0
名人编号为2
已询问3次
完整代码:
public class text4 {
static int id=0;//名人编号;
public static void main(String[] args) {
int n=new Scanner(System.in).nextInt();//n个人
int count=0;//记录询问次数;
int arr[][]=getArr(n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
count=select(arr,n);
System.out.println("名人编号为" + id);
System.out.println("已询问"+count+"次");
/* if (count>0){
System.out.println("名人编号为" + id);
}else
System.out.println("没有名人");
System.out.println("已询问"+Math.abs(count)+"次");*/
}
public static int [][] getArr(int n){
/*
* 初始化矩阵
* 生成矩阵*/
Random random=new Random();
int arr[][]=new int[n][n];
System.out.print("请输入名人所在编号:");
int loca=new Scanner(System.in).nextInt();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//arr[i][j]=new Scanner(System.in).nextInt();
arr[i][j]=random.nextInt(2);
}
}
for(int i=0;i<n;i++){
arr[i][loca]=1;
arr[loca][i]=0;
}
return arr;
}
public static int select(int arr[][],int n) {
/*
* 查找名人
* arr[i][j]=1表示i认识j
* arr[i][j]=0表示i不认识j
* */
if (n<=1)
return 0;
int count = 0;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) stack.push(i);
while (stack.size() > 1) {
int a = stack.pop();
int b = stack.pop();
count++;
if (arr[a][b] == 1) {
stack.push(b);
} else stack.push(a);
}
id = stack.pop();
/* for (int i = 0; i < n; i++) {
count++;
if (i != id && (arr[id][i] == 1 || arr[i][id] == 0)) {
return count * -1;
}
}*/
return count;
}
}