题解 P1255 【数楼梯】

Mr_WA的大号 · 2019-12-17 13:37:22 · 题解

程序是我家，AC靠大家，小学生又来发题解了！

题号:P1255【数楼梯】

难度：★★★

算法：高精，菲波那切数列，递推

开课了！

数楼梯这一道题首先分析数据，n<=5000，说明我们要用高精来计算。

高精，用一个数组或者字符串来记录每一位是数字几，用另一个变量来记录有几位，输出时一般要倒着输出。

我们还有一个问题：怎么计算呢？

我们可以通过推理来找出。

第3位可以由第1阶走两步或第2阶走一步得出。

第4位可以由第2阶走两步或第3阶走一步得出。

第5位可以由第3阶走两步或第4阶走一步得出。

......

最后可以得出：

a[i]=a[i-1]+a[i-2];

其中a表示走法数，i表示是第几位。

切记：加法要用高精来做，并倒着输出数组。

代码如下：

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
using namespace std;
int n,f[5010][5010],len;
void jiafa(int k)//高精加法
{
    for(int i=1; i<=len; i++)//两数相加
        f[k][i]=f[k-1][i]+f[k-2][i];
    for(int i=1; i<=len; i++)//进位
        if(f[k][i]>=10)
        {
            f[k][i+1]+=f[k][i]/10;
            f[k][i]%=10;
            if(f[k][len+1]>0)len++;
        }
}
int main()
{
    cin>>n;
    len=1;
    f[1][1]=1;//预处理
    f[2][1]=2;//预处理
    for(int i=3; i<=n; i++)//开始计算
        jiafa(i);
    for(int i=len; i>=1; i--)//输出
        cout<<f[n][i];
    return 0;
}

祝愿大家能AC