构造N位格雷码（递归，面向对象）

问题：
递归打印出N位格雷码（相邻两个编码只有一位数字不同）:
　　　　　　问题化归为：现有前N位的格雷码，如何构造N+1位的格雷码？

解决方法：采用递归构造格雷码集和。

　　递归出口：n = 1; 此时格雷码{0,1}
　　N+1：N+1位的格雷码 = N位格雷码（顺序）+0，N位格雷码逆序+1（N位的格雷码顺序最后一个编码与逆序第一个编码是同一个编码，在此可以分别加0,1两个编码依旧只有一位不同）

public class GC{

    int[][] G;//

    int N;

    int SIZE;

    GC(int N){

        this.N = N;

        SIZE =(int)Math.pow(2,N);

        G = createG(G,N);

    }

    public int[][] createG(int[][] g,int N){//由原有的格雷码集合g造新的格雷码集G  递归构造

        if(N <1){

            return null;

        }

        if(N == 1){

            g = new int[2][1];

            g[0][0] = 0;

            g[1][0] = 1;

            return g;

        }

        g = createG(g,N-1);

        SIZE =(int)Math.pow(2,N);

        G = new int[SIZE][N];

        int n =N-1;//原格雷码的位数

        for(int i =0;i<SIZE/2;i++){//顺序

            for(int j=0;j<n;j++){

                G[i][j] = g[i][j];

            }

            G[i][N-1] = 0;

        }

        for(int i = SIZE/2;i<SIZE;i++){//逆序

            for(int j=0;j<n;j++){

                G[i][j] = g[SIZE-1-i][j];

            }

            G[i][N-1] = 1;

        }

        return G;

    }

    public void show(){

        for(int i =0;i<SIZE;i++){

            for(int j=0;j<N;j++){

                System.out.print(G[i][j]+" ");

            }

            System.out.println();

        }

    }

    public static void main(String[] args){

        int N = new Integer(args[0]).intValue();

        GC G= new GC(N);

        G.show();

        return;

    }

}

巴特西

构造N位格雷码（递归，面向对象）

最新文章

热门文章