劍指offer系列之斐波那契數(shù)列

代碼

    
      package com.study;

/*
 * 求斐波那契數(shù)列第n個(gè)數(shù)字 
 * */
public class suanfa7 {
	
	/*最原始的遞歸版，思路簡(jiǎn)潔，但是如果輸入?yún)?shù)較大，會(huì)造成棧的深度太深，運(yùn)行會(huì)很慢*/
	public static int Fibonacci1(int num) {
		if(num <= 1)
			return num;
		
		else
			return Fibonacci1(num - 1) + Fibonacci1(num - 2);
	}
	
	/*第二種方法，算法復(fù)雜度為O(n),利用一種迭代的思路，避免了遞歸的入棧等操作，提高了時(shí)間效率
	 * 但是如果數(shù)字超過(guò)了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.斐波那契數(shù)列雖然看似簡(jiǎn)單，但是要考慮清楚實(shí)際的情況，要不斷優(yōu)化算法的復(fù)雜度。

2.另外，對(duì)于迭代這種思路，以前很沒(méi)有感覺(jué)，就覺(jué)得沒(méi)有一種屬于自己的快速的方法，可以看出迭代量。突然想到，調(diào)試的時(shí)候，觀察變量的時(shí)候，經(jīng)常用列表的方法去看值，直觀對(duì)比，那么寫(xiě)程序的時(shí)候不妨也列表試試，果然相當(dāng)有效果，迭代量是什么一目了然。

之后只要順著思路寫(xiě)程序即可。

3.斐波那契數(shù)列的應(yīng)用場(chǎng)景很多：

典型的比如：青蛙跳臺(tái)階問(wèn)題，矩形覆蓋問(wèn)題等。解決這種問(wèn)題的思路關(guān)鍵在于看能否找到一種遞歸關(guān)系

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

如果找到這種遞推關(guān)系，則很容易想到是斐波那契數(shù)列。

以后遇到數(shù)列題，一般首先應(yīng)該想到是斐波那契數(shù)列 。

斐波那契數(shù)列