Sum All Odd Fibonacci Numbers

What is "Fibonacci Numbers" ? 　　　　　Fibnacci Series wiki↓

　　費氏數列(Fibonacci Series)在數學上是以遞迴的方法來定義： Fib(0) = 1, Fib(1) = 1, Fib(n) = Fib(n-1) + Fib(n-2) if n> 2 用文字來說，就是費波那契數列由0和1開始，之後的費波那契系數就由之前的兩數相加。首幾個費波那契系數是:0, 1, 1, 2, 3, 5, 8, 13，題目要求為: 將奇數項的數字加總 
  function sumFibs(num) {
  var result = 0;
  function fibs(n)
  {
    return (n == 1 || n == 2) ? 1 : fibs(n-1) + fibs(n-2);
  }
  for(var i=1;i<=num;i++)
  {
    if(fibs(i) <= num  && (fibs(i)%2) == 1 )
      result += fibs(i);
  }
  return result;
}
sumFibs(4);
sumFibs(1000);
sumFibs(4000000);
sumFibs(75025);

Solution　1:
用遞迴方法來寫費氏數列，再依據題目要求寫入條件式:小或等於傳入的數字以及此項為奇數(以2取餘數為1)，然後按下執行，會發現Browser卡住，可能會以為程式當掉，其實不是，是因為遞迴計算所需要花的時間與空間太大(尤其到後面計算數字需求太大-基數太大)，以演算法來說，就是複雜度太大，造成執行效率的不佳(耗時且耗空間stack)，雖然最後程式有執行完，但是也有可能發生crash的狀況

 
function sumFibs(num) {
  var result = 0;
  function fibs(n)
  {
    var temp ;
    var x = 1 , y = 1;  
    for(var i=3;i<=n;i++)
    {
       temp = x + y;
       x = y;
       y = temp;
    }
    return (n == 1 || n == 2) ? 1 : temp;
  }
  for(var i=1;i<=num;i++)
  {
    if(fibs(i) <= num  && (fibs(i)%2) == 1 )
      result += fibs(i);
  }
  return result;
}
sumFibs(4);
sumFibs(1000);
sumFibs(4000000);
sumFibs(75025);

Solution 2:
既然用遞迴方法的複雜度太大，則用loop來試試看，按下執行後，我們可以發現結果差很多，因為迴圈不需要的複雜度頂多會執行n次而已，不像遞迴可能會到2的冪次方，更多關於複雜度的內容可能之後會再遇到，到時候會在討論



P.S. / Reference:　　about Recursion

results matching ""

    No results matching ""