赞
踩
Diogenes教授有n个被认为是完全相同的VLSI芯片,原则上它们是可以互相测试的。教授的测试装置一次可测二片,当该装置中放有两片芯片 时,每一片就对另一片作测试并报告其好坏。一个好的芯片总是能够报告另一片的好坏,但一个坏的芯片的结果是不可靠的。这样,每次测试的四种可能结果如下:
芯片A的结果 | 芯片B的结果 | 结论 |
B是好的 | A是好的 | 两片都是好的,或都是坏的 |
B是好的 | A是坏的 | 至少一块是坏的 |
B是坏的 | A是好的 | 至少一块是坏的 |
B是坏的 | A是坏的 | 至少一块是坏的 |
(1)将任何一片芯片与其它所有芯片进行比较,因为有多于n/2的芯片是坏的,且坏的芯片可以联合起来欺骗教授,则测试结果是不可靠的,无法判断出该芯片是好是坏。
(2)
1.随机的两两配对,则共有⌊n/2⌋对,分别测试。
2.如果测试结果为一好一坏,或者两坏,那么把这对丢弃;如果测试结果为两好,那么随意丢弃其中一个,留下一个。
3.重复以上操作,直至n<=2.
当n是偶数时:测试结果为一好一坏,或者两坏,丢弃后好芯片数都比坏芯片数多。如果测试结果为两好,那么好芯片的数量至少比坏芯片的数量多一对,随意丢弃一个时,好芯片的数量仍然多于坏芯片的数量。
当n是奇数时:单独操作,用剩下的芯片对其测试,判断其好坏。
(3)复杂度: 。根据主定理 。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。