UVA-900 - Brick Wall Patterns

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 相同題目：ZOJ-d038

題意概要

題目假設牆的高度為 $2$，並給定牆之長度，試問：要築起這道牆，磚塊的排列總共有多少種樣式。規則如下：

• 寛度為 $1$ 單位的牆只有一種花樣—就是讓磚塊直立。
• 長度為 $2$ 的牆有 $2$ 種花樣—兩個平躺的磚磈疊在一起以及兩個直立的磚塊併在一起。
• 長度為 $3$ 的牆有三種花樣。
• 長度為 $4$ 的牆你可以找出幾種花樣？

• 分析：本題為簡單的數學問題。可以利用題目給定的規則，會發現本題的排列規則，其實就是「費氏數列 (Fibonacci series)」，但本題有時間限制，所以要改寫成「迴圈版本」。唯獨要注意的是，本題的測資範圍要使用 long long int。

Input

Your program receives a sequence of positive integers, one per line, each representing the length of a wall. The maximum value for the wall is length $50$. The input terminates with a 0.

Output

For each wall length given in the input, your program must output the corresponding number of different patterns for such a wall in a separate line.

Sample Input

1
2
3
0

Sample Output

1
2
3