1

我的任务是使用递归打印出格雷码。用户在 之间输入一个位值，因此您可以拥有0-8的最大数量是 256 (2^8)。strings

我已经完成了基本案例，但我不知道我会为 else 部分做什么。

到目前为止我的代码：

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

void gcodes (int n) {
    char bits[256][8];
    int i, j;
    int x = pow (2, n);

    if (n == 1) {
        bits[0][0] = '0';
        bits[1][0] = '1';
    } else {
        gcodes (n-1);
    }

    for (i=0; i<x; i++) {
        for (j=0; j<n; j++) {
            printf("%c", reverse[i][j]);
        }
    printf("\n");
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Invalid number of arguments\n");
        return 0;
    }

    int n;
    n = atoi (argv[1]);

    if (n > 8 || n <= 0) {
        printf("Invalid integer\n");
        return 0;
    }

    gcodes (n);
}
4

2 回答 2

0

格雷码从一个数字到下一个连续数字只能有一位变化。并且在整个序列中，没有重复的值。

鉴于该标准，有几种可能的格雷码实现。

有几个死端序列，其中值开始正常，然后失败，

通过代码计算格雷码需要大量的实验。

实际上，从网上简单地找到一个有效的格雷码序列，并将其粘贴到任何需要格雷码序列的程序中要容易得多。

大多数情况下，输入是一个灰色编码的轮子，读取它以确定轮子是否移动，而不是代码中生成的东西。

但是，如果我正在实现格雷码生成器，我希望它在最后生成的值和建议的新/下一个值之间执行异或，如果这是有效的（只有一位更改），我将搜索现有表值以确保它不是重复的。

这个 SO question 提出了一种可能的算法：

非递归格雷码算法理解

答案在下面重复：

你所有四个问题的答案是这个算法不是从较低的 n 值开始的。它生成的所有字符串都具有相同的长度，并且第 i 个（对于 i = 1, ..., 2n-1）字符串是从第 (i-1) 个字符串生成的。

这是 n = 4 的前几个步骤：

从 G0 = 0000 开始

要生成 G1，请翻转 G0 中的第 0 位，因为 0 是 1 = 0001b 的二进制表示中最低有效 1 的位置。G1 = 0001。

为了生成 G2，翻转 G1 中的第 1 位，因为 1 是 2 = 0010b 的二进制表示中最低有效 1 的位置。G2 = 0011。

要生成 G3，翻转 G2 中的第 0 位，因为 0 是 3 = 0011b 的二进制表示中最低有效 1 的位置。G3 = 0010。

为了生成 G4，翻转 G3 中的第 2 位，因为 2 是 4 = 0100b 的二进制表示中最低有效 1 的位置。G4 = 0110。

要生成 G5，请翻转 G4 中的第 0 位，因为 0 是 5 = 0101b 的二进制表示中最低有效 1 的位置。G5 = 0111。

于 2015-04-11T04:27:40.137 回答
0

既然你定义

    char bits[256][8];

使用函数内部的自动存储持续时间gcodes()，数组的生命周期在从函数返回时结束，因此您会丢失递归调用的结果。因此，至少定义它

    static char bits[256][8];

或全局，如果您想将结果保留bits在gcodes().

由于在标准格雷码中，最低有效位（位 0）遵循 0110 的重复模式，因此即使n = 1不需要，也可以方便地在基本情况下设置完整模式。

对于第i个代码的位j，其中j > 0，其值可以取自代码i/2的位j-1。

这导致完成的功能：

void gcodes(int n)
{
    static char bits[256][8];
    int i, j, x = pow(2, n);

    if (n == 1)
    {
        bits[0][0] = '0';
        bits[1][0] = '1';
        bits[2][0] = '1';
        bits[3][0] = '0';
    }
    else
    {
        gcodes(n-1);
        // generate bit j (from n-1 down to 1) for codes up to x-1
        for (i=0, j=n; --j; i=x/2)
            for (; i<x; i++)
                bits[i][j] = bits[i/2][j-1];
        // replicate bit 0 for codes up to x-1
        for (; i<x; i++)
            bits[i][0] = bits[i%4][0];
    }

    for (i=0; i<x; i++, printf("\n"))
        for (j=n; j--; )
            printf("%c", bits[i][j]);
}
于 2015-10-02T09:36:07.070 回答