1190:上台阶
麦兜 / 2019-07-31 / 算法 / 阅读量 699

【题目描述】

楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶,编程计算共有多少种不同的走法。
【输入】

输入的每一行包括一组测试数据,即为台阶数n。最后一行为0,表示测试结束。
【输出】

每一行输出对应一行输入的结果,即为走法的数目。
【输入样例】

1
2
3
4
0

【输出样例】

1
2
4
7

【来源】

No

题解

首先根据题目给出的数字推理一下
1.png
用草稿写一下5个台阶 只走1、2、3步有多少种可能,很快就会明白了。
这是我算出来的!
2.png
然后有没有发现规律。

i=1 sum=1
i=2 sum=2
i=3 sum=4
i>3 sum=a[i-1]+a[i-2]+a[i-3]
3.png

参考代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    long long a[71] = {0};
    a[0] = 1;
    a[1] = 2;
    a[2] = 4;
    int n;
    for (int i = 3; i < 71; i++)
    {
        a[i] = a[i - 1] + a[i - 2] + a[i - 3];
    }
    cin >> n;
    while (n != 0)
    {
        cout << a[n-1]<<endl;
        cin >> n;
    }
}

发表留言

人生在世,错别字在所难免,无需纠正。