发一道逻辑算法题大家试试: 芯片测试

ideawu

芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片好芯片，说明你所用的比较次数上限．

其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏．坏芯片和其它芯片比较时，会随机的给出好或是坏。

ideawu

我先给出一种简单的方法, 递归, 复杂度是O(n^2).

---- http://www.ideawu.net/blog/?p=276

题目中给出的最重要信息是比较方法. 根据比较方法, 我们可以得出最重要的结论是, 如果两个芯片两两比较出现了坏的情况, 那么这两个芯片必有至少一个是坏的. 定义一个方法bcmp(a,b),表示a和b两两比较, 返回值0表示至少有一块芯片是坏的, 1表示a,b都是好的或者都是坏的.

因为好芯片比坏芯片多, 所以从2K块芯片中随机取出K块芯片必然有至少一块好芯片, 也可能全部都是好芯片. 将这K块芯片中的随机一块基准芯片与其它所有的K-1块芯片进行bcmp(), 如果全返回1, 说明这K块芯片全部都是好芯片, 因为如果至少有一块坏芯片话, 该坏芯片必能被其中至少的一块好芯片检测出来.

如果不是全部都是好芯片的情况, 那么当bcmp()返回0时, 同时将两块芯片排除, 得到的2(K-1)块芯片仍然满足题设的条件. 然后继续进行二分.

如果K为1时, 两块芯片都是好的.

------

但有O(n)的算法.

epegasus

随机一词用的不准确.
拿A做参考,如果A是好的,那么测试B就是永远得出是一致的结果,
那A是坏的,测B的时候这个随机表示多次测试永远一致吗?

peidright

2k分成两半，找个算法，判断出那边真多。于是将剩余的一1k,再分成两半，再判断那边真多。如此下去，判断
2*(k+ k/2 + k/4+....)=4k? 然后找到真的后，回朔以前的结果，。我觉得关键就在分成两半的时候，通过逻辑运算
判断哪边真多，哪边真少。。上班中，晚上思考。。。

emacsnw

原帖由 ideawu 于 2009-11-8 22:24 发表
我先给出一种简单的方法, 递归, 复杂度是O(n^2).

---- http://www.ideawu.net/blog/?p=276

题目中给出的最重要信息是比较方法. 根据比较方法, 我们可以得出最重要的结论是, 如果两个芯片两两比较出现了坏 ...

O(N^2)太复杂了。这是个老题，可以O(N)次比较找出一块好的。方法是：
2K个芯片分成K对两两比较，结果有三种：好-好，好-坏，坏-坏。

（1）好-好：扔掉任意一块
（2）好-坏：都扔掉
（3）坏-坏：都扔掉

只要原来2K块芯片里好的比坏的多，那么留下的<=K块芯片里一定还能保证好的比坏的多。这样下去最后总能留下一块好的芯片。时间复杂度O(N).

peidright

，好！

ideawu

原帖由 emacsnw 于 2009-11-9 15:01 发表


O(N^2)太复杂了。这是个老题，可以O(N)次比较找出一块好的。方法是：
2K个芯片分成K对两两比较，结果有三种：好-好，好-坏，坏-坏。

（1）好-好：扔掉任意一块
（2）好-坏：都扔掉
（3）坏-坏：都扔掉 ...

不错! 这个方法收了.