数楼梯
油菜花数楼梯
题目描述
楼梯有N阶,上楼可以一步上一阶,也可以一步上二阶。
编一个程序,计算共有多少种不同的走法。
输入格式
一个数字,楼梯数。
输出格式
输出走的方式总数。
样例 #1
样例输入 #1
样例输出 #1
提示
- 对于60%的数据,N<50;
- 对于100%的数据,1<N<5000。
分析
直接用简单的递归的话,数据过大栈会溢出
用数组的话也是超时
所以用高精度加法
高精度算法
算法核心:
也就是把个十百千位分别相加
1 2 3
| c[i]=a[i]+b[i]; c[i+1]=c[i]/10; c[i]=c[i]%10;
|
题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; int n,len=1,f[5005][5005]; void hp(int 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; cin>>n; f[1][1]=1; f[2][1]=2; for(i=3;i<=n;i++){ hp(i); } for(i=len;i>=1;i--) { cout<<f[n][i]; } return 0; }
|