Fibonacci数列

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

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