Monthly Archives: October 2010

算法导论题解: 4-6 VLSI Chip Testing

前几天面试的时候被问到一个涉及Master Theorem的题,于是今天把算法导论重新拿出来看了一下,发现了这道很有趣的题,以前居然没有注意。最近智商下降得厉害,想了N久才做出来,若有错请指出。

有N个人,分为好人和坏人两种,每次你可以挑两个人出来让他们互相指识彼此是好还是坏。好人一定说实话,坏人会乱说。现在你要从他们里面找出一个肯定是好人的。一共有三问:(1)证明若好人数目不超过N/2,则坏人们总可以通过故意捣乱,让你找不出正确答案。(2)证明若好人数大于N/2,存在一种方法可以通过floor(N/2)次判断使问题规模缩小到最多只有原来的一半。(3)证明若好人数大于N/2,可以用theta(N)次判断找出一个好人。

实际上问题的提示很强了,大致思路就是每次把问题缩小一半而已。

首先我们把情况列一下:如果两人互称对方是好人,那么两人同好或同坏;如果A说B好但B说A坏,那么A一定是坏人,B的好坏未知;如果两人互称对方是坏人,那么两人中至少有一个坏人。

首先我们试图证明第2问。因为好人比坏人多,所以我们是不怕“同归于尽”的,于是方法如下:把N个人任意两两组对,组成floor(n/2)对,如果是奇数的话就余出一个人。让他们互相指认,如果两人互称对方好人,随便挑其中一个杀掉;如果两人互称对方坏人,两个全杀掉;如果A称B好人但B称A坏人,把A杀掉。这样会发现人数至少缩小了一半,下面就是要证明剩下的人里仍然是好人占多数。

下面先考虑N是偶数的情况,此时一共组成了N/2对,每一对无外乎是好人遇好人,好人遇坏人,坏人遇坏人三种情况。设好人遇好人的有a对,好人遇坏人的有b对,坏人遇坏人的有c对,那么好人一共有2a+b个,坏人共有2c+b个。因为好人多,所以有2a+b>2c+b,即a>c。

如果我按照上面的规则杀人,那么当好人遇到坏人时,坏人应该说对方是坏人,这样还可以拼个同归于尽,不然他就白死了。当坏人遇到坏人时,两个坏人不管怎么说也至少要死一个。当好人遇到好人时,两个好人也要死一个。也就是说,如果坏人采取最佳策略,那么好人会死a+b个,坏人会死c+b个,于是好人还剩a个,坏人还剩c个,由前面已得a>c,所以剩下的还是好人多。

如果N是奇数,情况会复杂一些。此时有一个人会余出来,我们把这个余出来的人放在一旁观战。如果以后又出现了奇数个人,再让余出来的人替换掉原来观战的人。如果最后场上剩了一人(不管有没人观战),那个人就是好人。如果最后场上没人了,这时一定有人观战,观战的那个就是好人。这个方法的正确性在于,在任一时刻,如果场上好人和坏人数相同,观战的必然是好人。如果观战的是坏人,场上好人数必大于坏人数。(证明留给读者;p)

可见每轮过后最多剩下一半的人,所以第2问得证。然后第3问也就显然了,因为N+N/2+N/4+… = theta(N)

最后说一下第一问,如果坏人不比好人少,设好人有x个,坏人有y个且y>=x,那么我们可以让其中的x个坏人伪装好人。具体来讲,设好人集合为A,假好人集合为B,剩下的坏人为C(可以为空集),我们知道A集合里的人会说A集合里的人好,会说B,C都坏。坏人们可以商量好了让B集合的人都说B好,说A,C坏,让C说A,B都坏(或者都好)。这样你就无法区分A,B集合到底谁好谁坏了,因为他们的表现是完全一样的。