首页 > 代码库 > luoguP1255 数楼梯 x
luoguP1255 数楼梯 x
P1255 数楼梯
题目描述
楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入输出格式
输入格式：
一个数字，楼梯数。
输出格式：
走的方式几种。
输入输出样例
输入样例#1：
4
输出样例#1：
5
说明
用递归会太慢，需用递推
（60% N<=50 ,100% N<=5000)
思路:
题目中说明中提及递归太慢,所以用递推做的.但是又因为范围是到5000,范围太大,所以需要用高精来做.
坑点:
斐波那契第0项的值为0,是根据题目的意思来判断的.
代码:
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int M = 100010;int n;string f[M];string J(string aa,string bb){ if(aa.length()<bb.length()) { string tmp=aa; aa=bb; bb=tmp; } int i,j; for(i=aa.length()-1,j=bb.length()-1;i>=0;i--,j--) { aa[i]=char(aa[i] + ( j >= 0 ? bb[j]-‘0‘ : 0)); if(aa[i]-‘0‘>=10) { aa[i]=char((aa[i]-‘0‘)%10+‘0‘); if(i) aa[i-1]++; else aa=‘1‘+aa; } } return aa;}int main(){ int j=3; scanf("%d",&n); f[0]=‘0‘; f[1]=‘1‘; f[2]=‘2‘; while(j<=n) { f[j]=J(f[j-1],f[j-2]); j++; } cout<<f[n]; return 0;}
End.
luoguP1255 数楼梯 x
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。