1.题目
Description
楼梯有 NN 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
Input
一个数字，楼梯数。
Output
输出走的方式总数。
Sample 1
Inputcopy Outputcopy Hint
- 对于 60%60% 的数据，N≤50N≤50；
- 对于 100%100% 的数据，1≤N≤50001≤N≤5000。
2.思路：
分析易得，是斐波那契数列的高精度运算。
我们用递推来写
递推核心：
for(int i =2;i<=n;i++)
{c=a+b;a=b;b=c;//次序不能改
}
后使用高精度加法：
void add() {int carry = 0;//处理cfor (int i = 0; i < lc; i++) {c[i] = a[i] + b[i] + carry;carry = c[i] / 10;c[i] = c[i] % 10;}if (carry > 0) {c[lc] = carry;lc++;}//处理a,bfor (int i = 0; i < lc; i++) {a[i] = b[i];b[i] = c[i];}
}3.源码：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>#define N 5005
int a[N], b[N], c[N], lc = 1;void add() {int carry = 0;//处理cfor (int i = 0; i < lc; i++) {c[i] = a[i] + b[i] + carry;carry = c[i] / 10;c[i] = c[i] % 10;}if (carry > 0) {c[lc] = carry;lc++;}//处理a,bfor (int i = 0; i < lc; i++) {a[i] = b[i];b[i] = c[i];}
}int main() {int n;scanf("%d", &n);a[0] = 1;b[0] = 1;if (n == 1 || n == 0)printf("%d", 1);else {for (int i = 2; i <= n; i++) {add();}for (int i = lc - 1; i >= 0; i--)printf("%d", c[i]);}return 0;
}
