(1)蛮力算法
1)问题:假设条件:有n片芯片,已知其中好的芯片比坏的芯片至少多1片。
问题要求:通过测试从中找出1片好芯片。
测试方法:将2片芯片放到测试台上,2片芯片相互测试并报告测试结果,
“好”或者“坏”。假定好芯片的报告是正确的,坏芯片的报告
是不可靠的(可能是对的,也可能是错的)。
设计算法:使用最少的测试次数找出1片好芯片。
2)解析:任取一片和n-1测试,如果n/2(向下取整)结果是好的,这一片是好的。
3)设计:
#include<iostream>
#include<cmath>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <cstring>
#define MAX 100
using namespace std;
int main(){
int n;
int a[MAX];
while(cin>>n){
srand(time(NULL));
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){ /*芯片编号为数组下标,从1开始*/
cin>>a[i]; /*数组值代表芯片好坏,1为真0为假*/
}
int cnt=0; /*查找次数*/
for(int i=1;i<=n;i++){
int sum=0;
for(int j=1;j<=n;j++){
cnt++;
if(i!=j&&a[i]==1&&a[j]==1) /*两片芯片都是好的*/
sum++;
if(i!=j&&a[i]==1&&a[j]==0) /*测试芯片是坏的*/
sum+=rand()%2;
if(i!=j&&a[i]==0&&a[j]==0) /*两片芯片都是坏的*/
sum+=rand()%2;
}
if(sum>=n/2){
cout<<"查找次数:"<<cnt<<endl;
break;
}
}
}
return 0;
}
4)分析:
最好情况:第一个测试的芯片就是好的,则只需要测试n-1次,时间复杂度为O(n);
最坏情况:第n/2(向下取整)个测试芯片是好的,则需要测试(n-1)*(n/2)次,时间复杂度为O(nlogn);
平均情况:第一个好的芯片出现的可能从1到n/2(向下取整)是一样的,
每个芯片的测试次数都是n-1次,时间复杂度为O(nlogn)。
(2)分治算法
1)问题:同上。
2)解析:将芯片两两分组进行比较,如果测试结果都是好的,则保留任意一块芯片,否则两片芯片都舍弃。如果芯片块数为奇数,则未分组的那块直接保留。将保留的芯片继续两两分组比较,按照同样的规则取舍,直到只剩下一块芯片或者两块芯片。因为题目已经保证好的芯片比坏的芯片至少多一片,每次我们舍弃的都是一好一坏,或者舍弃一块好的保留一块好的,或者舍弃一块坏的保留一块坏的,始终保证了好的芯片至少比坏的芯片多一片,所以最后剩下的一块或者两块芯片就是好的。
3)设计:
#include<iostream>
#include <cmath>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <cstring>
#define MAX 100
using namespace std;
int main(){
int n;
int num1,num2,sum;
int a[MAX],b[MAX];
while(cin>>n){
srand(time(NULL));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
/*a数组标记芯片好坏,b数组记录被保留芯片编号*/
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=i;
}
num1=n;
num2=1;
sum=0;
while(1){
/*芯片只剩一片或两片则可以直接得到结果,结束循环*/
if(num1<=2)
break;
else if(num1%2){ /*芯片个数为奇数*/
for(int i=1;i<num1;i+=2){
sum++; /*记录查找次数*/
if(a[b[i]]==1&&a[b[i+1]]==1) /*两片芯片都是好的*/
b[num2++]=b[i+rand()%2];
/*两片芯片是坏的,rand模拟结果是好的这一随机现象*/
if(a[b[i]]==0&&a[b[i+1]]==0&&rand()%2)
b[num2++]=b[i+rand()%2];
}
b[num2++]=b[num1]; /*最后一块芯片保留*/
}
else{ /*芯片个数为偶数*/
for(int i=1;i<=num1;i+=2){
sum++;
if(a[b[i]]==1&&a[b[i+1]]==1) /*两片芯片都是好的*/
b[num2++]=b[i+rand()%2];
if(a[b[i]]==0&&a[b[i+1]]==0&&rand()%2) /*两片芯片是坏的*/
b[num2++]=b[i+rand()%2];
}
}
num1=num2-1; /*一次比较后保留芯片的个数*/
num2=1; /*下一次查找的开始位置*/
}
cout<<"查找次数:"<<sum<<endl;
cout<<"找到的芯片编号:"<<b[1]<<endl;
}
return 0;
}
4)分析:最好情况:当每次测试都是好坏芯片相互测试时,只需要测n/2次就可以找
出好的芯片,时间复杂度为O(logn);
最坏情况:全部都是好的芯片,则需要测试n/2+n/4+......+1次才能找出好的
芯片,时间复杂度为O(n);
平均情况:每次查找的时候通常都是有好有坏,每次的测试次数都小于
n/(2^k)(k为第几轮测试,0<k<=logn),所以时间复杂度为O(logn).