費波那西數列(Fibonacci)

費波那西是一個兔子生兔子的故事...關於內容的介紹可以參考這一篇閱讀(http://pansci.asia/archives/111546)，這邊我們專注於如何使用演算法來實現我們預期的結果。

CodePen中包含Divide and Conquer(分治法)與Dynamic Programming(動態規劃)，兩種方式來求解數列。

https://codepen.io/AllenShi/pen/JLeOyg?editors=1111

1.分治法進行運算

function FibonacciDC(n) {
  if (n == 0)
    return 0;
  if (n == 1)
    return 1;
  return Fibonacci(n - 1) + Fibonacci(n - 2);
}
data = FibonacciDC(4)
console.log('分治法版本：'+data)

2.動態規劃-遞迴版本

var map = [0,1]
function FibonacciRecursive(n) {
   if(typeof map[n] !== 'undefined') {
     return map[n];
   }
   map[n] = FibonacciRecursive(n-1) + FibonacciRecursive(n-2); 
   return map[n];
}
data = FibonacciRecursive(4)
console.log('遞迴版本：'+data)

3.動態規劃-迴圈版本

function Fibonacci(n) {
   // F(0) = 0, F(1) = 1 使用map給予固定的答案
   var map = [0,1]
   for (i = 2; i <= n; ++i){
      // 公式轉換
      map[i] = map[i - 1] + map[i - 2];
   }
   return map[n];
}
data = Fibonacci(4)
console.log('迴圈版本：'+data)