有n片芯片,其中好芯片比坏芯片至少多1片,现需要通过测试从中找出1片好芯片
时间: 2023-05-19 10:03:09 浏览: 51
可以使用二分法来找出好芯片。首先将所有芯片分成两组,分别进行测试。如果其中一组测试结果全为好芯片,则说明好芯片在这一组中,否则好芯片在另一组中。然后再将包含好芯片的那一组继续分成两组,重复上述步骤,直到找到一片好芯片为止。
相关问题
用c编写有n片芯片,其中好芯片比坏芯片至少多1片,现需要通过测试从中找出1片好芯片。测试方法是:将2片芯片放到测试台上,2片芯片互相测试并报告测试结果:“好”或者“坏”。假设好芯片的报告是正确的,坏芯片的报告是不可靠的。请设计一个算法,使用最少的测试次数来找出1片好芯片。
这是一个经典的二分查找问题,可以使用类似于二分查找的方法来解决。首先,将所有芯片分成两组,每组各选取n/2片芯片。然后,将这两组芯片分别放到测试台上进行测试。如果两组芯片中都有好芯片,那么我们可以随便选择一组继续测试,因为我们已经找到了好芯片。如果一组中有好芯片,而另一组中没有好芯片,那么我们可以确定好芯片在有好芯片的那组中,因为好芯片的报告是正确的。然后,我们可以继续将有好芯片的那组芯片分成两组,重复上述步骤,直到找到一片好芯片为止。因此,最少需要进行log2(n)次测试。
设芯片有好有坏,好的芯片能正确测出其他芯片的好坏,坏的芯片测试其他芯片的好坏可能会出错,在一批芯片中好的芯片至少比坏芯片多一片,设这批芯片有17片,求测试出结果得到的第一片好芯片的序号
假设我们从第一片芯片开始测试,先测试第一片芯片。如果第一片芯片是好的,则可以通过它来测出其他芯片的好坏,可测试的范围缩小至16片。如果第一片芯片是坏的,则还需要测试一片芯片才能确定两片芯片的好坏关系,测试范围依然是17片。
接下来我们先假设第一片芯片是好的,那么我们现在可以通过它来测试剩下的16片芯片。我们用二分查找的思想来测试芯片。将剩下的16片芯片编号从1到16排列,将它们从中间分为两组,一组是1到8,另一组是9到16。我们现在通过第一片芯片来测试这两组芯片中的任意一组芯片。如果测试结果显示一组芯片与第一片芯片好坏关系相同,则说明这一组芯片中肯定没有好芯片。我们剩下的范围就是8片芯片中的一半,即第2组8个芯片,我们再次将它们分为两组。用二分查找的思想,我们可以在测试了log2(8)=3次之后找到第一片好芯片。
如果第一片芯片是坏的,那么我们需要再测试另一片芯片才能确定第一片芯片与另一片芯片的好坏关系,测试范围依然是17片。我们现在可以将第一片芯片移到一边,将剩下的16片芯片编号从1到16排列,再用相同的方法测试,我们最多需要测试2次。假设当前测试的芯片序号为1到8,我们用第一片芯片测试这8个芯片中的任意一片。如果测试结果显示这8个芯片中有一片与第一片芯片的好坏关系相同,则说明好芯片在1到8范围内,否则好芯片在9到16的范围内。然后我们缩小测试范围,再用相同的方法测试。
综上所述,我们在最坏的情况下,最多需要测试log2(17)=5次,就能找到第一片好芯片。第一片好芯片的序号是5。