算法0x01：芯片测试
有n=2^k块芯片（好芯片至少比坏芯片多1片），从中挑出一片好芯片。已知有如下的测试情形：
A测试 B测试 结论
坏的 坏的 至少一片是坏的
坏的 好的 至少一片是坏的
好的 坏的 至少一片是坏的
好的 好的 都好或都坏
采用分治策略，伪码如下：
k = n;while k > 3{ 把当前所有芯片分为组; // 这里表示取k/2下界，下同 for(i = 1; i <= ; ++i) { if(两块都是好的) 任取一块留下; else 两块都丢弃; } if (2* < k) // 最后一组有3片 { 找出3块中测试结果为都好的那两块中的一块，与其它留下来的芯片再分别一起 测试一次，如果结果中为都好的超过一半，留下当前这块，否则留下3块中另外一块 } k = 留下的芯片数;}if (k == 3){ 任取两块，如它们都好，任取一块，否则取剩下的那一块;}else{ 任取一块;}
时间复杂度：
T(n) = T(n/2) + O(n)
由Master定理，知T(n) = O(n)
分析：
1：由抽屉原理：分组时两个好芯片在一组的级数大于两个坏芯片在一组的组数。
2：每次丢弃丢弃时，丢弃的坏芯片的数目一定大于等于丢弃的好芯片的数目，留下的芯片中的好芯片的数目一定大于坏芯片的数目。
3：如当前留下的芯片数目为奇数，在丢弃时要保证最后一组留下的是好芯片，通过前面的芯片来投票决定。
页:
[1]