PTA 1-2 求斐波那契数的尾数

1-2 求斐波那契数的尾数 (50分)

大家都很熟悉斐波那契数列吧？ 也许不会求出斐波那契数列的任意项，但这道题只需要你输出斐波那契数列第 n 项的最后一位数就可以了！

输入格式:
一个不超过100,000的正整数。

输出格式:
在一行中输出第 n 项斐波那契数的尾数。

输入样例:
7

输出样例:
3

“斐波那契数列当n很大的时候，斐波那契数可能会超出整数范围，最后一个样例会出错。由于只求尾数，所以大家思考如何解决这个问题。”

#include<iostream>
using namespace std;

int fib(int a)
{
    int ans;
    if(a==0) return 0;
    else if(a==1) return 1;
    else if(a==2) return 1;
    else 
    {
        ans=fib(a-1)+fib(a-2);
        while(ans/10>0)
        {
            ans=ans%10;
        }
        return ans;
    } 
}

int main()
{
    int n;
    cin>>n;
    
    cout<<fib(n);
    
    return 0;
}

解决了超出整数范围的问题，可是递归好像超时了。

换成了数组+循环

#include<iostream>
using namespace std;

int fib(int a)
{
    int nums[1000000];
    int ans,i=3;
    nums[0]=0;
    nums[1]=1;
    nums[2]=1;
    
    if(a==1) return 1;
    if(a==2) return 1;
    
    while(i<=a)
    {
        nums[i]=nums[i-1]+nums[i-2];
        ans=nums[i];
        while(ans/10>0)
        {
            ans=ans%10;
        }
        nums[i]=ans;
        i++;
    }
    return ans;
     
}

int main()
{
    int n;
    cin>>n;
    
    cout<<fib(n);
    
    return 0;
}

可以直接把尾数提取出来存 加的时候有升位也不会影响个位数的