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

您有一些乐高塑料积木，所有积木均为1x1x1。另外，您还有一个瓷砖，1xN(N
这是一个例子:

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

输入7
输出:17


(来源:mendo.mk)

另外，如果您没有积木，则算作1种组合。

我已经解决了这个问题，并且发现了一种方法来计算可能的组合，如果图块的最大长度为14(3个序列)。我发现它使用for循环。

我最大的问题是我需要运行大量的for循环。例如，对于1个序列，我将1个用于循环，对于2个序列将2个循环+ 1个用于1个序列...因此，如果我全部使用80个积木，则我可以创建20个序列，而我将不得不使用210个以上的循环，这是数量庞大。因此，如果我可以将它们嵌套在一个容器中会很好。我尝试过，结果变得凌乱，并且无法给出正确的答案。

新代码:

#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;
}

最佳答案

如果这是一个计数问题(不输出组合，而只是对它们进行计数)，这是一个简单的问题。假设我们解决了n≥3的问题，现在解决了n + 1的问题，我们通过归纳来解决它:
假设f是一个函数，它显示了可能的方法数量，以使最后一项是砖。
类似地，g是一个函数，它显示了可能的方法数量，以使最后一项不是砖块。
让我们将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

sample :

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)可以通过在最后一个位置添加一个砖块而从f(n)获得。
通过在g(n-2)之后加上三个积木也可以得到f(n + 1)，这意味着n-1，n，n + 1个像元。
请注意，我们不能在g(n-1)或g(n)之后添加砖来创建f(n + 1)的有效解，因为它们不是有效解(连续砖的数量小于3)。另外，请注意，我们不需要计算在g(n-3)之后添加砖所产生的方式数，因为它们之前已由f(n)枚举。所以我们有f(n+1) = f(n) + g(n-2)。
以相同的方式，我们可以证明g(n+1) = f(n)+g(n)这种情况更容易，因为g(n + 1)可以简单地从任何有效解生成，直到n，因为这里没有3个连续的砖壁垒，它们可以在任何有效解之后出现。

关于c++ - 乐高塑料积木C++的组合数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10396058/