数楼梯
题目描述
楼梯有 $N$ 阶,上楼可以一步上一阶,也可以一步上二阶。
编一个程序,计算共有多少种不同的走法。
输入格式
一个数字,楼梯数。
输出格式
输出走的方式总数。
样例 #1
样例输入 #1
4
样例输出 #1
5
提示
- 对于 $60\%$ 的数据,$N \leq 50$;
- 对于 $100\%$ 的数据,$1 \le N \leq 5000$。
题解:
思路:由于一次可以走一级或者两级台阶,那么就可以想到,第k级台阶的走法应该是第k-1级和第k-2级台阶的走法的和(因为第k级台阶只能从第k-1或第k-2级台阶走上来的),于是就得到递推式:step[k] = step[k - 1] + step[k - 2]
一个数列的每一项等于它的前两项之和,这就是斐波那契数列
于是这个问题就转换成求斐波那契数列数列的第n项是多少。
但是输入数据非常大,那么这就是个高精度+递推求斐波那契数列的问题。
高精度加法技巧:可以用一个二维数组来存储,第一维存储第k个fib数,第二维存储每一位数字(0 - 9)
两个数相加时,就遍历第二维的每一位,相加再进位
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int step[N][N];
int len = 1;//len表示当前斐波那契数列的项的长度是多少,初始长度为1
void hpa(int k)//高精度加法,求斐波那契数列第k项
{
for (int i = 1; i <= len; i++)//模拟竖式加法,从低位到高位依次相加
{
step[k][i] = step[k - 1][i] + step[k - 2][i];
}
for (int i = 1; i <= len; i++)//模拟进位
{
if (step[k][i] >= 10)//某一位数字大于等于10时,就需要进位
{
step[k][i + 1] += step[k][i] / 10;
step[k][i] %= 10;
if (step[k][len + 1] > 0) len++;//若发生了进位,则数字长度加一
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
step[1][1] = 1, step[2][1] = 2;//初始化
for (int i = 3; i <= n; i++)//从第三项开始递推
{
hpa(i);
}
for (int i = len; i >= 1; i--) cout << step[n][i];//倒序输出
return 0;
}