美文网首页
基础练习 芯片测试

基础练习 芯片测试

作者: 就这样吧嘞 | 来源:发表于2019-05-16 18:33 被阅读0次

    问题描述
      有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(并不表示该芯片对本身的测试结果。芯片不能对本身进行测试)。
    输出格式
      按从小到大的顺序输出所有好芯片的编号
    样例输入
    3
    1 0 1
    0 1 0
    1 0 1
    样例输出
    1 3

    第一种解法 和第一行比对,记录结果,相同为1;不同为0;

    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner (System.in);
            int n =sc.nextInt();
            int cunchu[][] = new int [n][n];
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    cunchu[i][j]=sc.nextInt();
                }       
            }
            int jieguo[]=new int[n];
            jieguo[0]=1;
            for(int x=1;x<n;x++) {
                jieguo[x]=bidui(cunchu,n,0,x);
    //          System.out.println(jieguo[x]);
            }
            
            int sum=0;
            for(int y=0;y<jieguo.length;y++) {
                sum=sum+jieguo[y];
            }
            if(sum>=n/2) {//第一片是好的
                shuchu(jieguo,1);
            }
            else {
                shuchu(jieguo,0);
            }
            
            
        }
        private static void shuchu(int[] jieguo, int p) {
            for(int i=0;i<jieguo.length;i++) {
                if(jieguo[i]==p) {
                    System.out.print(i+1+" ");
                }
            }
            
        }
        public static int bidui(int aa[][],int n,int i,int j) {
            int fanhui;//1 相同 0不同
            int jishu=0;
            for(int z=0;z<n;z++) {
                if(aa[i][z]==aa[j][z]) {
                    jishu++;
                }
            }
            if(jishu>=n-2) {
                fanhui=1;
            }
            else {
                fanhui=0;
            }
    //      System.out.println(fanhui);
            return fanhui;
        }
    }
    
    

    但是只得到80分
    找到错误数据,测试结果

    6
    1 0 1 1 0 1
    0 1 1 1 0 1
    1 0 1 1 0 1
    1 0 1 1 0 1
    1 0 1 1 0 0
    1 0 1 1 0 1
    1 2 3 4 5 6 
    

    发现算法缺陷,1行和2行无法对比
    决定换一种思路;
    由已知好芯片比坏芯片多。我们可以通过所有芯片判断一颗芯片的好坏
    即每列找出相同数据较多元素,即可指导当前列代表芯片的好坏
    代码如下:

    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            Scanner sc = new Scanner (System.in);
            int n =sc.nextInt();
            int cunchu[][] = new int [n][n];
            for(int i=0;i<n;i++) {
                for(int j=0;j<n;j++) {
                    cunchu[i][j]=sc.nextInt();
                }       
            }
            int jieguo[]=new int[n];
        
            for(int lie=0;lie<n;lie++) {
                int jishu=0;
                for(int hang=0;hang<n;hang++) {
                    if(hang==lie) {
                        cunchu[hang][lie]=1;//排除芯片自身影响
                    }
                    jishu=jishu+cunchu[hang][lie];
                }
                if(jishu>n/2) {//当前颗为好
                    jieguo[lie]=1;
                }
                else{//当前颗为坏
                    jieguo[lie]=0;
                }       
            }
            shuchu(jieguo);
            
        }
        private static void shuchu(int[] jieguo) {
            for(int i=0;i<jieguo.length;i++) {
                if(jieguo[i]==1) {
                    System.out.print(i+1+" ");
                }
            }
            
        }
    
    }
    

    问题解决,复杂度更低,代码也更为简便

    相关文章

      网友评论

          本文标题:基础练习 芯片测试

          本文链接:https://www.haomeiwen.com/subject/oghwaqtx.html