生成格雷碼

題目

在一組數的編碼中，若任意兩個相鄰的代碼隻有一位二進制數不同，則稱這種編碼為格雷碼（Gray Code）請編寫一個函數，使用遞歸的方法生成N位的格雷碼。

給定一個整數n，請傳回n位的格雷碼，順序為從0開始。

測試樣例：

1

傳回：[“0”,“1”]

什麼是格雷碼

格雷碼任意兩個相鄰的代碼隻有一位二進制數不同，例如下圖

格雷碼屬于可靠性編碼，是一種錯誤最小化的編碼方式。因為，雖然自然二進制碼可以直接由數/模轉換器轉換成模拟信号，但在某些情況，例如從十進制的3轉換為4時二進制碼的每一位都要變，能使數字電路産生很大的尖峰電流脈沖。而格雷碼則沒有這一缺點，它在相鄰位間轉換時，隻有一位産生變化。它大大地減少了由一個狀态到下一個狀态時邏輯的混淆。

遞歸生成碼表

這種方法基于格雷碼是反射碼的事實，利用遞歸的如下規則來構造：

1. 1位格雷碼有兩個碼字
2. (n+1)位格雷碼中的前2n個碼字等于n位格雷碼的碼字，按順序書寫，加字首0
3. (n+1)位格雷碼中的後2n個碼字等于n位格雷碼的碼字，按逆序書寫，加字首1
4. n+1位格雷碼的集合 = n位格雷碼集合(順序)加字首0 + n位格雷碼集合(逆序)加字首1

import java.util.*;

public class GrayCode {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        System.out.println(Arrays.toString(getGray(n)));
    }

    private static String[] getGray(int n) {
        if(n == 1){
            return new String[]{"0","1"};
        }else{
            String[] temp = getGray(n-1);
            String[] result= new String[temp.length*2];
            for(int i = 0; i < temp.length;i++)
                result[i] = "0"+temp[i];
            int i,j;
            j = temp.length - 1;
            for( i = 0; i < temp.length && j>= 0;i++,j--)
                result[i+temp.length] = "1"+temp[j];
            return result;
        }
    }
}