算法设计与分析 —— 3-4 芯片测试

一好一坏：

说对方好的那个芯片一定是坏的，因为对方说他是坏的。

说对方坏的那个芯片可以是好的，因为对方坏了也可以恰好说对了自己是好的。

也可以两个都是坏的，说好坏都无所谓。

----------------------------------------------------------------------------------------------------------------------------------

前提：好芯片比坏芯片至少多1片

分析：根据前提，必定有一组全是好的，另一组也至少有一个好的

分治：假设总共4片，分成两组，可能产生的结果：

1. 其中一组如果是“好，好”，另一组不是：成立。且第一组两片芯片全是好的，第二组至少一个好的。

2. 两组都是都是“好，好”：成立。且两组芯片全是好的。因为根据前提，不可能有一组全是坏的。

3. 两组都是“好，坏” 或者 “坏，好”，或者 “坏，坏”：不成立。这样每组都至少有一个是坏的，好芯片的总数不满足前提条件。

处理：根据本分治算法的淘汰规则，

           上述情况1: 留下一个好的，芯片总数减去3/4。剩下的芯片仍然满足前提条件。

           上述情况2: 留下两个好的，芯片总数减半。剩下的芯片仍然满足前提条件。

----------------------------------------------------------------------------------------------------------------------------------