Fibonacci数列

时间: 1ms        内存:128M

描述:

Fibonacci数列,定义如下: 
f(1)=f(2)=1 
f(n)=f(n-1)+f(n-2) n>=3。 
计算第n项Fibonacci数值,注意要求最后的结果要保留最后9位 

输入:

多组输入,每次输入一个整数N(1<=N<=100)。

输出:

输出为N行,每行为对应的f(Pi)。 

示例输入:

1
2
3
4
5

示例输出:

1
1
2
3
5

提示:

参考答案(内存最优[1120]):

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

参考答案(时间最优[1]):

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n,i;;
    while(scanf("%d",&n)!=EOF){
        unsigned long long int a[n];
        a[0]=1;a[1]=1;
        for(i=2;i<n;i++)
            a[i]=(a[i-1]+a[i-2])%1000000000;
        printf("%lld\n",a[n-1]);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。