題目描述
費氏數通常使用#{{F(n)}}#函數來形成數列,稱為費氏數列。在這個數列中,每個數字都是前兩個數字的和,最前面的兩個數字為0
和1
。也就是:
#{{{
\begin{eqnarray}
F(0) &=& 0, F(1) = 1 \nonumber \\
F(n) &=& F(n - 1) + F(n - 2) \text{, where } n > 1 \nonumber \\
\end{eqnarray}
}}}#
給定#{{n}}#,計算#{{F(n)}}#。
原題網址
輸入格式
0 <= n <= 30
輸出格式
費氏數#{{F(n)}}#。
範例輸入1
n = 2
範例輸出1
1
額外解釋1
#{{F(2) = F(1) + F(0) = 1 + 0 = 1}}#
範例輸入2
n = 3
範例輸出2
2
額外解釋2
#{{F(3) = F(2) + F(1) = 1 + 1 = 2}}#
範例輸入3
n = 4
範例輸出3
3
額外解釋3
#{{F(4) = F(3) + F(2) = 2 + 1 = 3}}#
題解
費氏數列的函數可以用遞迴的方式輕易完成,但這樣做的效率並不高。由於它只需要考慮到前兩個運算結果的值,因此可以很容易地用迴圈迭代的方式再另外宣告兩個變數來完成。