Gray码 (格雷码) 【二进制】 | 您所在的位置:网站首页 › gray码怎么算 › Gray码 (格雷码) 【二进制】 |
以下内容是看了Matrix67的关于二进制的blog(Link)的一点总结与摘录。
Gray码,中文“格雷码”,是一种特殊的编码,相邻两个格雷码的二进制表示中有且仅有一位不同,且 n 阶 Gray 码是 0~2^n-1 的一个排列。 n 阶 Gray 码可以由 n-1 阶 Gray 码镜像翻转之后最前面加一个 '1' 得到。 比如 2 阶 Gray 码为: 00 01 11 10
3 阶: 000 001 011 010 110 111 101 100
这样就巧妙的实现了相邻的数只有一个二进制位不同。
Gray 与 Hanoi 塔问题有着密切联系,第 i 个 n 阶格雷码改变的是第 x 位,相应的 n 个圆盘的 Hanoi 塔在这第 i 步就移动编号为 x 的盘子。 这样,只要能计算出第 i 个 n 阶格雷码是什么,就能知道第 i 步的 n 阶 Hanoi 的移动步骤是什么。
求出第 i 个 Gray 码非常简单 : Gray(i) = i xor (i shr 1) [C++] Gray[i] = i ^ (i >> 1); 这个证明可以看 Matrix67 的blog。
有关 Gray码的题目一道:Link 题目大意:给定 n 与 m,要求输出一个 2^n 行, 2^m 列的矩阵,里面填 0~2^(n+m)-1 的所有数字,每个数字与它相邻的数字的二进制表示都有且仅有一位不同。 题目分析:这道题是求一个“二维”的格雷码,然而我们有一个简便的构造方法,就是每个数字的前 n 位是 n 阶格雷码,后 m 位是 m 阶格雷码。 行与行之间的前 n 位不同,列与列之间的后 m 位不同,这样,由“一维”格雷码就轻松构造出“二维”格雷码了~ 代码如下: #include using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); int R, C, Num; R = 1 1)) > 1))); printf("\n"); } return 0; }
|
CopyRight 2018-2019 实验室设备网 版权所有 |