【面试题9】斐波那契数列

如果我们需要多次计算相同的问题，通常可以选择使用递归或者循环两种不同的方法。递归是在一个函数的内部调用这个函数自身。而循环则是通过设置计算的初始值及终止条件，在一个范围内重复运算。

题目1：写一个函数，输入n，求斐波那契数列的第n项。 斐波那契数列的定义如下： f(n)=0,n=0; f(n)=1,n=1; f(n)=f(n-1)+f(n-2),n>1

效率很低的解法：

long long Fibonacci(unsigned int n) { if(n<=0) return 0; if(n==1) return 1; return Fibonacci(n-1)+Fibonacci(n-2); }

上述的递归解法有很严重的效率问题。用递归的方法计算的时间复杂度是以n的指数的方式递增的。

上述的递归代码之所以慢是因为重复的计算太多，所以需要想办法避免重复计算就可以了。eg：可以把已经得到的数列中间项保存起来，如果下次需要计算的时候先查找一下，如果前面已经计算过就不用再重复计算了。 实用解法：

long long Fibonacci(unsigned n) { int result[2]={0,1}; if(n<2) return result[n]; long long fibNMinusOne=1; long long fibNMinusTwo=0; long long fibN=0; for(unsigned int i=2;i<=n;++i) { fibN=fibNMinusOne+fibNMinusTwo; fibNMinusTwo=fibNMinusOne; fibNMinusOne=fibN; } return fibN; }

题目2：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。