(30分)
芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片好芯片，说明你所用的比较次数上限．其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏．坏芯片和其它芯片比较时，会随机的给出好或是坏。
题目中给出的最重要信息是比较方法. 根据比较方法, 我们可以得出最重要的结论是, 如果两个芯片两两比较出现了坏的情况, 那么这两个芯片必有至少一个是坏的. 定义一个方法bcmp(a,b),表示a和b两两比较, 返回值0表示至少有一块芯片是坏的, 1表示a,b都是好的或者都是坏的.
因为好芯片比坏芯片多, 所以从2K块芯片中随机取出K块芯片必然有至少一块好芯片, 也可能全部都是好芯片. 将这K块芯片中的随机一块基准芯片与其它所有的K-1块芯片进行bcmp(), 如果全返回1, 说明这K块芯片全部都是好芯片, 因为如果至少有一块坏芯片话, 该坏芯片必能被其中至少的一块好芯片检测出来.
如果不是全部都是好芯片的情况, 那么当bcmp()返回0时, 同时将两块芯片排除, 得到的2(K-1)块芯片仍然满足题设的条件. 然后继续进行二分.
如果K为1时, 两块芯片都是好的.
该算法最坏的情况是对芯片进行二分总是无法得到全部都是好芯片的情况, 而且直到最后一次bcmp才返回0. 所以比较次数 ((K-1)+(K-2)+...+1)*2=(K^2-K). 注意到bcmp()进行再次比较.
解题思想: 递归.
==== 2009年10月9日更新: 经过长期的思索, 终于想到一种复杂度只有O(n)的算法:
O(N)解法1:
2K个芯片分成K对两两比较，结果有三种：好-好，好-坏，坏-坏。
（1）好-好：扔掉任意一块
（2）好-坏：都扔掉
（3）坏-坏：都扔掉
只要原来2K块芯片里好的比坏的多，那么留下的<=K块芯片里一定还能保证好的比坏的多。这样下去最后总能留下一块好的芯片。时间复杂度O(N).
Loading ...
芯片* x= &芯片堆[0];
for(int i=1; i”小于等于号”k; i++){
if(x-‘大于号’测试(芯片堆[i])!= 坏的)
x= &芯片堆[i];
}
return *x;
-END-
当测试结果为 ‘合格’的时候, 被测试的要么真的是好的, 要么测试者本身就是坏的.
也就是说, 测试 结果为 ‘合格’ 的时候, 被测试的芯片不会比测试者差.
也就是说,一旦碰上一个好芯片,那么x所指的芯片一定是好的.
又因为,好芯片比坏的多.
所以 测试k次 一定有至少一个芯片是好的.
所以 x是好芯片. Reply
最坏的情况：k-1坏和k+1好，选出来的恰好是K-1坏和1块好
然后测试好的那块，刚好K-1块坏芯片都给出差评（当然好的芯片也会给对方差评）
如果是这种极端情况，又该如何处理呢？ Reply
不知道你说的"如果比较后值100次都为同样的值"原理是什么? Reply
取下一芯片与上个芯片比较，如返回一直为坏的话则芯片为好芯片，如返回值有变化则芯片奕为坏，取下一芯片与上一芯片比较。。。。 Reply