网站已改版,免费建站模板网站,熊掌号wordpress,使用编辑字母做免费网站Gray码是一个长度为2ⁿ的序列#xff0c;序列中无相同元素#xff0c;且每个元素都是长度为n位的二进制位串#xff0c;相邻元素恰好只有1位不同。例如长度为2的格雷码为#xff08;000,001,011,010,110,111,101,100#xff09;#xff0c;设计分治算法对任意的n值构造相…Gray码是一个长度为2ⁿ的序列序列中无相同元素且每个元素都是长度为n位的二进制位串相邻元素恰好只有1位不同。例如长度为2³的格雷码为000,001,011,010,110,111,101,100设计分治算法对任意的n值构造相应的格雷码。 传统的二进制系统例如数字3的表示法为011要切换为邻近的数字4也就是100时装置中的三个位元都得要转换因此于未完全转换的过程时装置会经历短暂的010,001,101,110,111等其中数种状态也就是代表着2、1、5、6、7因此此种数字编码方法于邻近数字转换时有比较大的误差可能范围。格雷码的发明即是用来将误差之可能性缩减至最小编码的方式定义为每个邻近数字都只相差一个位元因此也称为最小差异码可以使装置做数字步进时只更动最少的位元数以提高稳定性。 数字07的编码比较如下
十进制 格雷码 二进制
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111分治构造算法
import java.util.Scanner;public class Solution {static int n, m;static int arr[][];private static void Gray(int m, int n) {if (n 1) {arr[0][0] 0;arr[1][0] 1;return;}for (int i 0; i m / 2; i) {arr[i][n - 1] 0;//n位gray码的上半段为0arr[m - i - 1][n - 1] 1;//n位gray码的上半段为1}Gray(m / 2, n - 1);for (int i m / 2; i m; i) {for (int j 0; j n - 1; j) {arr[i][j] arr[m - i - 1][j];}}}private static void print(int[][] arr, int m, int n) {for (int i 0; i m; i) {for (int j n - 1; j 0; j--) {System.out.printf(%d , arr[i][j]);}System.out.println();}}public static void main(String[] args) {Scanner cin new Scanner(System.in);n cin.nextInt();//gray码长度为nm (int) Math.pow(2, n);//m个gray码arr new int[m][n];Gray(m, n);print(arr, m, n);}
}
结果显示
