分治之芯片测试
一、问题描述
条件：有n片芯片，其中好芯片至少比坏芯片多1片。其中好芯片会给出正确的结果，而坏芯片的结果是不确定的。
问题：使用最少测试次数，从中挑出1片好芯片。
二、问题分析
1. 分析特例
假设有两个芯片A和B，使它们互相测试。结果如下：
|
|
A报告 |
B报告 |
结论 |
|
1 |
B是好的 |
A是好的 |
A，B都好或A，B都坏 |
|
2 |
B是好的 |
A是坏的 |
至少一片是坏的 |
|
3 |
B是坏的 |
A是好的 |
至少一片是坏的 |
|
4 |
B是坏的 |
A是坏的 |
至少一片是坏的 |
2. 分治的思想是问题的性质不变，但是规模缩减。
3. 解题思路
芯片两两测试，如果测试结果是情况1，A、B中留一片丢一片。如果是其他情况全丢掉，剩下的芯片仍然满足好芯片多于坏芯片的假设。因为对于1情况，两个芯片不是都好就是都坏，每次留一片丢一片，相当于对这种情况下的好芯片及坏芯片各种减半。而对于2、3、4情况中，至少有一片是坏的，那么全部丢弃的话，坏芯片减少的数量大于或者等于好芯片。所以，整体来说留下的芯片中好芯片仍然多于坏芯片。这样问题的性质不变，但是规模缩减。
三、伪代码
四、时间复杂度