斐波那契数列

问题描述

写一个函数，输入n，求斐波那契数列的第n项

思路分析

这个数列是一个迭代的数列，所以用递归很容易求出来，但是会存在效率问题

码上有戏
低效率解法

public long method1(int n){
		if(n==0)
			return 0;
		else if(n==1)
			return 1;
		else
			return method1(n-1)+method1(n-2);
	}

此时利用递归会发现，最终会有很多重复的计算

非递归解法

public long method2(int n){
		long result=0;
		long preOne=0;
		long preTwo=1;
		if(n==0){
			return preOne;
		}
		if(n==1){
			return preTwo;
		}
		for(int i=2;i<=n;i++)
		{
			preOne=preTwo;
			preTwo=result;
			result=preOne+preTwo;
		}
		return result;
	}

该算法核心就是把每次数列的结果缓存，这样就不用重复计算了