名人问题

来自计算思维百科
跳转至: 导航搜索
名人问题1.png

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

基本概念

假设有一6人的人群,分别为A、B、C、D、E、F,我们最少要问多少个问题才能找出其中的名人?

解决方案

方案一

对A,问B、C、D、E、F是否认识A;

对B,问A、C、D、E、F是否认识B;

对C,问A、B、D、E、F是否认识C;

对D,问A、B、C、E、F是否认识D;

对E,问A、B、C、D、F是否认识E;

对F,问A、B、C、D、E是否认识F。

按照这种方式,对每个人我们需要问5个问题,一共6个人,所以最坏的情况我们要问5×6=30个问题。

运用的计算思维

蛮力法找出名人,运用到机械化的思维方式。

方案二

假设6人人群中,D是名人。且6人认识关系如下,A→B表示A认识B。

名人问题2.png

我们从A开始,

第一步,问A是否认识B,A说认识,那么 A一定不是名人,B有可能是名人;

第二步,问B是否认识C,B不认识C,那么B有可能是名人;

第三步,问B是否认识D,B认识D,那么D有可能是名人;

第四步,问D是否认识E,D不认识E,那么D有可能是名人;

第五步,问D是否认识F,D不认识F,那么D有可能是名人。

第六步,如果人群中必存在一个名人,那么我们进行到第五步已经找出D是名人,否则我们需要再询问A、C、E、F看他们是否认识D,还要询问D是否认识A、B、C,如果A、C、E、F都认识D且D不认识A、B、C,那我们就能确定,D是名人。

所以,运用这种方式,我们最少需要问6-1=5个问题,最多也不会多于5+4+4=13个问题。

运用的计算思维

这种方法体现了计算思维的启发式特点。

方案三

第一步,把A、B、C、D、E、F两两分组,A和B,C和D,E和F。

第二步,对每一组问相互认不认识,如果都认识,都不是名人,排除;如果都不认识,这里面没有名人,如果其中一个认识另一个,则将认识的排除,另一个加入候选人集合里。这样,经过6次提问,候选人减少了一半。重新分组,提问,继续到只剩下一个人,就是名人。所以,问上12次,就可以找到唯一的候选人,再对他进行确认,就可以了。

运用的计算思维

分组的方式有效的减少了询问的次数,运用的是计算思维的分解特点。