算法导论 4.6

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

a)证明若少于 n/2 的芯片是坏的,在这种成对测试方式下,使用任何策略都不能确定哪个芯片是好的.

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

c)假设有多于 n/2 的芯片是好的,证明好的芯片可用 O(n) 对测试找出.

分析:

a)比较显然.略.

b)本题要求证明 n/2 对测试就能使问题的规模降至近原来的一半.所以要考虑的是怎么降低待测芯片的规模,而且还能继续可解.也就是需证明剩下的近一半中,仍然有多于1/2 的芯片是好的. 分两种情况讨论:

如果 n 是偶数,则把它为成 n/2 对.分别测试每一对.如果出现结果2,3,4.则将两片都暂时搁置.如果是结果1,则随意把其中一片搁置.因为有大于1/2 的芯片是好的,所以肯定总是能出现结果为1的一对芯片.设好的芯片 有 k 个,坏芯片 n-k个,分对时有 r 个坏芯片跟好芯片分成一对. k>n-k>=r. 则剩余的好芯片为 (k-r)/2, 剩余的坏芯片至多为 (n-k-r)/2,(当每对坏芯片相遇结果都是1的时候).显然 (k-r)/2 >(n-k-r)/2 .得证.

如果 n 是奇数,则先提一片(设代号为A),剩下的n-1片变为偶数,这在n-1片中,有好片>=坏片,然后按数偶数的情况处理.设经处理后剩下 q 片. 根据上面的步骤易知.在这 q 片中,好片不少于坏片.

现在又为两种情况: 1) q 为奇数: 这时 q 中的好片肯定多于坏片,将A 搁置.
2) q 为偶数: 这时 q 中的好片不少于坏片.若好片等于坏片,反推易知 A 为好片.将 加入 q 中.得证.

c)用b)方法找出一个好片对全部芯片做测试即可.显然只用O(n)对即可得出答案.
看到网上都没有递归式的证明，我证一下。

T(n)表示n个芯片需要找1个好芯片。

T(n/2)表示n/2个芯片需要找一个好芯片。

n/2表示需要n/2次比较n/2对芯片。

所以T(n)=T(n/2)+n/2;

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/atyuwen/archive/2007/10/09/1817600.aspx