1147.斐波拉切数列——如何减少递归次数

题目：

Description Fibonacci数列定义为（1,1,2,3,5,8,…..），即每个元素是前两个元素的和。如果一个Fibonacci数与所有小于它的Fibonacci数互质，那么称之为Fibonacci质数。 现在要求你输出前n个Fibonacci数 The Fibonacci Numbers {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …} are defined by the recurrence: F(0)=0 F(1)=1 F(i)=F(i-1)+F(i-2) Write a program to calculate the Fibonacci Numbers.

Input The first line of the input file contains a single integer T, the number of test cases. The following T lines,each contains an integer n ( 0 <= n <= 45 ), and you are expected to calculate Fn

Output Output Fn on a separate line.

Sample Input 5 0 3 5 9 20

Sample Output 0 2 5 34 6765

原始方法：

在斐波拉切数列中，如果直接使用这样的递归式：

Fibonacci(n) = Fibonacci(n-1)+Fibonacci(n-2);

那么需要的时间就很长。

改进：

通过递归树发现，上面的递归式有很多重复的计算，所以我们可以使用一个数组用来存放已经算过的值，这样就可以减少很多计算量。代码如下：

#include<stdio.h> #include<string.h> int b[100];//数组b就是用来存放已经算过的数 int Fibonacci(int n) { if(b[n]!=-1) return b[n]; else b[n] = Fibonacci(n-1)+Fibonacci(n-2); return b[n]; } int main() { int n,a[100]; scanf("%d",&n); memset(b,-1,sizeof(b)); b[0] = 0; b[1] = 1; for(int i=0;i<n;i++) { scanf("%d",&a[i]); } for(int i=0;i<n;i++) { printf("%d\n",Fibonacci(a[i])); } return 0; }