首页 > 代码库 > C程序设计的抽象思维-递归过程-格雷码
C程序设计的抽象思维-递归过程-格雷码
【问题】
每一对相邻整数的二进制表示只有一位发生变化,这种编码称为Gray码。
如下所示3位的Gray码:
000 | 0 |
001 | 1 |
011 | 2 |
010 | 3 |
110 | 4 |
111 | 5 |
101 | 6 |
100 | 7 |
1. 写出N-1位的Gray码。
2. 以相反的顺序在该Gray码下重写一遍。
3. 在第一步得到的Gray码前加0,在第二步得到的Gray码前加1。
继续以3位Gray码为例,推导过程如下所示:
【代码】
#include <stdio.h> #include <stdlib.h> #define MAX 1024 #define M 10 int a[MAX][M]; /*****************************************/ /* 前半部分格雷码存入数组 */ /*****************************************/ void ForeCode(int forenum, int n) { int i, j; for(i = 0; i <= forenum; i++)/*双重循环使n-1位格雷码后移一位*/ for(j = n - 2; j >= 0; j--) a[i][j + 1] = a[i][j]; for(i = 0; i <= forenum; i++)/*前半部分第0位为0*/ a[i][0] = 0; } /*****************************************/ /* 后半部分格雷码存入数组 */ /*****************************************/ void BackCode(int backbegin, int backend, int n) { int i, j; for(i = 0; i < backbegin; i++)/*后半部分与前半部分对称*/ for(j = 1; j < n; j++) a[backend - i - 1][j] = a[i][j]; for(i = backbegin; i < backend; i++)/*后半部分第0位为1*/ a[i][0] = 1; } /*****************************************/ /* 生成格雷码 */ /*****************************************/ void GrayCode(int nBits) { int i, k, m = 1; if(nBits == 1) { a[0][0] = 0; a[1][0] = 1; } else GrayCode(nBits - 1); /*递归调用*/ for(i = 0; i < nBits; i++) m = 2 * m; /*n位的Gray码总共有2**n次方个*/ k = m / 2; ForeCode(k - 1, nBits); BackCode(k, m, nBits); } /****************************************/ /* 打印格雷码 */ /****************************************/ void PrintGrayCode(int nBits) { int i, j, m = 1; for(i = 0; i < nBits; i++) m = 2 * m; for(i = 0; i < m; i++) { for(j = 0; j < nBits; j++) printf("%d", a[i][j]); printf("\n"); } } int main() { int nBit; nBit = 3; GrayCode(nBit); PrintGrayCode(nBit); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。