算法导论习题4-5：芯片检测 - groovy2007的专栏 - 博客频道 - CSDN.NET
Diogenes 教授有n个被认为是完全相同的VLSI芯片，原则上它们是可以互相测试的。教授的测试装置一次可测试二片，当该装置中放有两片芯片时，每一片就对另一片作测试并报告其好坏。一个好的芯片总能够正确的报告另一片的好坏，但一个坏的芯片的结果就是不可靠的。这样，每次的测试的四种可能结果如下：
A芯片报告 B芯片报告 结论
--------------------------------------------------------
B是好的 A是好的 都是好的，或都是坏的
B是好的 A是坏的 至少一片是坏的
B是坏的 A是好的 至少一片是坏的
B是坏的 A是坏的 至少一片是坏的
a)证明若不少于 n/2 的芯片是坏的,在这种成对测试方式下,使用任何策略都不能确定哪个芯片是好的.
b)假设有多于 n/2 的芯片是好的,考虑从 n 片中找出一片好芯片的问题.证明 n/2 对测试就足以使问题的规模降至近原来的一半.
c)假设有多于 n/2 的芯片是好的,证明好的芯片可用 O(n) 对测试找出.给出并解答表达测试次数的递归式。
第一问证明如下：将芯片分为3组，(a)好的 (b)数量和a组相同的坏的 (c)剩下的坏的，若每组都坚持认为本组是好的而其它组的都是坏的，则a组和b组无法区分。
可以通过如下两种方法找出一个好的芯片，时间复杂度都是O(n)。
Read full article from 算法导论习题4-5：芯片检测 - groovy2007的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment