你的位置:首页 > Java教程

[Java教程]格雷码那点事——递归非递归实现


简介

  在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同,则称这种编码为格雷码(Gray Code),另外由于最大数与最小数之间也仅一位数不同,即“首尾相连”,因此又称循环码或反射码。在数字系统中,常要求代码按一定顺序变化。例如,按自然数递增计数,若采用8421码,则数0111变到1000时四位均要变化,而在实际电路中,4位的变化不可能绝对同时发生,则计数中可能出现短暂的其它代码(1100、1111等)。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。

  格雷码(Gray Code)曾用过Grey Code、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字,它们有的不对,有的易与其它名称混淆,建议不要再使用这些曾用名。

 

生成格雷码 

  格雷码(Gray Code)是一个数列集合,每个数使用二进位来表示,假设使用n位元来表示每个数字,任两个数之间只有一个位元值不同。
  例如以下为3位元的格雷码: 000 001 011 010 110 111 101 100 。
  如果要产生n位元的格雷码,那么格雷码的个数为2^n.
 
  假设原始的值从0开始,格雷码产生的规律是:
第一步,改变最右边的位元值;
第二步,改变右起第一个为1的位元的左边位元;
第三步,第四步重复第一步和第二步,直到所有的格雷码产生完毕(换句话说,已经走了(2^n) - 1 步)。
 
用一个例子来说明:
  假设产生3位元的格雷码,原始值位 000
  第一步:改变最右边的位元值: 001
  第二步:改变右起第一个为1的位元的左边位元: 011
  第三步:改变最右边的位元值: 010
  第四步:改变右起第一个为1的位元的左边位元: 110
  第五步:改变最右边的位元值: 111
  第六步:改变右起第一个为1的位元的左边位元: 101
  第七步:改变最右边的位元值: 100
 
  如果按照这个规则来生成格雷码,是没有问题的,但是这样做太复杂了。如果仔细观察格雷码的结构,我们会有以下发现:
  1、除了最高位(左边第一位),格雷码的位元完全上下对称(看下面列表)。比如第一个格雷码与最后一个格雷码对称(除了第一位),第二个格雷码与倒数第二个对称,以此类推。
  2、最小的重复单元是 0 , 1
000
001
011
010
110
111
101
100

  所以,在实现的时候,我们完全可以利用递归,在每一层前面加上0或者1,然后就可以列出所有的格雷码。
  比如:
  第一步:产生 0, 1 两个字符串。
  第二步:在第一步的基础上,每一个字符串都加上0和1,但是每次只能加一个,所以得做两次。这样就变成了 00,01,11,10 (注意对称)。
  第三步:在第二步的基础上,再给每个字符串都加上0和1,同样,每次只能加一个,这样就变成了 000,001,011,010,110,111,101,100。
  好了,这样就把3位元格雷码生成好了。
  如果要生成4位元格雷码,我们只需要在3位元格雷码上再加一层0,1就可以了: 0000,0001,0011,0010,0110,0111,0101,0100,1100,1101,1110,1010,0111,1001,1000.
 
  也就是说,n位元格雷码是基于n-1位元格雷码产生的。

 


算法实现

1、递归实现

/**   * 递归生成二进制格雷码   * 思路:1、获得n-1位生成格雷码的数组   *   2、由于n位生成的格雷码位数是n-1的两倍,故只要在n为格雷码的前半部分加0,后半部分加1即可。   * @param n 格雷码的位数   * @return 生成的格雷码数组   */  public static String[] GrayCode(int n) {  //数组的大小是2的n次方,因为n位的格雷码有2的n次方种排列  String[] grayCodeArr = new String[(int)Math.pow(2, n)];    if(n < 1)  {    System.out.println("你输入的格雷码位数有误!");  }    if(1 == n)  {    grayCodeArr[0] = "0";    grayCodeArr[1] = "1";    return grayCodeArr;  }    //n-1 位格雷码的生成方式  String[] before = GrayCode(n-1);    for(int i = 0 ; i < before.length ; i++){    grayCodeArr[i] = "0" + before[i];    grayCodeArr[grayCodeArr.length -1 - i] = "1" + before[i];  }    return grayCodeArr;    }

 

2、非递归实现

 /**   * 非递归生成二进制格雷码   * 思路:1、获得n-1位生成格雷码的数组   *   2、由于n位生成的格雷码位数是n-1的两倍,故只要在n为格雷码的前半部分加0,后半部分加1即可。   * @param n 格雷码的位数   * @return 生成的格雷码数组   */  public static String[] GrayCode2(int n)  {      int num = (int)Math.pow(2, n);//根据输入的整数,计算出此Gray序列大小  String[] s1 = {"0","1"};//第一个Gray序列    if(n < 1)  {    System.out.println("你输入的格雷码位数有误!");  }    for(int i=2;i<=n;i++){//循环根据第一个Gray序列,来一个一个的求  int p = (int)Math.pow(2, i);//到了第几个的时候,来计算出此Gray序列大小  String[] si = new String[p];  for(int j=0;j<p;j++){//循环根据某个Gray序列,来一个一个的求此序列  if(j<(p/2)){  si[j] = "0" + s1[j];//原始序列前面加上"0"  }else{  si[j] = "1" + s1[p-j-1];//原始序列反序,前面加上"1"  }  }  s1 = si;//把求得的si,附给s1,以便求下一个Gray序列  }    return s1;  }

 

3、测试

public static void main(String[] args) {    System.out.println("————————————————————递归实现————————————————");  String[] strArr = GrayCode(4);  for(int i = 0 ; i < strArr.length ; i++)  {    System.out.println(strArr[i]);  }    System.out.println("——————————————————非递归实现————————————————");  String[] strArr2 = GrayCode2(4);  for(int i = 0 ; i < strArr2.length ; i++)  {    System.out.println(strArr2[i]);  }  }

 

4、结果:

————————————————————递归实现————————————————0000000100110010011001110101010011001101111111101010101110011000——————————————————非递归实现————————————————0000000100110010011001110101010011001101111111101010101110011000

  致谢:感谢您的耐心阅读!