c - 递归 C 函数

Question

我需要用 C 语言编写一个递归函数，对于某个 n，计算没有三个连续数字 1 的 n 位二进制数的数量..

例如，对于 n=3，所有可能的 3 位数字为:000001010011100101110111

因此该函数返回 7，因为只有一个数字包含三个 1。

到目前为止，我什至不知道从哪里开始。我看不到任何可以帮助我的算法。

如有任何帮助，我们将不胜感激。谢谢。

Answer 1

让我们构造一个从左到右不包含三个连续数字的数字。

它必须以最多两个 1 开头，因此它要么以没有 1、一个 1 或两个 1 开头。换句话说，我们的数字以 0、10 或 110 开头。在所有这些情况下，数字其余部分的唯一限制是它不包含任何三个连续的数字，因此这允许我们应用相同的递归函数:

#include <stdint.h>
#include <stddef.h>

uint64_t nothreeconsecutive(int n) {
    if (n <= 2) return 1 << n;
    return nothreeconsecutive(n-1) + nothreeconsecutive(n-2) + nothreeconsecutive(n-3);
}