Cille希乐水杯塑料:与乐高塑料砖的组合数 C++(g bricks)

关于Cille希乐水杯塑料的问题,在g bricks中经常遇到, 您有一些乐高塑料砖,所有砖都是 1x1x1。您还有一个 1xN(N & lt;= 80)的瓷砖,您应该在其上放置乐高砖。您可以按顺序订购它们(如果有 3 个或更多连续的砖块,则一个序列是正确的),并且在 2 个序列之间必须至少有 1 个空白空间。您应该计算可以将砖块放在砖块上的不同组合

您有一些乐高塑料砖,所有砖都是 1x1x1。您还有一个 1xN(N & lt;= 80)的瓷砖,您应该在其上放置乐高砖。您可以按顺序订购它们(如果有 3 个或更多连续的砖块,则一个序列是正确的),并且在 2 个序列之间必须至少有 1 个空白空间。您应该计算可以将砖块放在砖块上的不同组合

是一个例子:

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

输入:7 输出:17

pic of the example
(source: mendo.mk)

此外,如果你没有砖,它被视为 1 组合。

我已经解决了这个问题,我找到了计算可能的组合的方法,如果瓦片的最大长度是 14(3 个序列)。

我最大的问题是我需要运行的 for 循环的巨大数量。例如,对于 1 个序列,我使用 1 个循环,对于 2 个序列 2 个循环 + 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;
}
10

如果这是一个计数问题(不是输出组合,而只是计数它们),这是一个简单的问题。假设我们现在解决了 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

样品:

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 循环来解决它。

Why:

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 个连续的砖垒,它们可以在任何有效解之后。

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)),然后将其乘以

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

还请注意,此技术可以进一步应用:
您可以找到 A 的特征向量和特征值,然后将u(2)分解为特征向量。然后,您将为 f(n)和 g(n)提供一个封闭形式。

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

注意
这里描述的技术可以在各种问题中使用,并且在动态优化问题中具有极端的用途。另外,通常人们在第一次看到这一点时会印象深刻;)

本站系公益性非盈利分享网址,本文来自用户投稿,不代表码文网立场,如若转载,请注明出处

(358)
德力西c63漏电保护器接线图:使用 devtoolset-8安装VirtualBoxGuestAdditions时启用了堆栈保护
上一篇
Goo s:跟随鼠标指针的 Goo球(gooball)
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(21条)