[ACM_ZJUT_1029]斐波那契数列

Fibonacci数

Time Limit:1000MS Memory Limit:32768K

Description:
有一些整数（≤46），输出以这些整数为序数的第n项fibonacci数。文件中的数据可能上万，但要求运行时间不超过1秒钟。

注：f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2).

Sample Input:
5
6
7
8
9
40

Sample Output:
5
8
13
21
34
102334155

Source
ZJUT1029

如果我们使用递归或分治法的思想，可以得到代码：

#include<stdio.h>
int f(int n){
	if(n == 0)
		return 0;
	else if(n == 1)
		return 1;
	return f(n - 1) + f(n - 2);
}
int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		printf("%d\n", f(n));
	}
	return 0;
}

但这段代码的结果必定是TLE，因为问题的子问题大量重复，即：

f(n)
= f(n-1) + f(n-2)
= f(n - 2) + f(n - 3) + f(n - 1) + f(n - 2)
= f(n - 3) + f(n - 4) + f(n - 4) + f(n - 5) + f(n - 2) + f(n - 3) + f(n - 3) + f(n - 4)
 = ...

这样下去，当n比较大时，运算量将是极为恐怖的，我们可以用经典的空间换时间的思想，将数列前两位先储存到数组中，后面的斐波那契数直接通过已储存的数字相加得出，用户输入时直接从数组读取，这样便可以节省出大量的时间：

#include<stdio.h>
int main(){
	int f[47];
	f[0] = 0;
	f[1] = 1;
	for(int i = 2; i < 47; ++i){
		f[i] = f[i - 1] + f[i - 2];
	}
	int n;
	while(scanf("%d", &n) != EOF){
		printf("%d\n", f[n]);
	}
	return 0;
}

原文地址（本人博客）：http://lanfei.sinaapp.com/2012/04/457.html

欢迎访问交流。