[演算法題目] Nth Fibonacci

本題資訊

難度：easy
使用語言：C++
相關概念：Recursion

---

題目敘述

Write a function that takes in an integer n and returns the nth Fibonacci number.

首先介紹一下 Fibonacci （費波納契）數列的定義：

\(\begin{cases}
F_0 = 0, F_1 = 1 \\
F_n = F_{n-1} + F_{n-2} & \text{ when } n \geq 2
\end{cases}\)

費氏數列最初由 0, 1 兩個數字開始，並且每個數字是前面兩數相加而得出。

Idea 1

可以直接從定義出發，每次回傳的值都是前兩個數相加，前兩個數怎麼來的呢？分別是所在位置的前兩個數相加……如此重複下去。

using namespace std;

int getNthFib(int n) {
  if (n == 1) {
    return 0;
  } else if (n == 2) {
    return 1;
  } else {
    return getNthFib(n - 1) + getNthFib(n - 2);
  }
}

時間複雜度：\(O(2^n)\)，\(n\) 代表 input 的數字。
空間複雜度：\(O(1)\)

Idea 2

仔細想想，Fibonacci 數列中每個數字生成也只需要數列中最後兩個數字，可以只用兩格完成（依定義我只需要前兩個數字即可）。

作法 1

創一個 tmp = {0, 1} 表示數列最開頭的兩個數字，並且設定一個計數器從3開始算。執行一個迴圈，若計數器小於目前的 n，則重複以下步驟：
設定 next 為 tmp 裡面兩個數字（也就是目前數列最後兩個數字）相加，得出目前的 Fibonacci 數並存在 tmp 的第 2 格，tmp 的第 1 格則存放先前在第 2 格的數字。

using namespace std;

int getNthFib(int n) {
  int tmp[] = {0, 1};
  int counter = 3;

  while(counter <= n){
    int next = tmp[0] + tmp[1];
    tmp[0] = tmp[1];
    tmp[1] = next;
    counter++;
  }
  return n > 1 ? tmp[1] : tmp[0];
}

作法 2

這個作法 2 和作法 1 的想法類似，只是作法稍微不同。首先也是創一個 tmp = {0, 1} 表示數列最開頭的兩個數字，但我們不用多設定一個空間 next 了，直接利用 n 和 2 相除的餘數（只會有 0 和 1）當成要改變的 index 即可，算是一種沒那麼直覺的小技巧。

using namespace std;

int getNthFib(int n) {
  int tmp[] = {0, 1};
  for (int i=2; i<n; i++){
    tmp[i%2] += tmp[(i+1) % 2];
  }
  return tmp[(n-1) % 2];
}

時間複雜度：\(O(n)\)，\(n\) 代表 input 的數字。
空間複雜度：\(O(1)\)