微网站设计与开发,购票网站模板,电脑制作ppt的软件,旅游网站系统问题#xff1a;产生n位元的所有格雷码。格雷码(Gray Code)是一个数列集合#xff0c;每个数使用二进位来表示#xff0c;假设使用n位元来表示每个数字#xff0c;任两个数之间只有一个位元值不同。例如以下为3位元的格雷码#xff1a; 000 001 011 010 110 111 101 100 。…问题产生n位元的所有格雷码。格雷码(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位元格雷码产生的。 如果能够理解上面的部分下面部分的代码实现就很容易理解了。 //格雷码
#include iostream
#include vector
#include string
#include cmath
using namespace std;vectorstring GrayCode(int n) {// produce 2^n grade codesvectorstring graycode(int(pow(float(2.), n)));if (n 1) {graycode[0] 0;graycode[1] 1;return graycode;}vectorstring last GrayCode(n - 1);for (int i 0; i last.size(); i) {graycode[i] 0 last[i];graycode[graycode.size() - i - 1] 1 last[i];}return graycode;
}
int main()
{vectorstring graycode GrayCode(4);for (auto x: graycode){cout x endl;}} 参考文献 1.格雷码的实现 2.格雷码百度百科
