第19题（数组、递归）： 题目：定义Fibonacci数列如下：   / 0 n=0 f(n)= 1 n=1 / f(n-1)+f(n-2) n>=2 输入n，用最快的方法求该数列的第n项。 分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。

因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。

思路：斐波那契数列，学过计算机的人应该都知道的。就像july大神在题目里说的那样，我们大多数在学习时都是采用的递归的思路来解的。因为这样写出来的代码，思路上非常清晰。与数列的定义基本一致。但是，这样做的结果是时间复杂度比较高，基本上是指数级的。所以，我们现在要做的就是，尽量不用递归的思路来做。如果采用数组的方法，来做，时间复杂度为O(n),空间复杂度也为O(n),这样做虽然时间上快了不少，但是空间浪费也是比较大的。经过观察，因为，在计算第n个数的时候，只需要它的前两个数，所以我们其实并不需要用数组把计算的来的数全保存下来，只要申请两个变量，保存两个就可以了。这应该算是迭代的思想。

在编程之美上，我还看到过另一种方法，时间复杂度在O(lg n)，主要是利用矩阵的思路。我数学不好，让我自己想是不太容易想出来的，所以仅供欣赏把。

贴上迭代的代码：

/*===================================================*\第19题（数组、递归）：题目：定义Fibonacci数列如下：  / 0 n=0f(n)= 1 n=1/ f(n-1)+f(n-2) n>=2输入n，用最快的方法求该数列的第n项。分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。\*===================================================*/#include 
    
     using namespace std;int fibonacci(int n){	int first = 0;	int second = 1;	int ret = 0;	if(0 == n){		return first;	}	if(1 == n){		return second;	}	int i = 2;	while(i++ <= n){		ret = first + second;		first = second;		second = ret;	}	return ret;}int main(){	int n = 0;	cin >> n;	int ret = fibonacci(n);	cout << "n = " << n << ": " << ret << endl;	return 1;}