每天一道劍指offer-牛客網斐波那契數列

• 2019 年 10 月 4 日
• 筆記

題目詳述

大家都知道斐波那契數列，現在要求輸入一個整數n，請你輸出斐波那契數列的第n項（從0開始，第0項為0）。 n<=39

題目詳解

思路

• f(n) = f(n-1) + f(n-2)，第一眼看就是遞歸啊，簡直完美的遞歸環境，遞歸肯定很爽，這樣想着關鍵代碼兩三行就搞定了，注意這題的n是從0開始的： if(n<=1) return n; else return Fibonacci(n-1)+Fibonacci(n-2); 然而並沒有什麼用，測試用例里肯定準備着一個超大的n來讓Stack Overflow，遞歸本質是利用棧，棧深度太深就會溢出；
• 非遞歸的方法，就是劍指offer思路，每次使用兩個變量a,b來計算下一個數的值sum,然後a,b,sum分別是斐波那契數列中的三個數，那麼就令a=b,b=sum,這樣a和b就往下移動了一個位置，再計算sum就是滴4個數了，重複這個過程即可。

代碼

public class Solution {      public int Fibonacci(int n) {          int a = ;          int b = ;          if(n == )              return ;          if(n == )              return ;          int i = ;          int sum=;          while(i <= n)          {              sum = a + b;              a = b;              b = sum;              i++;          }          return sum;      }  }  

代碼講解

• 3-8行就是初始值n的個數為0或者1，直接返回當前結果
• 11-17行就是計算斐波那契數列的下一個數，其中i用來統計計算出了幾個數，循環終止條件。