6

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

这是一个例子：

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

输入：7 输出：17

示例图片
（来源：mendo.mk）

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

我已经解决了这个问题，并且我找到了计算图块的最大长度是否为 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;
}
4

2 回答 2

10

如果这是一个计数问题（不输出组合，而只是计数它们），那很容易。假设我们现在求解 n ≥ 3 以求解 n+1，我们通过归纳求解：

Assumef是一个函数，它显示最后一项是砖块的可能方式的数量。类似地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

样品：

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

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

为什么：

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

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

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

f(n+1) 可以通过在最后一个位置添加一块砖来从 f(n) 获得。f(n+1) 也可以通过在 g(n-2) 之后添加三个砖块来获得，这意味着 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 个连续的砖障碍，它们可以在任何有效解决方案之后出现。

于 2012-05-01T10:48:41.433 回答
5

作为一个受过数学训练而不是 CS 的人，我觉得有必要提一下，虽然 Saeed Amiri 的算法非常好，并且对于 N 到几百万（当然，具有恒定的记忆）来说可能工作得足够快，但有一个从时间的角度来看更好的算法。

我会在他离开的地方捡起：

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

由于 f 和 g 是离散函数，您可以将它们视为序列。那么这变成了递归关系的线性系统。幸运的是，可以完全解决这样的系统，从而可以呈现 f 和 g 的显式形式。
不幸的是，SO 似乎不像 math.SE 那样支持 MathJax，所以我为从这里开始的低质量方程道歉。
让

     | f(n) |
     |f(n-1)|
u(n)=|f(n-2)|
     | g(n) |
     |g(n-1)|
     |g(n-2)|

也就是说，u(n) 是一个向量行。那么，以下情况属实：

|f(n+1)| |1 0 0 0 0 1| | f(n) |
| f(n) | |1 0 0 0 0 0| |f(n-1)|
|f(n-1)| = |0 1 0 0 0 0| . |f(n-2)|
|g(n+1)| |1 0 0 1 0 0| | g(n) |
| g(n) | |0 0 0 1 0 0| |g(n-1)|
|g(n-1)| |0 0 0 0 1 0| |g(n-2)|

由此得出的结论是u(n) = A * u(n-1)，其中 A 是上面的矩阵。
然后，u(n) = (A^(n-2)) * u(2)，其中u(2)是向量，包含问题的初始值。这反过来又给出了一个O(log(n))复杂的算法，因为您可以使用快速求幂来计算(A^(n-2))，然后将其乘以u(2).

当然，任何这样的技术都可能需要某种 BigInt，否则溢出几乎是有保证的。

另请注意，此技术可以进一步应用：
您可以找到 A 的特征向量和特征值，然后分解u(2)为特征向量。然后，您将获得 f(n) 和 g(n) 的封闭形式。

我强烈建议您不要使用基于封闭形式的算法
它几乎肯定会涉及高精度浮点计算（除非所有特征值都是整数，这是极不可能的），从编程的角度来看，这些计算至少具有这种复杂性，并且是通常不是恒定时间操作。当然，BigInt 操作也不是。因此，恒定时间算法通常是不可行的，而且您可能甚至不需要O(log(n))，因为对于大多数用途来说，线性就足够了。

注意
这里描述的技术可以用于各种问题，并且在动态优化问题中非常有用。另外，通常人们在第一次看到这个时会印象深刻；）

于 2012-05-02T12:46:06.377 回答