芯片测试（分治）- 例题

转载自知乎

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。

问题描述：

给定n个芯片，（1）好芯片比坏芯片至少多一片；（2）两个芯片可以互相测出对方的好坏，好芯片可以测准，坏芯片不一定测准。从中选出一片好芯片。

思路分析：

角度一：随机选一片芯片，与其他芯片比较：

当芯片总数是偶数：好芯片数目大于等于 n/2+1 ， 如果选中的芯片是好芯片，剩下的超过一半（ n/2） 报好（结果一） ，如果选中的芯片是坏芯片，超过一半的报坏（结果二）；结果不是一半（及以上）报好就是一半（及以上）报坏，因此可以检测出选中的单芯片的好坏；

如果选中的芯片是奇数：好芯片数目大于等于 （n+1）/2 ，如果选中的是好芯片，剩下的至少芯片一半报好；如果选中的是坏芯片，超过一半报坏；结果不是一半（及以上）报好就是一半（及以上）报坏，因此可以检测出选中的单芯片的好坏；

仔细想一想，由于好芯片比坏芯片多，抽出一片好芯片，剩下的至少还有一半好芯片，根据他们测定的结果，可以得出判断；抽出一片坏芯片，那剩下的好芯片就更多了，也可以得出判断。

因此，采取蛮力算法：随机选一片，判断其好坏，如果是坏的，重复进行；最坏的情况是每一片都与其他片比较一遍，需要 O(n^2) 。

角度二：随机的两片比较有四种可能：

A片     B片
B好     A好   要么都好，要么都坏     
B好     A坏   至少坏一片
B坏     A好   至少坏一片 
B坏     A坏   至少坏一片

每种情况考虑四种情形：AB都好、 AB都坏 、一片好一片坏

第一种情况：设AB都好吻合，设AB都坏吻合，一片好一片坏矛盾，所以要么都好，要么都坏；

第二种情况：AB都好矛盾，AB都坏吻合，A坏B好吻合，A好B坏矛盾，所以至少坏一片；

其他两种情况同理，也是至少坏一片；

如果我们给芯片随便两两配对测量（先假设芯片数是偶数），都报好的任选一片，其他情况的全不选，从而选出新子集，如果新子集还满足原来集合的性质，就可以逐步缩小筛选的范围，不用一片一片去比。这时满足表达式 W(n) = W(n/2) + O(n) ，可以看出这个就是典型的分治算法——寻找相同的子问题，将原来的大问题分解后递归求解，复杂度为W(n) = O(n)。

新子集还满足原来集合的性质?

原来集合的性质：好芯片比坏芯片多；由于选取的芯片组有两种类型：都是好的，都是坏的，可以知道好的芯片组的数目多于坏的芯片组的数目，因此子集中好芯片还是比坏芯片多，因此满足条件。

那如果芯片数目是奇数怎么办？

当遇到芯片数目是奇数时，将轮空的（未分到组的）芯片采取角度一方法判断，好的话，结束程序，坏的话就丢弃该芯片。

伪码算法：

n <- 芯片总数
while n > 3 then:
    将 n 分为 n/2(默认向下取整) 组
    if n是奇数 then:
         轮空的芯片检测其好坏，好的话结束程序，坏的话丢弃
    对每个分组进行元素抽取，测试结果都好的随机抽一个，其余的丢弃
    n <- n/2
    if n == 3 then:
        ‍随机选取一片芯片比较一次
        if 都好 then 选择一片
        els‍e 选择剩下的一片
    if n<3 then:随机选择一片
        return