赞
踩
测试方法:将两片芯片(a,b)置于测试台上,互相进行测试,测试报告为“好”或“坏”,只取其一。
假设:好芯片的报告一定是正确的,坏芯片的报告是不确定的(可能会出错)
测试结果分析:
A报告 | B报告 | 结论 |
B是好的 | A是好的 | AB都好或AB都坏 |
B是好的 | A是坏的 | 至少一片是坏的 |
B是坏的 | A是好的 | 至少一片是坏的 |
B是坏的 | A是坏的 | 至少一片是坏的 |
输入:n片芯片,其中好芯片至少比坏芯片多一片
问题:设计一种测试方法,通过测试从n片芯片中挑出一片好芯片。
要求:使用最少的测试次数
结论:至少一半的芯片报“好”,则该芯片为好芯片。
超过一半芯片报“坏”,则该芯片是坏芯片。
分治法设计思想:
假设n为偶数,将n片芯片凉凉一组做测试淘汰,剩下芯片作为子问题,进入下一轮分组淘汰。
淘汰规则:“好”,“好” -> 任意留一片,进入下一轮(因为前提是好芯片比坏芯片至少多一片,如果一共有奇数个,根据单个的轮空,其中一定会有两个好的在一组或者轮空的是一个好的,所以这样的规则可以留下一个好的)
其他情况-> 全部抛弃(一好一坏或者两个坏的一定会有一个坏的,这样可以淘汰两个坏的或者一好一坏,不会影响剩余留下来的同样是好的比坏的至少多一)
上面说了 当数量为奇数时需要对单个芯片进行轮空操作:处理办法时对该单个轮空芯片进行单独测试,用其余所有芯片对其进行测试,如果至少一般芯片报好,则该芯片为好芯片,直接返回该芯片即可;如果该芯片是坏芯片,则舍弃该芯片,这样对单独的芯片进行处理了以后,就可以进行两两测试了。
为了方便,我使用了结构体存芯片,包括芯片编号和芯片的好坏。(下面代码在我自己的测试中没有出错,但是知道是不是有没有考虑到的地方,如果大家发现有错误,欢迎给我指出错误)
- //芯片测试
-
- struct Chip{
- int num; //芯片编号
- int state; //好坏
- };
-
-
- //两个芯片进行测试,2全好,0全坏,1一好一坏
- int judge(Chip *a,Chip *b){
- int count = 0;
- if(a->state==1){
- count=+b->state; //如果a是好的,判断b的结果与b一致
- }else if(a->state==0){
- count +=(rand()%2); //如果a是坏的,判断b可能好可能坏,随机产生
- }
- if(b->state==1){
- count += a->state;
- }else if(b->state==0){
- count +=(rand()%2);
- }
- return count;
- }
-
- //如果为奇数个
- vector<Chip*> oddTest(vector<Chip*> a){
- int size = a.size();
- vector<Chip*> result;
-
- int count = 0; //轮空操作
- for(int i=1;i<size;i++){
- if(a[i]->state ==1){
- count = count + a[0]->state;
- }else{
- count = count + (rand()%2);
- }
- }
- if(count >= size/2){ //如果轮空的是好的
- result.push_back(a[0]); //只返回这个 否则舍弃
- }else{
- for(int i =1;i<size;i+=2){
- int r = judge(a[i],a[i+1]);
- if(r == 2){
- result.push_back(a[i]); //判断后面的
- }
- }
- }
- return result;
- }
- //需测芯片个数为偶数
- vector<Chip*> evenTest(vector<Chip*> a){
- int size = a.size();
- vector<Chip*> result;
- for(int i =0;i<size;i+=2){
- int r = judge(a[i],a[i+1]);
- if(r == 2){
- result.push_back(a[i]);
- }
- }
- return result;
- }
-
-
-
- int test(vector<Chip*> a){
- int n = a.size();//有几个芯片
- if(n==3){
- int r = judge(a[0],a[1]); //选前两个进行测试
- if(r==1){ //如果一好一坏 取第三个
- return a[2]->num;
- }else{ //其他 任取一片
- return a[0]->num;
- }
- }
- else if(n==2||n==1){
- return a[0]->num; //任取一片 取第一片
- }
- vector<Chip*> next;
- while(n>3){
- if(n%2==0){
- next = evenTest(a);
- }else{
- next = oddTest(a);
- }
- return test(next);
- }
- }
测试时直接输入芯片的好坏
- int main(){
-
- //芯片测试
- vector<Chip*> chip ;
- for(int i=0;i<10;i++){
- Chip* a = new Chip();
- a->num = i;
- cin>>a->state;
- chip.push_back(a);
- }
-
- int t = test(chip);
- cout<<"芯片为:"<<t;
- return 0;
- }
时间复杂度分析:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。