【洛谷习题】P1255 数楼梯

题目描述

楼梯有N阶,上楼可以一步上一阶,也可以一步上二阶。

编一个程序,计算共有多少种不同的走法。

输入格式

一个数字,楼梯数。

输出格式

走的方式几种。

输入样例

4

输出样例

5

说明/提示

60% N<=50
100% N<=5000)

思路与解法

根据题意会发现,到每阶楼梯的走法数量和斐波那契数列很相像,都是f[i] = f[i-2]+f[i-1],但基准情况有点不同,先总结出该题公式
公式
于是完全按公式写出一个解法

#include<iostream>

using namespace std;

unsigned long long f[5005];            //存储走到第i阶楼梯有多少种走法的余数 
int main(){
    int n;
    cin >> n;
    f[1] = 1,f[2] = 2;
    for(int i = 3;i <= n;i++)
        f[i] = f[i-2] + f[i-1];
    cout << f[n] << endl;
    
    return 0;
}

但这个解法显然是会溢出的,即使是unsigned long long也不可能装下f(5000),这时可以考虑用数组来存储单个值,自己模拟一个高精度的加法。代码如下

#include<iostream>
#include<cstring>

using namespace std;

char f[5005][2000];            //存储走到第i阶楼梯有多少种走法的余数 
inline void bigAdd(char *ret,const char *f1,const char *f2){
    int flag = 0;        //进位 
    int i;
    for(i = 0;f1[i]!='\0'||f2[i]!='\0'||flag;++i){
        int a = f1[i]?f1[i]-'0':0;
        int b = f2[i]?f2[i]-'0':0;
        if(a+b+flag >= 10){        //如果要进位 
            ret[i] = a+b+flag-10+'0';
            flag = 1;
        }
        else{
            ret[i] = a+b+flag+'0';
            flag = 0;
        }
    }
}
int main(){
    int n;
    cin >> n;
    strcpy(f[0],"0");
    strcpy(f[1],"1");
    strcpy(f[2],"2");
    for(int i = 3;i <= n;i++)
        bigAdd(f[i],f[i-2],f[i-1]); 
    for(int i = strlen(f[n])-1;i >= 0;--i)
        cout << f[n][i];
    cout << endl;
    
    return 0;
}

上面用的是字符数组存储数值,也可以直接使用整型数组来存储,更加方便计算,同时在计算方面,可以直接遍历两数每位,存储相加的值先不进位,然后再第二遍遍历时来处理进位,最后依然是倒序输出。附上该题第一位题解的代码,该代码原地址

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int n,len=1,f[5003][5003];//f[k][i]--第k阶台阶所对应的走法数 
void hp(int k)//高精度加法,k来存阶数 
{    
    int i;
    for(i=1;i<=len;i++)
     f[k][i]=f[k-1][i]+f[k-2][i];//套用公式 
    for(i=1;i<=len;i++)             //进位 
     if(f[k][i]>=10)
     {
         f[k][i+1]+=f[k][i]/10;
         f[k][i]=f[k][i]%10;
         if(f[k][len+1])len++;
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    f[1][1]=1; f[2][1]=2;         //初始化 
    for(i=3;i<=n;i++)              //从3开始避免越界 
     hp(i);                         
    for(i=len;i>=1;i--)             //逆序输出 
     printf("%d",f[n][i]);
    return 0;
}
本文作者:六月丶

本文链接:https://www.hctra.cn/index.php/archives/654/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2020 年 07 月 06 日 05 : 44 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论