LintCode: Fibonacci 費布那西數列

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 https://www.lintcode.com/problem/fibonacci/description。

 從Wiki的說明：
在數學上，費波那契數列是以遞迴的方法來定義：

  • F_0=0
  • F_1=1
  • F_n = F_{n-1}+ F_{n-2}（n≧2）

所以先用Recursion解，結果Time Limit Exceeded了。

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution{
public:
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    int fibonacci(int n) {
        // write your code here
        if(n < 3)
            return n - 1;
        else {
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }
};

 只好換成Iteration囉。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution{
public:
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    int fibonacci(int n) {
        // write your code here
        if(n < 3)
            return n - 1;
        else {
            int i;
            int* f = new int[n];
            f[0] = 0;
            f[1] = 1;
            i = 2;
            while(i < n) {
                f[i] = f[i - 1] + f[i - 2];
                i++;
            }
            return f[n-1];
        }
    }
};

Labels: ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)