算法2.分治算法芯片判断好坏

青旅半醒 2022-07-14 13:41 136阅读 0赞

有n片芯片，已知好芯片比坏芯片至少多1片。  
现需要通过测试从中找出1片好芯片，测试方法为：将2片芯片放到测试台上，2片芯片互相测试并报告测试结果（即好或者坏）；其中，好芯片的报告是正确的，坏芯片的报告是不可靠的（即可能正确、也可能错误）。  
为保证使用较少的测试次数就能从中找出1片好芯片，请设计一个分治算法解决上述问题。

1.  算法设计思路
2.  芯片进行一一比较可能的结果为（好，好）（好，坏），其中（好，好）包括的可能性为两片芯片都是好的，也有可能两片都是坏的。
3.  n奇数：先取出一片芯片，然后将该芯片和其余的芯片进行一一比较，若比较结果为（好，好）的次数>n/2,则该芯片为好芯片，反之则为坏芯片，将坏芯片删除后，进行n偶数
4.  n偶数次：芯片两两比较，在结果为（好，好）中取出一片另放，以便后续继续比较，将结果为（好，坏）的都舍去。若最后的芯片片数为偶数，则继续进行n偶数，若为奇数，则进行n奇数
5.  若结果剩余的片数为1或者2，则该芯片为好芯片。
6.  算法实现的伪代码  
    功能描述：在n片芯片中找出好的芯片  
    输入：n>0（芯片总片数），再输入0,1。0代表坏芯片，1代表好的芯片。其中1的个数大于0的个数  
    输出：已经找到好的芯片，比较的次数count。

```
        int find(n,int a[]){
        count++;
        if n=1 or n=2,return true count;
        else if n%2!=0 EvenNum(n,int Nnew[]);
        else if n%2=0 OddNum(n,int Nnew[]);
        }
        功能描述：n为偶数时，任意两片芯片进行一一比较，将比较结果为（好，好）的其中一片取出放入新的数组中，其余结果删除。
        输入：n，int Nnew[]
        输出：新的n，新的数组Nnew2[];
        int EvenNum(n,int Nnew[]){
        int k=0;
        for (int i=0;i<n;i+=2){
        if Nnew[i]=Nnew[i+1]  Nnew2[k]=Nnew[i] k++;
        return find(k,Nnew2[])
        }
        }
        功能描述：n为奇数时，取出其中任意一片芯片，将该芯片与其他芯片一一比较，若结果为（好，好）的次数大于n/2，则该芯片为好芯片，反之删除该芯片后进行n偶数。
        输入：n，int Nnew[];
        输出：好芯片和比较次数count或者新的数组Nnew3[];
        int OddNum(n, int Nnew[]){
        int k=0;
        for (int i=1;i<n;i++){
        if Nnew[0]=Nnew[i] k++;
        }
        if k>n/2 输出比较次数count
    else for (int j=1;j<n;j++) Nnew3[j-1]=Nnew[j] return find()
    }

1.  实现代码

import java.util.*;
        public class main{
            public static void main(String []args){
                Scanner in=new Scanner(System.in);
                while (true){
                    count=0;
                    System.out.println("输入芯片的总数n");
                    System.out.println("输入0或者1,0代表坏芯片，1代表好芯片");
                    System.out.println("其中1的个数大于0的个数");
                    int n=in.nextInt();
                    int a[] =new int[n];
                    for (int i=0;i<n;i++){
                        a[i]=in.nextInt();
                    }
                    count=find(n,a);
                    System.out.println("使用方法n奇数和n偶数的总次数"+count);
                    System.out.println();
                }
            }
            static int count=0;
            static int find(int n,int a[]){
                if (n==1||n==2)
                    return count;
                else if (n%2==0)//n=偶数
                    count=EvenNum(n,a);
                else if (n%2!=0)//n=奇数
                    count=OddNum(n,a);
                count++;
                return count;
            }
            private static int OddNum(int n, int[] Nnew) {
       //奇数
                int k=0;//定义一个确定记录（好，好）的次数k
                for (int i=1;i<n;i++){
                    if (Nnew[0]==Nnew[i])//将第一个和其余芯片比较
                        k++;//记录（好，好）的次数
                }
                int[] Nnew3 = new int[n-1];//当k<n/2，创建数组存储新的
                if (k>=n/2)
                    return count;//找到
                else {
                    for (int j=1;j<n;j++)
                        Nnew3[j-1]=Nnew[j];//删除第一个，
                    return find(n-1, Nnew3);//返回偶数
                }
            }
            static int EvenNum(int n,int Nnew[]){
       //偶数
                int k=0;//记录返回后芯片的个数
                int[] Nnew2 = new int[n/2];
                for (int i=1;i<n;i+=2){
       //芯片两两检验，将结果相同的取一个录入新的数组。
                    if (Nnew[i-1]==Nnew[i]){
                        Nnew2[k]=Nnew[i];
                        k++;
                    }
                }
                return find(k, Nnew2);//返回find，并根据k的奇偶性重新判断
            }
        }

1.  算法运行结果及计算时间复杂度分析  
    ![这里写图片描述][SouthEast]  
    T(n)=T(n/2)+n/2 O(n)=log N
2.  体会  
    编写过程中犯了很多的错误，其中比较多的错误都是由于自己粗心大意，也就是基础理解不到位，例如判断一个整数是否为偶数老是爱写成/，导致了结果出现了很大的差池，最终在调试的时候发现了这个致命的错误。编写程序的时候，先把思路写下来，然后按照这个思路进行编写，感觉会比较顺手，要不然像以前一样，边写边想，老是停停顿顿，导致效率不是很高。程序写完后，测试花费了比较多的时间。很多都是要通过调试来验算自己的预算值。

[SouthEast]: /images/20220714/dbe5ebc050e3438fb72089737abbee17.png