w**t
发帖数: 23 | 1 n个人中，有一个人是名人，特征是他不认识其他人，然其他的人都认识他，问要怎样
最快找到这个名人，你只可以问A是否认识B这样的问题。。。
大家有想法吗? |
r**u
发帖数: 130 | 2 建个矩阵，找出除对角线外全是0（1）的行（列）？
【在 w**t 的大作中提到】
: n个人中，有一个人是名人，特征是他不认识其他人，然其他的人都认识他，问要怎样
: 最快找到这个名人，你只可以问A是否认识B这样的问题。。。
: 大家有想法吗?
|
r*******e
发帖数: 7583 | 3 http://c2.com/cgi/wiki?GraphSinkDetection
根据给的条件
每问一个问题可以排除掉一个人
问A是否认识B，如果认识，那么A不是名人；如果不认识，那么B不是名人
最多需要问n-1个问题
【在 w**t 的大作中提到】
: n个人中，有一个人是名人，特征是他不认识其他人，然其他的人都认识他，问要怎样
: 最快找到这个名人，你只可以问A是否认识B这样的问题。。。
: 大家有想法吗?
|
r******e
发帖数: 80 | |
i****d
发帖数: 35 | 5 最后应该还是要回头check一遍？
【在 r*******e 的大作中提到】
: http://c2.com/cgi/wiki?GraphSinkDetection
: 根据给的条件
: 每问一个问题可以排除掉一个人
: 问A是否认识B，如果认识，那么A不是名人；如果不认识，那么B不是名人
: 最多需要问n-1个问题
|
o*o
发帖数: 5155 | 6 no.
【在 i****d 的大作中提到】
: 最后应该还是要回头check一遍？
|
i****d
发帖数: 35 | 7 那么请问如果最后剩一个。。。你怎么确定所有人都认识他？
【在 o*o 的大作中提到】
: no.
|
o*o
发帖数: 5155 | 8 Why do you need to prove that?
【在 i****d 的大作中提到】
: 那么请问如果最后剩一个。。。你怎么确定所有人都认识他？
|
r*******e
发帖数: 7583 | 9 前提是一定有一个名人
如果不成立的话，就要加额外的检查
【在 i****d 的大作中提到】
: 那么请问如果最后剩一个。。。你怎么确定所有人都认识他？
|
i****d
发帖数: 35 | 10 嗯对~
【在 r*******e 的大作中提到】
: 前提是一定有一个名人
: 如果不成立的话，就要加额外的检查
|
b*******s
发帖数: 5216 | 11
问，连你自己在内，你一共认识几个人？
大于1的都不是
【在 w**t 的大作中提到】
: n个人中，有一个人是名人，特征是他不认识其他人，然其他的人都认识他，问要怎样
: 最快找到这个名人，你只可以问A是否认识B这样的问题。。。
: 大家有想法吗?
|
S******1
发帖数: 269 | 12 只要不认识任何人就是名人了啊。。。别人至少都认识名人 |
z**c
发帖数: 625 | 13 p[1..n]
if (p[2] knows p[1]) return p[1];
for (i = 2; i <= n; ++i)
if (p[1] knows p[i]) return p[i];
【在 w**t 的大作中提到】
: n个人中，有一个人是名人，特征是他不认识其他人，然其他的人都认识他，问要怎样
: 最快找到这个名人，你只可以问A是否认识B这样的问题。。。
: 大家有想法吗?
|
