P1255 数楼梯题解

本文主要是介绍P1255 数楼梯题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

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

输入输出格式

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

输入输出样例

输入样例

4

输出样例

5

解析

这个题目如果想要走到第1000个台阶，必须要先走到第998个台阶或者第999个台阶，然后一步跨到第1000级，所以到第1000个台阶的走法数量就是从第998级的走法数量与从头到第999级的走法数量之和，这么想就简单多了。不过还得先知道走到第998级和第999级的走法数量是多少。

假设从头走到第i个台阶的走法数量是，根据上面的分析可以得到。同理，,以此类推，可以归纳得到，且知道，其他的就可以通过递推得到

像这样知道递推式，也知道初始条件，从初始条件开始往上顺推直到求的目标解的思想就是递推。

这个题目由于斐波那契数子增长得很快，所以需要使用高精度计算。可以使用结构体封装大整数结构体。

#include<iostream>
#include<cstring>
#define maxn 6000
using namespace std;
struct Bigint{int len,a[maxn];Bigint(int x=0){memset(a,0,sizeof(a));for(len=1;x;len++){a[len]=x%10;x/=10;}len--;}int &operator[](int i){return a[i];}void flatten(int L){len=L;for(int i=1;i<=len;i++){a[i+1]+=a[i]/10;a[i]%=10;}for(;!a[len];){len--;}}void print(){for(int i=len;i>=1;i--){cout<<a[i];}}
};
Bigint operator+(Bigint a,Bigint b){Bigint c;int len=max(a.len,b.len);for(int i=1;i<=len;i++){c[i]+=a[i]+b[i];}c.flatten(len+1);return c;
}
int main(){int n;cin>>n;Bigint f[5050];f[1]=Bigint(1);f[2]=Bigint(2);for(int i=3;i<=n;i++){f[i]=f[i-2]+f[i-1];}f[n].print();return 0;
}

也可以使用数组直接模拟进位的方式实现。

#include<iostream>
using namespace std;
int n,len=1,f[5001][5001];
void hp(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]>9){f[k][i+1]+=f[k][i]/10;f[k][i]%=10;if(f[k][len+1]){len++;}}}
}
int main(){cin>>n;f[1][1]=1;f[2][1]=2;for(int i=3;i<=n;i++){hp(i);}for(int i=len;i>=1;i--){cout<<f[n][i];}return 0;
}

这篇关于P1255 数楼梯题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---