当前位置:编程学习 > C/C++ >>

西电1232 求斐波拉契数列的后四位

Description
定义一个序列:f[0]=0,f[1]=1,f[n]=f[n-1]+f[n-2]。那么,f[10]是多少,f[100]是多少,f[1000]呢...
模拟的话显然最后结果非常大,现在只要你输出f[n]的最后四位,前面的0不输出,若答案为10000,输出0,若答案为10001,输出1.
0 ≤ n ≤ 1,000,000,000
 
 
 
Input
多组数据,每组一个n
Output
f[n]的最后四位
Sample Input
4
Sample Output
3
Hint
Source
LLL
 
看到mod=10000
而有1000000000个数据 那么一定有重复的
如果f(n)==f(1)&&f(n-1)==f(0)  那么这时候循环节就找到了   结果为15000 好像
 
 
[cpp]  
#include<iostream>  
#include<cstdio>  
using namespace std;  
int a[30001];  
int main()  
{  
    int n;  
    a[0] = 0;  
    a[1] = 1;  
    for(int i=2; i<=30000; i++)  
        a[i] = (a[i-1]%10000+a[i-2]%10000)%10000;  
    while(scanf("%d", &n)!=EOF)  
    {  
        if(n <= 30000)  
            printf("%d\n", a[n]);  
        else  
            printf("%d\n", a[n%30000]);  
    }  
    return 0;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,