蓝桥杯BEGIN-4-Fibonacci数列

问题描述

Fibonacci数列的递推公式为：F_n=F_n-1+F_n-2，其中F₁=F₂=1。

当n比较大时，F_n也非常大，现在我们想知道，F_n除以10007的余数是多少。

输入格式 输入包含一个整数n。 输出格式 输出一行，包含一个整数，表示F _n除以10007的余数。

说明：在本题中，答案是要求F_n除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出F_n的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

样例输入 10 样例输出 55 样例输入 22 样例输出 7704 数据规模与约定 1 <= n <= 1,000,000。 总结：第一次程序设计错误；           第二次数据范围问题，输入1000000 返回负数； 

         

#include <iostream> using namespace std; int Fibonacci(int num){ int f1=1,f2=1; if(num==1)return f1007; if(num==2)return f2007; int n=(num+1)/2-1; while(n){ f1=(f1+f2)007; f2=(f1+f2)007; --n; } if(num%2==1) return f1; if(num%2==0) return f2; } int main(){ int num,f,y; cin>>num; y=Fibonacci(num); cout<<y; return 0; } 究极进化版： #include <stdio.h> int main() { unsigned long s=0,f1=1,f2=1,f3=1,n=0; scanf("%d",&n); if(n>2) for(s=3;s<=n;s++) { f3=(f2+f1)007; f1=f2; f2=f3; } printf("%d",f3); return 0; }