分治法之芯片测试

最近在看算法导论时，看到了这道芯片测试的题，想了很久，总结一下我的思路

一、问题描述

Diogenes教授有n个被认为是完全相同的VLSI芯片，原则上它们是可以互相测试的。教授的测试装置一次可测二片，当该装置中放有两片芯片时，每一片就对另一片作测试并报告其好坏。一个好的芯片总是能够报告另一片的好坏，但一个坏的芯片的结果是不可靠的。这样，每次测试的四种可能结果如下：

b）假设有多于n/2的芯片是好的，考虑从n片中找出一片好芯片的问题。证明n/2对测试就足以使问题的规模降至近原来的一半。

c）假设多于n/2片芯片是好的，证明好的芯片可用Θ(n)对测试找出。给出并解答表达式测试次数的递归式。

二、题干解读

1. 当两个芯片都报告是好的，如果其中一个A是坏的，因为另一个B说A是好的，所以B也是坏的
2. 当两个芯片的报告一好一坏时：
   1. 说对方好的那个芯片一定是坏的：假设A说B是好的，B说A是坏的，若A是好的，则B是好的，那么B说A是坏的就自相矛盾了，所以A一定是坏的。
   2. 说对方坏的那个芯片可能是好的，也可能是坏的：经过上面的分析，A一定是坏的，那么A说的就不可信（可能是对的可能是错的），那么B说A是坏的，B好的坏的都有可能
3. 当两个芯片的报告都是坏的时：
   1. 首先不可能两个都是好的
   2. 若一个是好的：假设A是好的，则A说B是坏的，成立；B是坏的，所以还不管B的说辞
   3. 两个都是坏的，就无所谓他们说啥了

三、算法分析

对于问题a，采用穷举法，将任何一片芯片与其它所有芯片进行比较，因为有多于n/2的芯片是坏的，且坏的芯片可以联合起来欺骗教授，则测试结果是不可靠的，无法判断出该芯片是好是坏。

对于问题b和c，先假设：设有a个好的芯片数，b个坏的芯片数，z对测试结果为全好的测试对，其中芯片（注意这里是芯片全为好的，不是测试结果为好的）全是好的测试对为x，芯片全为坏的测试对为y，x+y=z。

分治算法设计思想

这里先说明一下前提：好芯片比坏芯片至少多1片！（以下例子，想不明白可以假设总共有4片或者6片芯片）

一、随机的两两配对，则共有⌊n/2⌋对，分别测试。

二、根据问题描述：

（1）如果测试结果为一好一坏，或者两坏，那么把这对丢弃：

• 很好理解，本来好的比坏的多，丢一个好的一个坏的，那么好的还是比坏的多，丢两个坏的就更不用说了

（2）如果测试结果为两好，那么随意丢弃其中一个，留下一个：

• 解释：这样做的主要目的是减小芯片的规模，经过第一步后，现在就剩两个都报告好的情况了（因为好的芯片比坏的芯片多，所以不存在所有的芯片对均测试为一好一坏），这种情况一对的两个芯片要么都是好的，要么都是坏的，那么从每对芯片中随意扔一个，最后好的芯片还是比坏的芯片多，但芯片数减少了一半

（3）这里要考虑芯片为奇数的情况：

• 若n为奇数，则剩余一个芯片没有配对。那么这个时候，就要根据第（2）步中测试结果为两好的芯片对数z进行判断：若z为奇数，丢弃这个芯片；若z为偶数（0也是偶数），留下这个芯片。
  • 解释：（a）当z为奇数时，假设最坏的情况，即最后剩的那一个芯片是好的，假设前面（z-1）对的好芯片与坏芯片数相同，那么现在就剩一对芯片了，这对芯片要么都是好的，要么都是坏的，如果是坏的，则好的芯片数比坏的芯片数少一，不成立，则这对芯片都是好的。即当z为奇数时，好芯片对数-坏芯片对数>= 1对，即好芯片数-坏芯片数>= 2，丢掉一半后，好芯片数-坏芯片数>=1(见下图)；那么把最后多出来的一个芯片必须丢掉，最后好的芯片还是比坏的芯片多
  • （b）若z为偶数（0也是偶数），还是假设最坏的情况，即这z对芯片好的与坏的一样多，那么这多出来的一片必是好的；若多出来的这一片是坏的，那么z对芯片中，好的芯片对数-坏的芯片对数>=2对，即好芯片数-坏芯片数>= 4，减半后，好芯片数-坏芯片数>= 2，即使放进来一个坏芯片，最后好的芯片还是比坏的芯片多

这样操作后，留下的好芯片数一定还是大于坏的芯片数的，且经过⌊n/2⌋对测试后，原问题的规模降低了近一半（解决了问题(b)）。

三、 重复第（二）步，当n<=2时，就只剩下了好的芯片。

因为始终是好芯片数多于坏芯片数，那么当n<=2时，就只有好的芯片了

总结：

测试结果为一好一坏或者两坏的芯片对中至少一片是坏的，把这对丢弃能保证剩下的芯片中好芯片的数量仍大于坏芯片的数量。

测试结果为全好的，这对芯片有可能全为好，有可能全为坏，随意丢弃其中一个，留下 一个。

设好芯片的对数为x，坏芯片的对数为y。考虑n的情况：

      若n为偶数，则x>y，所以留下的好芯片数还是大于坏的芯片数；

      若n为奇数，则剩余一个没有配对的芯片。考虑z的情况：

           若z是奇数，则x>y，丢弃这个芯片，这样留下的好芯片数还是大于坏的芯片数；

           若z是偶数，考虑这个芯片的情况：

                若芯片是好的，则x>=y，留下这个好的芯片，这样留下的好芯片数还是大于坏的芯片数；            

                若芯片是坏的，则x-y>=2，留下这个坏的芯片，这样留下的好芯片数还是大于坏的芯片数。

综上所述，留下的好芯片数一定还是大于坏的芯片数的。

复制代码

对于问题c：采用b中的操作方法，递归式为：f(n) = f(n/2) + n/2。这个递归式符合主定理中的第三种情况，所以好的芯片可用Θ(n)对测试找出。

四、代码实现

class Test {
    public static void main(String[] args) {
    	//用数组来存储芯片，1代表为好的芯片，0代表为坏的芯片，下面的数组总有23个芯片，12个为好的
        int[] arr = {1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1};
        System.out.println(Arrays.toString(getRight(arr,arr.length)));
    }

    //定义一个测试平台，来模拟题干中的测试装置，好的芯片输出对的，坏的芯片随机输出
    public static boolean[] judge(int x, int y) {
        boolean[] result = new boolean[2];
        if (x == 1 && y == 1) {
            result[0] = true;
            result[1] = true;
        } else if (x == 1 ^ y == 1) {
            result[0] = false;
            result[1] = ((int) (Math.random() * 2)) == 1;
        } else {
            result[0] = ((int) (Math.random() * 2)) == 1;
            result[1] = ((int) (Math.random() * 2)) == 1;
        }
        return result;
    }

    //返回一个正确的芯片
    public static int[] getRight(int[] arr,int length) {
    	//当芯片个数小于等于2时，均为好的芯片，返回
        if (length<= 2) {
            int[] z = new int[length];
            for (int i = 0; i < length; i++) {
                z[i] = arr[i];
            }
            return z;
        }
        //这里用数组存储选出来的芯片，数组定义为最坏情况下的长度，其它情况数组后边可能有多余的位数
        //所以用length来标明数组中的有效长度
        int[] tmp = new int[length / 2 + 1];
        boolean[] result = null;//这个数组用来接收测试结果

        int point = 0;//记录选出来的芯片个数
        //芯片两两为一组，进行测试
        for (int i = 0; i < length-1; i += 2) {
            result = judge(arr[i], arr[i + 1]);
            if (!result[0] ^ result[1]) {
                //两个芯片都测试为好的情况，则随机选出其中一个芯片
                int x = (int) (Math.random() * 2);
                tmp[point] = arr[i + x];
                point++;
            }
        }
        //考虑总个数为奇数的情况
        if (length % 2 == 1) {
        	//这时要根据选出来的个数进行判断，偶数就加进去，奇数就扔掉
            if (point % 2 == 0) {
                tmp[point] = arr[length - 1];
                point++;
            }
        }
		//递归，继续两两进行测试，直到芯片个数少于3个
        return getRight(tmp,point);
    }
}
复制代码