題目描述

費氏數通常使用#{{F(n)}}#函數來形成數列,稱為費氏數列。在這個數列中,每個數字都是前兩個數字的和,最前面的兩個數字為01。也就是:



#{{{
\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)}}#。

原題網址

https://leetcode.com/problems/fibonacci-number/

輸入格式

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}}#

題解

費氏數列的函數可以用遞迴的方式輕易完成,但這樣做的效率並不高。由於它只需要考慮到前兩個運算結果的值,因此可以很容易地用迴圈迭代的方式再另外宣告兩個變數來完成。

參考答案