一个工程师有 n 个假定相同的集成电路芯片，它们原则上能够相互测试。工程师测试夹具一次可容纳两个芯片。当夹具被加载时，每个芯片测试另一个并报告它的好坏。一个好的芯片总是准确地报告另一个芯片的好坏，但工程师不能相信一个坏芯片的答案。假设好筹码的数量大于坏筹码的数量。然后回答以下问题：
是否可以设计一种算法，在最多 O(n log n) 成对测试之后找到所有好的芯片？
芯片测试问题
计算科学
算法
2021-12-26 15:38:21
1个回答
答案是肯定的。有可能的。你都尝试了些什么？您是否实现了任何代码来测试不同的算法？
我也怀疑这是作业，但我会给你一些思考这个问题的方法。测试芯片的最坏方法是什么？如果您将任何芯片与其他芯片进行检查，您将需要执行 n² 次检查。有什么方法可以使用附加信息，即正确的读数多于错误的读数，来改善这一点？
其它你可能感兴趣的问题