大神的世界

此題答案為畢氏數列的第n項

長度為n的牆可視為

長度為n-1的牆 +1

長度為n-2的牆 +2

故數列第n項 = 第n-1項 + 第n-2項

到這頗似有理，但我實在很懷疑

難道牆的排列方式不會重複嗎?

例如:

我現在要問長度為4的牆

於是我就去找長度為2跟3的牆

長度為2:  11    2

長度為3:  111 12  21

現在，我把長度為2的牆+2

長度為3的牆+1

那麼

11 + 2 -> 112 (長度為2 +2)

1 + 12 ->  112 (長度為3 +1)

不會重複嗎?

於是我就很無聊的把它列出來

(種類     可能的排列數量       計算方式)

長度為3

21                   2                    C(2,1)
111                 1                     C(3,0)

長度為4

22                   1                    C(2,2)
211                 3                     C(3,1)
1111               1                      C(4,0)

長度為5

221                 3                    C(3,2)
2111               4                    C(4,1)
11111             1                     C(5,0)

長度為6

222                 1                    C(3,3)
2211               6                    C(4,2)
21111             5                     C(5,1)
111111           1                      C(6,0)

透過 C(n, r-1) + C(n, r) = C(n+1, r)

我們可以確定，真的是畢氏數列!!!!!!

#include <iostream>

#define N 51

using namespace std;

unsigned long long int arr[N];

void setTable()
{
    arr[0] = arr[1] = 1;

    for(int i = 2; i<N; i++)
        arr[i] = arr[i-1] + arr[i-2];
}

int main()
{
    int length;

    setTable();

    while(cin >> length && length)
        cout << arr[length] << endl;

    return 0 ;
}