芯片检测问题_有 n 块完全一样的芯片,只能两两互相检测,一块好的芯片总能准确报告另外 一片芯片

（原题见算法导论第三版思考题4-5）
问题：有n个芯片，只能两两互相检测，一块好的芯片总能准确报告另外一片芯片的好坏，两两测试结果及结论如下表所示

假设超过一半的芯片是好的，请在线性时间内找出一片好的芯片。
解答：
问题说明：
若超过一半的芯片是坏的，那么基于好坏芯片的分布的方法不能解决这个问题，坏的芯片对另外一片芯片的好坏的检测结果是随机的，那么某种情况下与好的芯片同样数量的坏的芯片可以选择模仿好的芯片的检测行为，从而形成不可区分两组。
若超过一半的芯片是好的，则可以采用以下策略来进行区分：将芯片分成两组分别两两进行检测，若两两检测结果为第一种，则从中任意抽取一片芯片保留到下一轮，若两两检测结果为其余情况，则两个都抛弃。在超过一半的芯片是好的的情况下，经过该种策略一轮后，剩余芯片少于n/2个，且其中好的芯片的个数多余坏的芯片的个数（扔掉一个好的芯片至少同样扔了一个坏的芯片），即问题规模缩减一半。则假设T(n)为所花费的时间，有：
T(n) = T(n/2) + n/2
由算法导论主定理知，T(n) = Θ(n)即为线性时间内找出一片好的芯片。