精华内容
下载资源
问答
  • 芯片测试

    2021-02-16 15:55:14
    而用坏芯片测试其他芯片时,会随机给出好或是坏的测试结果(即此结果与被测试芯片实际的好坏无关)。  给出所有芯片的测试结果,问哪些芯片是好芯片。 输入说明 :  输入数据第一行为一个整数n,表示芯片个数。 ...

    作者: Turbo时间限制: 1S章节: 深度优先搜索

    问题描述 :

      有n(2≤n≤20)块芯片,有好有坏,已知好芯片比坏芯片多。
      每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时,能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时,会随机给出好或是坏的测试结果(即此结果与被测试芯片实际的好坏无关)。
      给出所有芯片的测试结果,问哪些芯片是好芯片。

    输入说明 :

      输入数据第一行为一个整数n,表示芯片个数。
      第二行到第n+1行为n*n的一张表,每行n个数据。表中的每个数据为0或1,在这n行中的第i行第j列(1≤i, j≤n)的数据表示用第i块芯片测试第j块芯片时得到的测试结果,1表示好,0表示坏,i=j时一律为1(并不表示该芯片对本身的测试结果。芯片不能对本身进行测试)。

    输出说明 :

      按从小到大的顺序输出所有好芯片的编号

     

     

    #include <iostream>
    using namespace std;
    
    int main(){
        //组数
        int n;
        cin>>n;
        //输入芯片检测情况
        int a[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>a[i][j];
            }
        }
        for(int j=0;j<n;j++){
            int sum=0;
            for(int i=0;i<n;i++){
                sum+=a[i][j];
            }
            if(sum>n-sum){
                cout<<j+1<<" ";
            }
        }
        return 0;
    }
    

     

    展开全文
  • 分治 芯片测试

    2020-04-29 17:39:31
    1. 芯片测试 在讲解具体的芯片测试的分治策略算法之前,先来了芯片测试的意思 1.1 一次测试的过程 如上图,A、B为芯片。测试方法为:将2片芯片(A和B)置于测试台上,互相进行测试,测试报告是“好”或者“坏”,只...

    1. 芯片测试

    在讲解具体的芯片测试的分治策略算法之前,先来了芯片测试的意思

    1.1 一次测试的过程

    在这里插入图片描述

    如上图,A、B为芯片。测试方法为:将2片芯片(A和B)置于测试台上,互相进行测试,测试报告是“好”或者“坏”,只取其一。

    • 假设:好芯片的报告一定是正确的,坏芯片的报告是不确定的(可能会出错)

    那么上述测试的结果有四种可能,如下图:

    在这里插入图片描述

    上面的结果应该不难理解

    那么现在问题来了:

    • 输入:n片芯片,其中好芯片,至少比坏芯片多一片
    • 问题:设计一种测试方法,通过测试从n片中挑出1片好芯片
    • 要求:使用最少的测试次数

    1.2 如何测试一块芯片的好坏

    针对上述问题,现在先来研究一下,如何在上述n片芯片中,测试出A是好芯片还是坏芯片?

    • 问题:给定芯片A,判定A的好坏
    • 方法:用其他n-1片芯片对A进行测试。

    假设:n=7:好芯片数>=4

    1. A好,6个芯片中至少3个报“好”
    2. A坏,6个芯片中至少4个报坏

    所以对于n是奇数情况下:好芯片数>=(n+1)/2
    A好,至少有(n-1)/2个报“好”
    A坏,至少有(n+1)/2个报“坏”

    结论:
    至少一半报好,A是好芯片
    超过一半报坏,A是坏芯片

    假设: n=8:好芯片数>=5

    1. A好,7个芯片中至少4个报“好”
    2. A坏,7个芯片中至少5个报“坏”

    所以对于n是偶数:好芯片数 >= n/2+1.
    A 好, 至少有 n/2个报告“好”
    A 坏, 至少有 n/2+1个报告“坏”

    结论:n-1份报告中
    至少一半报好,A是好芯片
    至少一半报坏,A是坏芯片

    上面的分析,已经很清晰,我们已经知道如何测试一块芯片的好坏。那么人们最拿手的方法就是:暴力算法(蛮力算法)可以直接写代码了。。。

    1.3 蛮力算法

    测试算法:任取 1片测试,如果是好芯片,测试结束;如果是坏芯片,抛弃,再从剩下芯片中任取 1片测试,直到得到 1片好芯片

    时间估计:

    第一片是坏芯片,最多测试n-2次
    第二片是坏芯片,最多测试n-3次

    总计:Θ(n^2 )

    #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;
    }
    

    可见时间复杂度之高,数据量一多,肯定会超时。

    1.4 分治算法设计思想

    在分析分治算法的正确性之前,我们先给出这个算法的描述:

    假设n为偶数,将n片芯片两两一组做测试淘汰,剩下芯片构成子问题,进入下一轮分组淘汰。

    淘汰规则为:

    • “好,好” ==> 任留1片,进入下轮
    • 其他情况 ==> 全部抛弃

    递归截止条件:n<=3
    3片芯片,一次测试可得到好芯片
    1或者2片芯片,不需要再测试,他们都为好芯片。

    上述算法过程就是我们给出的分治策略的设计。那么为什么上述的策略是正确的呢?

    回忆一下,前面的文章,要保证分治策略的正确性的基本条件是:子问题与原问题性质相同。下面我们就来证明,上述分治策略的子问题与原问题性质相同。

    1.41 分治算法的正确性证明

    原问题:n片芯片,其中好芯片,至少比坏芯片多一片

    那么子问题,命题1:当 n 是偶数时,在上述淘汰规则下,经过一轮淘汰,剩下的好芯片比坏芯片至少多1片

    我们需要证明上述子问题的命题1是正确的。

    证明:假设原问题中A,B都好的芯片有i组,A与B一好一坏的有j组,A与B都坏的有k组。那么经过一轮淘汰后,好芯片还剩i片,坏芯片还剩k片。

    因为

    • 初始芯片总数 2i+2j+2k = n
    • 初始好芯片多于坏芯片:2i+j > 2k+j

    得出:i>k

    所以,剩余的芯片好芯片比坏芯片,至少多1片。命题1 是正确的。即证明了上述分治算法的正确性。

    当n为奇数时,特殊处理。当n是奇数时,可能会出现问题,如图:
    在这里插入图片描述
    可见淘汰后的子问题并不满足于原问题性质相同,此时无法继续测试。

    • 处理办法是:当n为奇数时,增加一轮对轮空芯片的单独测试,如果该轮空芯片为好芯片则算法结束,如果是坏芯片,则淘汰该芯片。

    下面给出上述分治算法的伪码描述:
    在这里插入图片描述
    补充说明:

    1. 第6点:if(1好1坏),则说明测试的两个至少一个为坏,所以未参加测试的一定为好的
    2. 第7点:由于题目初始条件,好的芯片一定比坏的芯片多

    1.42 时间复杂度分析

    设输入规模为n,,每轮淘汰后,芯片数至少减半,测试次数(含轮空处理):O(n)

    时间复杂度:

    W(n) = W(n/2) + O(n)
    W(3)=1,W(2)=W(1)=0

    解上述方程的得:W(n) = O(n)

    结果很振奋人心,你已经将一个O(n^2)级别的算法优化为了O(n)O(n)O(n)级别!!!

    2. 总结

    最大的需要注意的地方就是:如何保证子问题与原问题性质相同:
    可以:

    1. 增加额外处理(比如上述n为奇数时对轮空数据的处理)
    2. 额外处理的工作量,不改变函数的阶
      #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;
      }
    

    参考链接:https://www.jianshu.com/p/1cec17bfb2d5
    参考链接:https://blog.csdn.net/qq_37375427/article/details/102529005


    代码思路,编辑格式不易,大家觉得还可以可以点赞、收藏、关注一下吧!
    也可以到我的个人博客参观一下,https://motongxue.gitee.io

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,751
精华内容 3,500
关键字:

芯片测试