Fibonacci Number

0, 1, 1, 2, 3, 5, 8…

背景知識

• Python 基礎語法

F(0) = 0
F(1) = 1
F(n) = F(n-2) + F(n-1), n = 2, 3, 4…

理解問題

• 爬樓梯
• 不死兔子

思路視覺化

0, 1, 1, 2, 3, 5…

f(1) = 0+1 == 1
f(2) = 1+1 == 2
f(3) = 1+2 == 3 # f(1)+f(2)
f(4) = 2+3 == 5 # f(2)+f(3)

f(n) = f(n-2) + f(n-1), n = 2, 3, 4…

Python

TC: O(2ˆn), SC: O(n)
def recur_fibo(n):
  if n< 2: return n
  else:
    return recur_fibo(n-2) + recur_fibo(n-1)

TC: O(n), SC: O(n)
memo={}
def memo_fibo(n):
    if n in memo: return memo[n]
    if n<2: return n
    memo[n] = memo_fibo(n-1)+ memo_fibo(n-2)
    return memo[n]

TC: O(n), SC: O(1)
def series_fibo(n):
  a,b = 1,0
  for _ in range(n):
    a,b = a+b,a
  return a

Java

// 1,1,2,3,5,8

class Fibonacci {
public static void main(String[] args){
    int index = 4;
    //System.out.println(recur_fibo(index+1));
    //System.out.println(memo_fibo(index+1));
    System.out.println(series_fibo(index));
}
public static long recur_fibo (int n){
    if (n<2) return n;
    long ret = recur_fibo(n - 1) + recur_fibo(n - 2);
    return ret;
}

public static long memo_fibo (int n){
    long[] memo = new long[n+1];
    if(memo[n] ==0){
        if (n < 2) {
            memo[n] = n;
        } else {
            memo[n] = memo_fibo(n - 1) + memo_fibo(n - 2);
        }
    }
    return memo[n];
}

static int a=0,b=1,c=0;  
public static long series_fibo (int n){
    if(n>0){
        c = a + b;
        a= b;
        b= c;
        series_fibo(n-1);
    }
    return c;
}
}

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)