pat乙级练习题 斐波那契凤尾

凤尾"/>

pat乙级练习题 斐波那契凤尾

代码思路

斐波那契数列从第30位开始超过六位数，故只需将每次结果对1000000求余，之后在输出时检查是第几位决定输出格式

解题代码

#include<iostream>
#include<iomanip>
using namespace std;#define MAXN 100001long long F[MAXN];
bool B[MAXN];int main(){int n;F[1] = 1;F[2] = 2;for (int i = 3; i < MAXN; i++){F[i] = (F[i - 1] + F[i - 2]) % 1000000;}while (scanf("%d", &n) != EOF){if(n <= 29)cout<<F[n]<<endl;elsecout<<setfill('0')<<setw(6)<<F[n] % 1000000<<endl;}return 0;
}