PDSOJ 1048 Fibonacci Numbers(大数)

淡淡的烟草味﹌ 2022-06-17 00:49 148阅读 0赞

## [Fibonacci Numbers][] ##

时间限制: 1 Sec   内存限制: 128 MB  
提交: 13   解决: 2  
\[ [提交][Link 1]\]\[ [状态][Link 2]\]\[ [讨论版][Link 3]\]

## 题目描述 ##

A Fibonacci sequence is calculated by adding the previous two members of the sequence, with  
the first two members being both 1.  
f (1) = 1, f (2) = 1, f (n > 2) = f (n − 1) + f (n − 2)  
Your task is to take a number as input, and print that fibonacci number.

## 输入 ##

100

## 输出 ##

354224848179261915075

## 样例输入 ##

100

## 样例输出 ##

354224848179261915075

## 提示 ##

No generated fibonacci number in excess of 1000 digits will be in the test data, i.e. f (20) = 6765

和大数加法类似，还要注意数据的变换s1,s2,sum之间的变换，sum=s1+s2.然后字符处理

#include<iostream>
    #include<cstring>
    using namespace std;
    char sum[1200];
    int s=0,m=0,n;
    int main()
    {
        cin>>n;
        string s1,s2;
        int a[10000],b[10000];
        int he,i;
        s1="1";
        s2="1";
        for(m=2;m<n;m++)
        {
            memset(a,0,sizeof(a));
            memset(b,0,sizeof(b));
            a[0]=s1.length();
            for(i=1;i<=a[0];i++)
            {
                a[i]=s1[a[0]-i]-'0';
            }
              b[0]=s2.length();
            for(i=1;i<=b[0];i++)
            {
                b[i]=s2[b[0]-i]-'0';
            }
            he=(a[0]>b[0]?a[0]:b[0]);
            for(i=1;i<=he;i++)
            {
                a[i]=a[i]+b[i];
                a[i+1]=a[i+1]+a[i]/10;
                a[i]=a[i]%10;
            }
            he++;
            while((a[he]==0)&&(he>1))
            he--;
            for(i=he,s=0;i>=1;i--,s++)
            {
                sum[s]=a[i]+'0';
            }
            s1=s2;
            s2=sum;
       }
            cout<<s2<<endl;
    
    }

[Fibonacci Numbers]: http://211.69.26.100/problem.php?id=1048
[Link 1]: http://211.69.26.100/submitpage.php?id=1048
[Link 2]: http://211.69.26.100/problemstatus.php?id=1048
[Link 3]: http://211.69.26.100/bbs.php?pid=1048