劍指offer系列之斐波那契數列

代碼

    
      package com.study;

/*
 * 求斐波那契數列第n個數字 
 * */
public class suanfa7 {
	
	/*最原始的遞歸版，思路簡潔，但是如果輸入參數較大，會造成棧的深度太深，運行會很慢*/
	public static int Fibonacci1(int num) {
		if(num <= 1)
			return num;
		
		else
			return Fibonacci1(num - 1) + Fibonacci1(num - 2);
	}
	
	/*第二種方法，算法復雜度為O(n),利用一種迭代的思路，避免了遞歸的入棧等操作，提高了時間效率
	 * 但是如果數字超過了30可能就需要把返回類型改成long了*/
	public static int Fibonacci2(int num) {
		if(num <= 1)
			return num;
		else {
			int sum = 1;
			int preNum = 1;
			int prepreNum = 0;
			int i = 2;
			while(i < num) {
				prepreNum = preNum;
				preNum = sum;
				sum = prepreNum + preNum;
				i++;
			}
			
			return sum;
		}
	}
	
	
	public static void main(String[] args) {
		System.out.println(Fibonacci2(10));
	}
}
    <pre>
    
  

備注：

1.斐波那契數列雖然看似簡單，但是要考慮清楚實際的情況，要不斷優化算法的復雜度。

2.另外，對于迭代這種思路，以前很沒有感覺，就覺得沒有一種屬于自己的快速的方法，可以看出迭代量。突然想到，調試的時候，觀察變量的時候，經常用列表的方法去看值，直觀對比，那么寫程序的時候不妨也列表試試，果然相當有效果，迭代量是什么一目了然。

之后只要順著思路寫程序即可。

3.斐波那契數列的應用場景很多：

典型的比如：青蛙跳臺階問題，矩形覆蓋問題等。解決這種問題的思路關鍵在于看能否找到一種遞歸關系

    
      f(n) = f(n-1) + f(n - 2)
    
  

如果找到這種遞推關系，則很容易想到是斐波那契數列。

以后遇到數列題，一般首先應該想到是斐波那契數列 。

斐波那契數列