杰拉斯的博客

[ACM_ZJUT_1029]斐波那契数列

杰拉斯 杰拉斯 | 时间:2012-04-03, Tue | 17,725 views
编程算法 

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;
}

如需转载请注明出处:杰拉斯的博客

相关文章

当前暂无评论 »