-1

我正在考虑从以下行开始进行 for 循环：

for(int i = 0; i <= 20, i++){ 


    if i = 1; 


       i --;

` 然后在考虑 i = 0 的情况时我遇到了麻烦。有两种可能的情况，即 print i = 0 或 print i = 1。我可以看到这将被递归定义，即每个位是根据前面的数字定义的。

4

2 回答 2

0

如果我理解得很好，您想生成每个不包含连续 1 的 20 位模式。例如，00000000000000000001有效，但00000000000000000011无效。

这是一个自然递归的问题。你可以把它想象成一棵树，其中每个节点要么是 1 要么是 0。1 的节点只能有一个孩子（0 位），0 的节点有 2 个孩子，因为在 0 之后可以是另一个0。从图形上看，它的工作原理是这样的：

位树

树会像这样扩展，直到我们达到 20 的深度。我将这个值称为 value CUTOFF，因为您将来可能想要更改它。代码背后的思想正是树所传达的思想：

#include <stdio.h>
#define CUTOFF 20

char buffer[CUTOFF+1];

void print_bits(char next_bit, unsigned char count) {
    buffer[count] = next_bit + '0';
    if (count == CUTOFF-1) {
        buffer[CUTOFF] = '\0';
        printf("%s\n", buffer);
        return;
    }
    print_bits(!next_bit, count+1);
    if (next_bit == 0)
        print_bits(next_bit, count+1);
}

我们为位字符串保留一个缓冲区，因为我们需要多次打印它以应对next_bit == 0. 缓冲区是一种知道从根节点到当前节点的路径的方法，每个节点只能写入与其深度对应的位置（由 跟踪count）。

您可以通过以下方式开始派对：

int main(void) {
    print_bits(0, 0);
    print_bits(1, 0);
    return 0;
}

对于非常大的值CUTOFF（大于 255），您可能需要从count更改unsigned char为int。

请注意，根据定义，此代码将发现00000000000000000000是一个有效条目。如果你想总是至少有一个 1，你必须忽略这种情况。您可以在递归的基本情况下使用它来测试它strcmp()，但这将是低效的。另一种可能的方法是记录你写了多少个计数器，并在基本情况下测试它的值（或者只使用一个标志来指示是否至少写了一个“1”）。

于 2013-10-29T10:50:08.073 回答
0

我没有清楚地理解你的问题，但我猜想，你想得到“从 1 到 (1<<20) 的所有整数，没有像 11 或 111 或 111 等块”。

如果是这样，这是代码：

for(int m = 0x55555; m <= 0xAAAAA; m <<= 1) {
  int x = m;
  do {
    printf("x=0x%05x\n", x);
  } while(x = (x - 1) & m);
}
于 2013-10-29T00:57:37.887 回答