题解 P1255 【数楼梯】

babingbaboom · 2018-01-30 10:11:10 · 题解

我们可以用高精度加法来计算斐波那契数列的每一个数，加法代码如下

#include<iostream>
#include<cstring>
using namespace std;
char sum[1200];
int s=0;
int main()
{
string s1,s2;
int a[1200],b[1200],he;
int i;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>s1>>s2;
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]+=b[i];
a[i+1]+=a[i]/10;
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';
}
cout<<sum;
}

然后只需要做一点修修补补就可以了 附上完整代码：

#include <bits/stdc++.h>
using namespace std;
char sum[1200];//用它来存斐波那契大数字的每一位数 
int s=0, n, a[1200], b[1200], fib;
string s1,s2;
int main()
{
    scanf("%d", &n);
    if (n == 0) { printf("0\n"); return 0; }//不加这句话就会WA第六个点 
    n++;
    s1 = "1";
    s2 = "1";
    //高精度加法 
    for(int m = 2; m < n; m++)
    {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        a[0] = s1.length();
        for (int i = 1; i <= a[0]; i++) a[i] = s1[a[0] - i] - '0';
        b[0] = s2.length();
        for (int i = 1; i <= b[0]; i++) b[i] = s2[b[0] - i] - '0';
        fib = (a[0] > b[0] ? a[0] : b[0]);
        //进位 
        for (int i = 1; i <= fib; i++)
        {
            a[i] += b[i];
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        fib++;
        while ((a[fib] == 0) && (fib > 1)) fib--;
        for (int i = fib, s = 0; i >= 1; i--, s++) sum[s] = a[i] + '0';
        s1 = s2;
        s2 = sum;//存最终结果 
    }
    cout << s2 << endl;
    return 0;
}