斐波那契数列
时间限制(普通/Java)
:
1000 MS/ 10000 MS 运行内存限制 : 65536 KByte
总提交 : 5750 测试通过 : 2053
比赛描述
在数学上，斐波那契数列（
Fibonacci Sequence
），是以递归的方法来定义：
F0 = 0
F1 = 1
Fn = Fn – 1 + Fn – 2
用文字来说，就是斐波那契数列由
0
和
1
开始，之后的斐波那契数就由之前的两数相加。首几个斐波那契数是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
，………………
特别指出：
0
不是第一项，而是第零项。
在西方，最先研究这个数列的人是比萨的列奥纳多（又名斐波那契），他描述兔子生长的数目时用上了这数列。
n 第一个月有一对刚诞生的兔子
n 第两个月之后它们可以生育
n 每月每对可生育的兔子会诞生下一对新兔子
n 兔子永不死去
假设在
n
月有新生及可生育的兔子总共
a
对，
n+1
月就总共有
b
对。在
n+2
月必定总共有
a+b
对：因为在
n+2
月的时候，所有在
n
月就已存在的
a
对兔子皆已可以生育并诞下
a
对后代；同时在前一月
(n+1
月
)
之
b
对兔子中，在当月属于新诞生的兔子尚不能生育。
现请以较短的时间，求出斐波那契数列第
n
项数值，
0
≤
n
≤
40
。
输入
斐波那契数列项数
n
，
0
≤
n
≤
40
。
输出
斐波那契数列第
n
项数值
样例输入
4
样例输出
3
题目来源
NUPT
第一次的答案：
#include<stdio.h>
int fun(int a)
{
if(a == 0)
return 0;
if(a==1 || a==2)
return 1;
else
return fun(a-1) + fun(a-2);
}
int main()
{
int a = 0;
scanf("%d", &a);
if(a> 40)
return 0;
int sum = fun(a);
printf("%d\n", sum);
return 0
}
代码 很简洁 但是 却显示 时间 超限。 想想也是 递归的实质 是由上之下的调用，最后在层层 回调， 而fun(a-1) + fun(a-2)很多都是重复的 。
后来 重写一个 谢天谢地过了：
#include<stdio.h>
#define N 41
int main()
{
int num = 0, sum = 0;
int a[N]={0};
a[0] = 0;
a[1] = 1;
a[2] = 1;
int i =0;
scanf("%d", &num);
if(num > 40)
if(num == 0)
{
printf("0\n");
return 0;
}
else if(num == 1 || num == 2)
{
printf("1\n"); return 0;
}
for(i=3; i<=num; i++)
{
if(a[i] == 0)
{
a[i] = a[i - 1] + a[i-2];
}
}
printf("%d\n", a[num]);
return 0;
}
注意 N = 41，
#include<stdio.h>
#include <sys/time.h>
int fun(int a)
{
if(a == 0)
return 0;
if(a==1 || a==2)
return 1;
else
return fun(a-1) + fun(a-2);
}
int main()
{
struct timeval start, end;
gettimeofday(&start, NULL);
int a = 40;
// scanf("%d", &a);
if(a> 40)
return 0;
int sum = fun(a);
gettimeofday(&end, NULL);
printf("%d\n", sum);
int timeuse = 1000000*(end.tv_sec -start.tv_sec) + end.tv_usec - start.tv_usec;
printf("seconds: %d us\n", timeuse);
return 0 ;
}
： 102334155
seconds: 745969 us
#include<stdio.h>
#include<sys/time.h>
#define N 41
int main()
{
struct timeval start, end;
gettimeofday(&start, NULL);
int num = 40, sum = 0;
int a[N]={0};
a[0] = 0;
a[1] = 1;
a[2] = 1;
int i =0;
// scanf("%d", &num);
if(num > 40)
if(num == 0)
{
printf("0\n");
return 0;
}
else if(num == 1 || num == 2)
{
printf("1\n"); return 0;
}
for(i=3; i<=num; i++)
{
if(a[i] == 0)
{
a[i] = a[i - 1] + a[i-2];
}
}
printf("%d\n", a[num]);
gettimeofday(&end, NULL);
<span style="white-space:pre"> </span>int timeuse = 1000000*(end.tv_sec -start.tv_sec) + end.tv_usec - start.tv_usec;
printf("seconds: %d us\n", timeuse);
return 0;
}
：102334155
seconds: 23 us