LEGOプラスチックレンガとの組み合わせ数C++

Question

いくつかのLEGOプラスチックレンガがあります。すべてのレンガは1x1x1です。また、1xN（N < = 80）のタイルが1つあり、その上にLEGOレンガを置く必要があります。シーケンスを順番に並べることができます（連続したレンガが3つ以上ある場合は1つのシーケンスが正しい）。また、2つのシーケンスの間に少なくとも1つの空きスペースが必要です。あなたはタイルにレンガを置くことができる異なる組み合わせの数を計算する必要があります。ここで

は例です：

タイルが1x7の場合は、17種類の組み合わせがあります。

入力：7 出力：あなたは何のレンガを持っていない場合は17

pic of the example http://mendo.mk/task_files/kocki.gif

また、それは1つの組み合わせとしてカウントされます。

私はこの問題に取り組みました。タイルの最大長さが14（3シーケンス）である場合の可能な組み合わせを計算する方法を発見しました。 forループを使って見つけました。

私の最大の問題は、実行する必要があるforループの膨大な数です。たとえば、1シーケンスの場合は1つのループを使用し、2つのシーケンスの場合2つのループ+ 1の場合は1つのsequnce ...したがって、80のレンガをすべて使用すると、20シーケンスを作成できます。巨大な数。だから、私はそれらを1つに入れ子にしてもいい。私はそれを試して、それは乱雑になり、それは正解を与えていない。

新コード：

#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

このカウントされた問題（outputingない組み合わせがちょうどそれらをカウント）した場合には、それは簡単です。 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)のループのための1でそれを解決することができます。

---

理由：

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

まず最初の部分を証明してみましょう：

は、我々は（N）（N）最後の項目でプラスチックのレンガを持って作業溶液、およびGはFを想定していることを忘れないでください最後の項目でレンガを持っていないワーキングソリューションです。

f（n + 1）はf（n）の方法を続けることができ、最後の場所に1つのブリックを追加することを意味します。 また、f（n + 1）は、g（n-2）の後に3つのレンガを追加することによって作ることができ、n-1、n、n + ）またはg（n）を使用してf（n + 1）の有効解を作成します（連続レンガ数は3未満です）。また、f（n）によって以前に列挙されているので、g（n-3）の後にレンガを追加することによって生じる方法の数を数える必要はないことにも注意してください。だから我々はf(n+1) = f(n) + g(n-2)を持っている。

g（n + 1）は、有効な解をnから簡単に作ることができるため、空きスペースに3つのブリック制限が存在しないため、このケースは簡単です。任意の有効後ソリューション。

Answer 2

CSではなく、数学の訓練を受けている人として、Saeed Amiriのアルゴリズムは非常に素晴らしく、おそらく数百万にも達するまで高速に動作するだろうと言わざるを得ません。時間の観点からは、より良いアルゴリズムがあります。

彼が去ったところ私がピックアップします：

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)| 

何本から以下は、Aは上記の行列であるu(n) = A * u(n-1)、です。
u(n) = (A^(n-2)) * u(2)ここで、u(2)は、問題の初期値を含むベクトルです。これは、(A^(n-2))を計算するために高速累乗を使用してからu(2)にそれを掛けることができるので、O(log(n))の複雑さを持つアルゴリズムを与えます。

当然のことながら、そのようなテクニックはおそらく何らかの種類のBigIntを必要とするでしょう。さもなければオーバーフローがかなり保証されるからです。

はまた、この技術は、さらに一歩適用することができることに注意してください。
あなたはAの固有ベクトルと固有値を検索し、固有ベクトルにu(2)を分解することができます。次に、f（n）とg（n）の両方について閉じた形式を持つことになります。

私は強く、少なくともである、（すべての固有値は非常に低いです整数、でない限り）それはほぼ確実に高精度の浮動小数点演算を必要とするだろう閉じた形
に基づくアルゴリズムに対して、あなたをアドバイスこの複雑さはプログラミングの視点からのものであり、一般的には一定時間の操作ではありません。もちろん、どちらもBigInt操作ではありません。したがって、一定時間アルゴリズムは一般的に実行可能ではありません。さらに、ほとんどの場合、線形性が十分であるため、おそらくO(log(n))は必要ありません。

注
は、ここで記載された技術は、様々な問題で使用され、動的最適化問題の極端な使用であることができます。プラス、通常、人々はこれを初めて見るとかなり印象づけられています;）