斐波那契数列(2)

佚名 6年前 (2019-04-26) 随笔 1383人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

【真题出处】

【题目描述】

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。

【输入】

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 ≤ a ≤ 1000000)。

【输出】

n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到的结果。

【输入样例】

【输出样例】

5
1
181
1


-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
emm，总而言之，就是一道高精度，初始化条件a₁为1，a₂为1，然后后面的第n个数就是a

_[n-1]

+a_[n-2]。但是对于1000取模需要注意，因为结果得出来一般是字符串与数组，一开始我就在使用高精度除，（高精度除转载末位大佬的代码，个人写的不是特别好）：

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<string>
using namespace std;

int x,n;
inline void clear(string& a){
    while(a.length()>0&&a[0]=='0')a.erase(0, 1);
    if(a=="")a="0";
}
bool isBigger(string a, string b){
    clear(a);
    clear(b);
    if(a.length() > b.length())
        return true;
    if(a.length()==b.length() && a>=b)
        return true;
    return false; 
}
string Add(string a,string b){
    while(a.length()<b.length())a='0'+a;
    while(a.length()>b.length())b='0'+b; 
    a ='0'+a;b='0'+b;
    for(int i=a.length()-1;i>=0;i--){
        a[i]=a[i]+b[i]-'0';
        if(a[i]>'9'){
            a[i]=a[i]-10;
            a[i-1]+=1;
        }
    } 
    clear(a);
    return a;  
}
string fors(string a,string b){
    string c="";
    for(int i=3;i<=x;i++){
        c=Add(a,b);
        a=b;b=c;
    }
    clear(c);
    while(c.length()>3)c.erase(0, 1);
    return c;
}
int readln(){
    string a="1",b="1";
    cin>>x;
        if(x==0)return 0;
        if(x==1){
            printf("1\n");return 0;
         }else
        if(x==2){
            printf("1\n");return 0;
        }else cout<<fors(a,b)<<endl;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)readln();
}

毋庸置疑，0分

具体原因同下:

测试点1: 运行超时 508KB 997MS
测试点2: 运行超时 508KB 998MS
测试点3: 运行超时 512KB 998MS
测试点4: 运行超时 504KB 998MS
测试点5: 运行超时 508KB 998MS
测试点6: 运行超时 504KB 998MS
测试点7: 运行超时 432KB 1002MS
测试点8: 运行超时 428KB 1002MS
测试点9: 运行超时 496KB 998MS
测试点10: 运行超时 504KB 998MS