分治算法:芯片测试
问题描述
有n片芯片,已知好芯片比坏芯片至少多1片。现在需要通过测试从中找出1片好芯片,测试方法如下:将2片芯片放到测试台上,2片芯片互相测试并报告测试结果(即好或者坏);其中,好芯片的报告是正确的,而坏芯片的测试报告是不可靠的(即报告结果可能为“好”或者“坏”)。
方案一:枚举法
设计思路
拿单个芯片跟其余芯片进行测试,当测试结果为“好”的次数大于n/2时,则证明此芯片为好芯片,否则,进行下一个芯片的测试。
方案二:分治算法
设计思路
规则:好芯片比坏芯片至少多1片。
芯片数为偶数时,当测试结果为“好,好”,可丢弃其中一片,因为可能两个都是好芯片|两个都是坏芯片。当测试结果为“好,坏”,可两个都丢弃,因为这两个芯片至少有一个坏芯片,丢弃两个不影响规则。当测试结果为“坏,坏”时,也可全部丢弃,理由同上。
芯片数为奇数时,可对轮空的芯片进行线性测试,即可对最后一个芯片进行测试,若测试结果为“好”的次数≥芯片数量的一半,则为好芯片,否则,则丢弃该芯片。
边界条件:待测芯片等于3片,或者待测芯片小于2片(因为要满足上面的规则)
伪代码实现
输入:芯片数n 芯片数组chips[]
输出:测试次数
S1: if n=3 then return 1
S2: if n<3 then return 0
S3: if (n%2=0) then newChips[n/2]
S4: for i=0 to n
S5: if chips[i]=chips[i+1] then newChips[nElems++] = chips[i]
S6: return sum+findGoodChip(nElems,newChips)
S7: if n%2!=0 then
S8: for i = 0 to n-1
S9: if chips[i] = chips[n-1] then k++
S10: if k>n/2 return sum
S11: else 执行偶数测试过程
代码实现
static int findGoodChip(int n, int[] chips) {//n为芯片个数,chips[]为存放芯片报告的数组
if(n == 3) {//只剩下三片芯片时,因为好芯片至少比坏芯片多一片,所有测试一次就可以找到好芯片
return 1;
}else if(n < 3)//当芯片小于3时,两个都是好芯片,直接找到。
return 0;
int sum = 0;
if(n%2 == 0) {//当芯片个数为偶数时,分为n/2组,两两测试
int[] newChips = new int[n/2];
int nElem = 0;
for(int i = 0;i < n;i+=2) {
if(chips[i] == chips[i+1]) {
newChips[nElem++] = chips[i];
}
sum++;
}
return sum+findGoodChip(nElem,newChips);
}else {//当芯片为奇数时
int k = 0;
for(int i = 0;i < n-1;i++) {//取最后一个芯片,用剩余的芯片对其测试
if(chips[i] == chips[n-1])
k++;
sum++;
}
if(k >= n/2)//若测试结果“好”>一半,则为好芯片
return sum;
int[] newChips = new int[n/2];//否则,删掉最后一个芯片,对其余芯片进行偶数操作。
int nElem = 0;
for(int i = 0;i < n-1;i+=2) {
if(chips[i] == chips[i+1])
newChips[nElem++] = chips[i];
sum++;
}
return sum+findGoodChip(nElem,newChips);
}
}
时间复杂度
每轮的淘汰,芯片个数至少减半,即W(n/2),测试次数为O(n).(含轮空处理)
时间复杂度W(n)=W(n/2)+O(n)
当芯片个数为2或1时,无需测试。W(1)=W(2)=0
当芯片个数为3时,只需测试一次。W(3)=1
即W(n) = O(n)