洛谷P1255 数楼梯c++
·
数楼梯
题目描述
楼梯有 NNN 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
样例 #1
样例输入 #1
4
样例输出 #1
5
提示
- 对于 60%60\%60% 的数据，N≤50N \leq 50N≤50；
- 对于 100%100\%100% 的数据，1≤N≤50001 \le N \leq 50001≤N≤5000。
递推问题：怎么走到第n阶台阶？f(n)=f(n-1)+f(n-2)从第n-1阶走到第n阶有一种方式，从第n-2阶走到第n阶有两种方式。f(1)=1 走一层一种方式，f(2)=2,走两层两种方式。
#include<bits/stdc++.h>
using namespace std;
//高精度，用数组存大数
int n,a[5005]={1},b[5005]={1},c[5005]={1},len=1;
void f()
{
int jw=0;
for(int i=0;i<len;i++)
{
c[i]=a[i]+b[i]+jw;
jw=c[i]/10;
c[i]=c[i]%10;
}
if(jw!=0)
{
c[len]=jw;
len++;
}
for(int i=0;i<len;i++)
{
a[i]=b[i];
b[i]=c[i];
}
}
int main()
{
cin>>n;
for(int i=2;i<=n;i++)
{
f();
}
for(int i=len-1;i>=0;i--)
{
cout<<c[i];
}
return 0;
}
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
0
0- 0
已为社区贡献3条内容
所有评论(0)