好人 坏人

有n个人,其中超过半数是好人,剩下的是坏人
好人只说真话,坏人可能说真话也可能说假话
这n个人互相都知道对方是好人还是坏人

现在要你从这n个人当中找出一个好人来,只能通过以下方式:
每次挑出两个人,让这两个人互相说出对方的身份,
你根具两个人的话进行判断。

问通过何种方法才能最快的找出所有人的身份(最坏的情况下)

 

解法:

首先分析只有两个人的情况:a和b

1、a说b是好人,b说a是好人:则a和b是同样的人,同为好人或者同为坏人

2、a说b是好人,b说a是坏人:则a肯定是坏人,b不确定

3、a说b是坏人,b说a是好人:要么a好b坏,要么a坏b坏,则b肯定是坏的

4、a说b是坏人,b说a是坏人:要么a好b坏,要么a坏b好,要么a坏b坏。

那么现在就顺序的从n人中抽出一个人i来,和剩下的人来依次比较。

假设挑出来的坏人,那么最坏的情况前面n/2个都相互说是坏人,这样就无法判断了?

如果符合1的情况超过1/2,则i是好人

如果符合2,则i是坏人,去掉i,再取一个i

如果符合3,则把集合中的对应的人去掉,继续下一个

如果符合4的情况超过1/2,则i是坏人,去掉i,再取一个i

反复如此,可以找到所有人的身份。