斐波那契数列的3种java程序实现 - JAVA

先说说为什么写这个吧,这个完全是由去阿里巴巴面试引起的一次惨目忍睹的血案。去面试的时候，由于面试前天晚上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_1=1$

$F_n = F_{n-1}+ F_{n-2}$

实现需求：输入序号n返回得到对应费波那西数

程序实现1――函数自迭代

/**
	 * 函数自迭代
	 * @Title: fnType1
	 * @Description: TODO
	 * @param @param n
	 * @param @return    
	 * @return int
	 * @throws
	 */
	public int fnType1(int n){
		if(n==0){
			return 0;
		}else if(n==1||n==2){
			return 1;
		}else if(n>2){
			int temp=fnType2(n-1)+fnType2(n-2);
			return temp;
		}else{//n<0
			return -1;
		}
	}

此种方式缺点：大量迭代不断消耗栈空间(搞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
    
      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; } }

此方法一般用于：对象或变量在程序运行的整个生命周期都存在或频繁调用的场景，如调用外部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
	 */
	public int fnType1(int n){
		if(n==0){
			return 0;
		}else if(n==1||n==2){
			return 1;
		}else if(n>2){
			int temp=fnType2(n-1)+fnType2(n-2);
			return temp;
		}else{//n<0
			return -1;
		}
	} 
	/**
	 * 时间换空间
	 * @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; System.out.println("Type1="+init.fnType1(n)); System

斐波那契数列的3种java程序实现(一)