c++ - 乐高塑料积木的组合数 C++

Question

您有一些乐高塑料积木，所有积木都是 1x1x1。您还有一 block 瓷砖，1xN(N <= 80)，您应该在上面放置乐高积木。您可以按顺序排列它们(如果有 3 个或更多连续的积木，则一个序列是正确的)，而且您必须在 2 个序列之间至少有 1 个空格。您应该计算可以将砖 block 放在瓷砖上的不同组合的数量。

这是一个例子:

如果图 block 是 1x7，则有 17 种不同的组合。

输入:7输出:17

_{(来源:mendo.mk)}

此外，如果您没有积木，则计为 1 种组合。

我已经研究过这个问题，并且找到了计算图 block 的最大长度是否为 14(3 个序列)的可能组合的方法。我发现它使用 for 循环。

我最大的问题是我需要运行大量的 for 循环。例如，对于 1 个序列，我使用 1 个 for 循环，对于 2 个序列，2 个循环 + 1 个用于 1 个序列...所以如果我使用所有 80 个积木，我可以创建 20 个序列，我将不得不使用超过 210 个 for 循环，这是数量巨大。所以如果我能把它们嵌套在一起就好了。我试过了，它变得很乱，而且没有给出正确的答案。

新代码:

#include <iostream>
using namespace std;
int main()
{
    long long int places, combinations = 1;
    cin >> places;
    long long int f[80], g[80];
    f[0] = 0;
    f[1] = 0;
    f[2] = 0;
    g[0] = 1;
    g[1] = 1;
    g[2] = 1;
    for(int i = 3; i<=places; i++)
    {
        f[i] = f[i-1] + g[i-3];
        g[i] = f[i-1] + g[i-1];
    }
    combinations = f[places] + g[places];
    cout << combinations;
    return 0;
}

Answer 1

如果这是一个计数问题(不是输出组合，而只是计算它们)，这是一个简单的问题。假设我们现在对 n ≥ 3 求解它对 n+1 求解，我们通过归纳求解:

假设 f 是一个函数，它显示使最后一项成为砖 block 的可能方式的数量。类似地，g 是一个函数，它显示了使最后一项不是砖 block 的可能方式的数量。让定义 h = f+g，作为所有可能方式的数量。

所以我们有:

f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)

有初始条件:

for n=0,1,2: g=1, f= 0.
for n = 3: g=1,f=1

示例:

n=4: g=2,f=2 ==> h=4
n=5: g=4, f= 3 ==> h=7
n=6: g=7, f= 4 ==> h=11
n=7: g=11,f=6 ==> h=17

我们可以用 O(n) 中的一个 for 循环解决它。

---

为什么:

f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)

首先，让我们证明第一部分:

请记住，我们假设 f(n) 是最后一项有塑料砖的工作解决方案，而 g(n) 是最后一项没有砖的工作解决方案。

f(n+1) 可以通过在最后一个地方添加一 block 砖从 f(n) 获得。同样f(n+1)可以在g(n-2)后加三 block 砖得到，即n-1,n,n+1的单元格。

请注意，我们不能在 g(n-1) 或 g(n) 之后添加砖 block 来创建 f(n+1) 的有效解决方案，因为它们不是有效解决方案(连续砖 block 的数量少于 3 ).另外，请注意，我们不需要计算在 g(n-3) 之后添加砖 block 所产生的路数，因为它们之前已由 f(n) 枚举。所以我们有 f(n+1) = f(n) + g(n-2)。

以同样的方式我们可以证明 g(n+1) = f(n)+g(n) 这种情况更容易，因为 g(n+1) 可以简单地由直到 n 的任何有效解决方案，因为这里没有 3 个连续的砖 block 障碍，它们可以在任何有效解决方案之后出现。