首页 > 代码库 > 数楼梯
数楼梯
题目描述
楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入输出格式
输入格式：
一个数字，楼梯数。
输出格式：
走的方式几种。
输入输出样例
输入样例#1：
4
输出样例#1：
5
说明
用递归会太慢，需用递推
（60% N<=50 ,100% N<=5000)
思路：高精+斐波那契数列
代码实现：
1 #include<cstdio> 2 int n,al,bl,cl; 3 int a[3000],b[3000]={1},c[3000]; 4 int main(){ 5 scanf("%d",&n); 6 if(n==0){printf("0\n");return 0;} 7 for(int k=1;k<=n;k++){ 8 cl=bl; 9 for(int i=0;i<=cl;i++){10 c[i]+=a[i]+b[i];11 if(c[i]>9){12 c[i+1]+=1;13 c[i]%=10;14 if(i==cl) cl++;15 }16 }17 al=bl;18 for(int i=0;i<=al;i++) a[i]=b[i];19 bl=cl;20 for(int i=0;i<=bl;i++) b[i]=c[i],c[i]=0;21 }22 for(int i=bl;i>=0;i--)23 printf("%d",b[i]);24 printf("\n");25 return 0;26 }
题目来源：洛谷
数楼梯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。