java實作斐波那契數列的3種方法

先說說為什麼寫這個吧,這個完全是由去阿里巴巴面試引起的一次慘目忍睹的血案。去面試的時候，由於面試前天晚上11點鐘才到阿里巴巴指定面試城市，找到旅館住下基本上都1點多，加上晚上完全沒有睡好，直接導致第二天面試效果很不好(對於那些正在找工作的大蝦們不要向小蝦一下悲劇，提前做好準備還是很重要滴)，面試大概進行了一個多小時(面試結束回去的時候基本走路都快睡著了，悲催！！) ，面試快結束的時候面試官問的我問題就是關於費波那西數列，當時頭腦完全漿糊，只知道要設定三個變數或用List先初始化，當寫到for循環的時候，腦袋簡直漿糊的不能再漿糊了，沒寫出來，最後只能在面試官的步步誘導下寫出了下面的第一種方式，很不應該呀；從現在來看阿里只是把粗枝大葉的把整個應用的框架搭建起來了，真是變革、挖金的黃金期(有能力的大蝦趕緊去)，畢竟阿里巴巴手中99%的數據都是重要數據而向百度這類的主推搜索的巨頭99%數據都是垃圾相比，對於數據分析來說，阿里更能透過對手中掌握的多種多樣的用戶詳細數據進行分析，更能精確定位用戶的品味及需求，為精確推送和精準廣告推送提供更好的服務。如果說騰訊未來的夢想是做用戶生活中的水電氣的話，那麼阿里可能實現的未來夢想就是用戶的衣食住行外加代收水電氣等等，O(∩_∩)O~還是轉入正題吧。
   對於優秀的演算法設計員來說，在程式功能主體實現的基礎上無非關心兩個東西，一個設計演算法的時間複雜度，一個是空間複雜度(說白了就是執行一個程式所用的時間和占用的記憶空間)；在根據不同的應用場景的基礎上，一般充滿智慧的演算法設計師會在時間和空間兩個相對矛盾的資源中尋求到平衡點，如實時性要求高的系統一般會以空間資源換取時間或對於常用到的物件一般會常駐記憶體以提高回應時間(快取技術和現在比較流行NoSQL中大多是記憶體資料庫都是如此)，對於記憶體資源比較寶貴的嵌入式系統而言一般會以時間上的延遲來換取時間。
下面從費波那西數列三個實現上來說說，怎麼才能真正設計出真正符合實際應用場景的優秀演算法
首先說說費波那西數列：
從文字上說，費波那西數列由0和1開始，之後的費波那西係數就由之前的兩數相加，數列形式如下：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………
在數學上，是以遞歸的方法來定義：
F_0=0
在數學上，是以遞歸的方法來定義：
F_0=0 F_{n-1}+ F_{n-2}

實現需求：輸入序號n回傳得到對應費波那西數
程式實作1－函數自迭代

/**
  * 函数自迭代
  * @Title: fnType1
  * @Description: TODO
  * @param @param n
  * @param @return    
  * @return int 
  * @throws Exception
  */
 public int fnType1(int n)throws Exception{
  if(n==0){
   return 0;
  }else if(n==1||n==2){
   return 1;
  }else if(n>2){
   int temp=fnType1(n-1)+fnType1(n-2);
   if(temp<0){
    throw new Exception("Invalid value for int type, too larage");
   }else{
    return temp;
   }
  }else{
   throw new Exception("IllegalArgument value for n,please enter n>=0 ");
  }
 }

此種方式缺點：大量迭代不斷消耗棧空間(搞web開發調試維護的都應該知道伺服器棧資源的可貴，如果大量並發調用迭代導致伺服器棧資源遲遲得不到回收，而導致web伺服器崩潰)，效率底，函數自閉性比較弱(優秀的介面應該對輸入輸出可能出現的錯誤訊息進行捕捉，並提供清楚明了的處理結果)，很容易出現錯誤，調試困難，實際應用中一般不建議使用這種方式，使用時迭代次數也不能超過3次；
程式實現2－時間換空間

/**
  * 时间换空间
  * @Title: fnType2
  * @Description: TODO
  * @param @param n
  * @param @return    
  * @return int (n<0 return -1,beyond max int size return -2)
  * @throws
  */
 public int fnType2(int n){
  int result=-1;
  int temp1=0;
  int temp2=1;
  for(int index=0;index<=n;index++){
   if(index==0){
    result=temp1;
   }else if(index==1){
    result=temp2;
   }else{
    result=temp1+temp2;
    if(result<0){
     result=-2;
     break;
    }
    temp1=temp2;
    temp2=result;
   }
  }
  return result;
 }

此方法主要使用於:使用場景一：對於物件或變數使用次數比較少，使用一次以後就不會再使用的場景；使用場景二：對於記憶體資源比較稀缺的即時性要求不是太高的嵌入式系統設計中多會採用此種方式；
程式實現3－空間換取時間

 private static List<Integer> fnData=new ArrayList<Integer>();
 private static final int maxSize=50000;
 /**
  * 初始化器
  * @Title: setFnData
  * @Description: TODO
  * @param     
  * @return void
  * @throws
  */
 private static  void setFnData(){
  int result=-1;
  int temp1=0;
  int temp2=1;
  for(int index=0;index<=maxSize;index++){
   if(index==0){
    result=temp1;
   }else if(index==1){
    result=temp2;
   }else{
    result=temp1+temp2;
    if(result<0){
     result=-2;
     break;
    }
    temp1=temp2;
    temp2=result;
   }
   fnData.add(result);
  }
 }
 /**
  * 对外接口
  * @Title: getFnData
  * @Description: TODO
  * @param @param n
  * @param @return    
  * @return int <span style="font-family: sans-serif;">(n beyond fnData.size() and n<0 return -1)</span>
  * @throws
  */
 public int getFnData(int n){
  if(fnData.size()==0){
   setFnData();
  }
  if(fnData.size()>n&&n>=0){
   return fnData.get(n);
  }else{
   return -1;
  }
 }

此方法一般用於：物件或變數在程式運作的整個生命週期都存在或頻繁呼叫的場景，例如呼叫外部WebService介面、抽象持續化層、常用設定檔參數載入等等
測試案例：

package com.dbc.yangg.swing.test;
import java.util.ArrayList;
import java.util.List;
/**
 * 输入序号n返回得到对应费波那西数
 * @ClassName: Init
 * @Description: TODO
 * @author guoyang2011@gmail.com
 * @date 2014年1月10日 下午7:52:13
 *
 */
public class Init {
 /**
  * 函数自迭代
  * @Title: fnType1
  * @Description: TODO
  * @param @param n
  * @param @return    
  * @return int 
  * @throws Exception
  */
 public int fnType1(int n)throws Exception{
  if(n==0){
   return 0;
  }else if(n==1||n==2){
   return 1;
  }else if(n>2){
   int temp=fnType1(n-1)+fnType1(n-2);
   if(temp<0){
    throw new Exception("Invalid value for int type, too larage");
   }else{
    return temp;
   }
  }else{
   throw new Exception("IllegalArgument value for n,please enter n>=0 ");
  }
 } 
 /**
  * 时间换空间
  * @Title: fnType2
  * @Description: TODO
  * @param @param n
  * @param @return    
  * @return int (n<0 return -1,beyond max int size return -2)
  * @throws
  */
 public int fnType2(int n){
  int result=-1;
  int temp1=0;
  int temp2=1;
  for(int index=0;index<=n;index++){
   if(index==0){
    result=temp1;
   }else if(index==1){
    result=temp2;
   }else{
    result=temp1+temp2;
    if(result<0){
     result=-2;
     break;
    }
    temp1=temp2;
    temp2=result;
   }
  }
  return result;
 }
 private static List fnData=new ArrayList();
 private static final int maxSize=50000;
 /**
  * 空间换时间
  * @Title: setFnData
  * @Description: TODO
  * @param     
  * @return void
  * @throws
  */
 private static  void setFnData(){
  int result=-1;
  int temp1=0;
  int temp2=1;
  for(int index=0;index<=maxSize;index++){
   if(index==0){
    result=temp1;
   }else if(index==1){
    result=temp2;
   }else{
    result=temp1+temp2;
    if(result<0){
     result=-2;
     break;
    }
    temp1=temp2;
    temp2=result;
   }
   fnData.add(result);
  }
 }
 /**
  * 
  * @Title: getFnData
  * @Description: TODO
  * @param @param n
  * @param @return    
  * @return int (n beyond fnData.size() and n<0 return -1)
  * @throws
  */
 public int getFnData(int n){
  if(fnData.size()==0){
   setFnData();
  }
  if(fnData.size()>n&&n>=0){
   return fnData.get(n);
  }else{
   return -1;
  }
 }
 /**
  * 
  * @Title: main
  * @Description: TODO
  * @param @param argv    
  * @return void
  * @throws
  */
 public static void main(String[] argv){
  Init init=new Init();
  int n=46;
  try {
   System.out.println("Type1="+init.fnType1(n));
  } catch (Exception e) {
   // TODO Auto-generated catch block
   System.out.println(e.getMessage());
  }
  System.out.println("Type2="+init.fnType2(n));
  System.out.println("Type3="+init.getFnData(n));
 }
}

輸出結果：

Type1=1836311903  
Type2=1836311903  
Type3=1836311903

对于算法设计，不要盲目遵循概念，概念是死的，人是活的（在这个需要crazy man的时代，有想法比循规蹈矩更有优势），只用结合具体的应用场景才能设计出优秀的算法和结构。
吐槽一下：个人认为优秀的数据结构设计可以简化算法设计的复杂度提高代码的可读性、程序的扩展性及执行效率；
再吐槽一下：做需求分析的时候应该遵循三点原则：1.从用户角度及其思维方式分析；2.用户说的不一定是他们真正想要的；3.用户说的不一定是对的。做程序开发遵循原则：积极提升自身品味，站在用户使用角度和使用场景分析功能；例如你做后台接口开发，你的用户就是接口调用者，你应该考虑接口功能是什么，使用者在什么情况下会调用，传入参数可能导致哪些异常，你的接口实现中可能出现哪些异常并对可能出现的异常进行捕获，清楚明了的输出，良好的函数自闭性；如果你是搞前台，那你应该在保证业务实现的基础上从用户使用习惯等方面把自己当做使用者来设计UI。很有意思对不，需求、开发多了自然就明白了O(∩_∩)O~。

更多java实现斐波那契数列的3种方法相关文章请关注PHP中文网！