[LeetCode]費氏數(Fibonacci Number)

題目描述

費氏數通常使用#{{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

範例輸出1

額外解釋1

#{{F(2) = F(1) + F(0) = 1 + 0 = 1}}#

範例輸入2

範例輸出2

額外解釋2

#{{F(3) = F(2) + F(1) = 1 + 1 = 2}}#

範例輸入3

範例輸出3

額外解釋3

#{{F(4) = F(3) + F(2) = 2 + 1 = 3}}#

題解

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

impl Solution {
    pub fn fib(n: i32) -> i32 {
        match n {
            0 => 0,
            1 => 1,
            _ => {
                let mut n_1 = 1;
                let mut n_2 = 0;
                
                for _ in 2..=n {
                    let temp = n_1;
                    n_1 += n_2;
                    n_2 = temp;
                }
                
                n_1
            }
        }
        
    }
}

const fib = (n: number): number => {
    switch (n) {
        case 0:
            return 0;
        case 1:
            return 1;
        default: {
            let n1 = 1;
            let n2 = 0;

            for (let i = 2;i <= n;i++) {
                const temp = n1;
                n1 += n2;
                n2 = temp;
            }

            return n1;
        }
    }
};