算法0x01：芯片测试

cuckoo

有n=2^k块芯片（好芯片至少比坏芯片多1片），从中挑出一片好芯片。
已知有如下的测试情形：
A测试    B测试    结论
坏的     坏的     至少一片是坏的
坏的     好的     至少一片是坏的
好的     坏的     至少一片是坏的
好的     好的     都好或都坏

采用分治策略，伪码如下：
k = n;while k > 3{    把当前所有芯片分为[k/2]组; // 这里[k/2]表示取k/2下界，下同    for(i = 1; i <= [k/2]; ++i)    {        if(两块都是好的)            任取一块留下;        else            两块都丢弃;    }    if (2*[k/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：如当前留下的芯片数目为奇数，在丢弃时要保证最后一组留下的是好芯片，通过前面的芯片来投票决定。