本文共 506 字，大约阅读时间需要 1 分钟。

问题描述:有一堆芯片，已知其中好芯片比坏芯片至少多1片，现在的任务是通过测试从这一堆芯片中挑选出1片好芯片。请设计一个算法，使用最少的测试次数找出1片好芯片

测试方法的描述：将2⽚芯⽚（A和B）置于测试台上，互相进⾏测试，测试报告是“好”或“坏”，只取其⼀。好芯⽚的报告⼀定是正确的，坏芯⽚的报告是不确定的（可能会出错）。

 

为了能够用最少的测试次数找出好芯片，我们可以考虑用分治算法，不断缩小问题的规模

那么我们首先要想清楚这几个问题：

①我们应该选择什么样的规则，来缩减问题规模？ 

②观察两片芯片相互测试的报告，我们能得到什么结论？

首先我们来分析第二个问题

假设我们随机选取2片A和B，那么它们的测试包括有一下几种情况

有了这些结论，我们就可以思考如何缩减问题规模了，初始的想法的将这一堆芯片2个2个分为一组，每组测试一次，根据测试报告的结果，淘汰一部分芯片，剩下的芯片构成一个规模更小的子问题进行第二轮测试。（就像体育比赛的淘汰赛一样）。

那么我们应该采取什么样的规则，使得每轮淘汰的坏芯片数目至少和好芯片数目一样呢？

 规则：当报告是第一种情况时，任选一个芯片淘汰。 当报告是后三种情况时，两个芯片都淘汰掉

转载地址：https://blog.csdn.net/qq_26952443/article/details/129801859 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！