Gray码问题的程序实现

1 Gray码问题的程序实现用的是分治法测略递归调用：

 

 

public class Gray {
	public static void main(String[] args) {
		String[] string = new String[1 << 5];
		string = Grays(5);
		for (int i = 0; i < (1 << 5); i++)
			System.out.print(string + ".");
	}

	public static String[] Grays(int n) {
		String[] s = new String[1 << n];
		if (n == 1) {
			s[0] = "0";
			s[1] = "1";
		} else {
			int n1, n2, n3;
			n2 = n / 2; // 将n拆分成n1和n2的形式 递归调用实现
			n1 = n - n2;
			String[] s1 = new String[1 << n2];
			s1 = Grays(n2);
			String[] s2 = new String[1 << n1];
			s2 = Grays(n1);
			for (int i = 0; i < (1 << n2); i++) {
				n3 = (1 << n1) + 1; // 这个变量用户将一定位置的S调换
				for (int j = 0; j < (1 << n1); j++) {
					if (i % 2 != 0) {
						n3 = n3 - 2;
						s = s1 + s2[j];//实现有些变量的逆转
					} else
						s = s1 + s2[j];
				}
			}
		}
		return s;
	}

}

 2 这个是另一种的Gray码算法

void Gray(int n){
 
              /* 初始条件 */
 
              if(n == 1){
 
                     gs[0] = "0";
 
                     gs[1] = "1";
 
              }
 
              else{
 
                     /* 先算出n-1位所有的Gray码 */
 
                     Gray(n-1);
 
                     /* n位Gray码的后半部分是n-1位Gray码倒序再加上一个"1" */
 
                     for(int j = 1<<(n-1);j < 1<<n;j++)
 
                            gs[j] = gs[(1<<n)-j-1]+"1";
 
                     /* n位Gray码的前半部份是n-1位Gray码末尾加"0" */
 
                     for(int j = 0;j < 1<<(n-1);j++)
 
                            gs[j] = gs[j]+"0";
 
              }

 

3 第三种方法

    

public class MyGray{

public static void main(String args[]){
  Gray(4);
} 

public static void Gray(int n){
   String [] s = new String[(1<<n)];
   s[0] = new String("0");
   s[1] = new String("1");
   
   for(int i = 1;i <= n;i++){
    for(int j = 1;j <= (1<<(i-1));j++){
     s[(1<<i)-j] = s[j-1];
     s[j-1] = s[j-1]+"0";
     s[(1<<i)-j] = s[(1<<i)-j]+"1";
    }
   }
   for(int i = 0;i<(1<<n);i++){
    System.out.print(s+" ");
   }
   
  }

}