下图是由2^3个二进制数字组成的环,由3个二进制数字构成的2^3种不同的数字序列恰好在该环中分别出现一次,例如:从箭头位置开始按顺时针方向每三个连续的二进制数字构成的序列各不相同,它们所代表的十进制数依次是:0,1,2,5,3,7,6,4.编写一个完整程序,该程序对于输入的正整数 n,生成由 2^n个二进制数字构成的环,使得从环中每个不同位置的数字开始按顺指针方向构成的长度为n的二进制数字序列各不相同。编程过程中,环的表示方式任意,程序输出结果是一个由2^n个二进制数字构成的序列,用它表示求得的环,该序列可以从环中的任何一个位置上的数字开始,例如:对应下图的输出结果(n=3时的输出结果)可以是00010111,也可以是 00101110,还可以是01011100,等等,程序输出任何一个即可。给出代码前,需要简述你的编程思路
#include <stdio.h>
#include <stdlib.h>
// Function to generate a binary array of size 2^n from a given gray code of size 2^(n-1)
void generateGrayCode(int n, int gray[1 << n]) {
if (n == 1) {
gray[0] = 0;
gray[1] = 1;
} else {
int prevSize = 1 << (n - 1);
int grayPrev[prevSize];
generateGrayCode(n - 1, grayPrev);
// Copy previous gray code
for (int i = 0; i < prevSize; i++) {
gray[i] = grayPrev[i];
}
// Reflect and prefix with 1
for (int i = prevSize - 1, j = prevSize; i >= 0; i--, j++) {
gray[j] = grayPrev[i] | (1 << (n - 1));
}
}
}
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s <n>\n", argv[0]);
return 1;
}
int n = atoi(argv[1]);
int gray[1 << n];
// Array to hold the gray code generateGrayCode(n, gray);
// Print the gray code starting from any position
// Here we start from the beginning for simplicity
for (int i = 0; i < (1 << n); i++) {
printf("%d", (gray[i] >> (n - 1)) & 1);
// Print the least significant bit first
for (int j = n - 2; j >= 0; j--) {
printf("%d", (gray[i] >> j) & 1);
}
}
printf("\n");
return 0;
}
标签:gray,数字,程序实现,二进制,int,prevSize,序列,14 From: https://blog.csdn.net/j000405/article/details/141364379