2000芯片测试

2000芯片测试问题

问题描述：
芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片
好芯片，说明你所用的比较次数上限．
　其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏．
坏芯片和其它芯片比较时，会随机的给出好或是坏。


算法设计：
1.随机选一芯片（称为A），和剩余芯片比较，根据结果，将剩余芯片分为“好”，“坏”两堆。
2.若“好”的芯片比“坏”的少，则A为坏的，去除A，对剩余芯片重新执行步骤1
3.“好”的芯片比“坏”的多，则A可能是好，也可能是坏。由于原始条件（好的总数比坏的多，所以好那堆里肯定有好的芯片）
4.将“好”堆里芯片与A作比较，只要有一次把A比较成坏的，A就是坏的，去除A，做步骤1，否则，A为好的。算法结束。