信息学奥赛一本通1190：上台阶
1190：上台阶
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 69016 通过数: 23589
【题目描述】
楼梯有n(0<n<71)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。
【输入】
输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。
【输出】
每一行输出对应一行输入的结果，即为走法的数目。
【输入样例】
1
2
3
4
0
【输出样例】
1
2
4
思路：
这道题，有没有人在数学考试附加题见过啊？我就见过了
首先我们来分析一下
我要走n节台阶，那我有几种可能呢？（假设我要走1~n-1节台阶的可能数都知道了，就是1~n-1节台阶我知道有几种可能）
很显然，因为我们可以上1、2、3阶，所以，上n阶台阶，一共有f（n-1）+f(n-2)+f(n-3)种可能（f(n)表示走n节台阶的可能数）
所以我们发现，这道题跟斐波那契数列一样，只要你会写斐波那契数列就好了
代码：
#include<bits/stdc++.h>
using namespace std;long long f(long long n){//f（n）表示走n节台阶的可能数 long long a[n+10];//定义数组用于计算斐波那契数列 a[1] = 1;//我们知道第一节台阶的可能数 a[2] = 2;//第二阶 a[3] = 4;//第三节 for(int i = 4; i <= n; i++){a[i] = a[i-1] + a[i-2] + a[i-3];}return a[n];//返回
}int main(){long long a;while(cin >> a && a){//解释一下，这里就是一直读入a，如果a==0的时候，就结束循环 cout << f(a) << endl;}return 0;
}