1180: 零起点学算法87——超级楼梯

谁践踏了优雅 2022-10-24 06:12 174阅读 0赞

## Description ##

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

## Input ##

输入数据首先包含一个整数N，表示测试实例的组数

接下来的N行，每行表示一组测试数据，每行包含一个整数M（1<=M<=40），表示楼梯的级数。

## Output ##

对于每组测试实例，请输出不同走法的数量。

## Sample Input ![5f8f312f51791b8bb0ed0ae07c2ffa43.gif][] ##

3
    1
    2
    3

## Sample Output ##

1
    1
    2

## Source ##

[零起点学算法 递推][Link 1]

## Code ##

#include<iostream>
    #include<stdio.h>
    #include<string.h>
    using namespace std;
    int main()
    {
        int n;
        cin>>n;
        while(n--)
        {
            int m;
            cin>>m;
            int ans[m];
            ans[1]=1;
            ans[2]=1;
            for(int i=3;i<=m;i++)
            {
                ans[i]=ans[i-1]+ans[i-2];
            }
            cout<<ans[m]<<endl;
        }
    }

其实就是一个斐波那契数列。因为每一步的步长是1或2，所以分别对应的两种情况是n-1和n-2

那么就把之前的两种加起来就可以了

[5f8f312f51791b8bb0ed0ae07c2ffa43.gif]: /images/20221024/014b6dfd2f264193b10b14a84a5cab77.png
[Link 1]: https://oj.wustacm.top/problemset.php?search=%E9%9B%B6%E8%B5%B7%E7%82%B9%E5%AD%A6%E7%AE%97%E6%B3%95%20%20%E9%80%92%E6%8E%A8&searchmode=source&soj=0

发表评论取消回复

表情：

评论列表（有 0 条评论，174人围观）

还没有评论，来说两句吧...

相关阅读

相关 1147: 零起点学算法54——Fibonacci

Description Fibonacci数列定义为（1,1,2,3,5,8,.....），即每个元素是前两个元素的和。如果一个Fibonacci数与所有小于它的Fibo

小鱼儿/ 2023年01月11日 08:44/ 0 赞/ 166 阅读

相关 1199: 零起点学算法106——Max Num

Description There are some students in a class, Can you help teacher find the highest

ゞ浴缸里的玫瑰/ 2022年10月26日 14:10/ 0 赞/ 131 阅读

相关 1198: 零起点学算法105——多项式求和

Description 多项式的描述如下： 1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ... 现在请你求出该多项式的前n项的和。 I

谁借莪１个温暖的怀抱￠/ 2022年10月26日 14:09/ 0 赞/ 231 阅读

相关 1190: 零起点学算法97——A == B ?

Description Give you two integer numbers A and B, if A is equal to B, you should prin

电玩女神/ 2022年10月25日 05:52/ 0 赞/ 144 阅读

相关 1185: 零起点学算法92——单词数（*）

Description BobLee 最近忙着考研，话说某一天当他正在看一篇英语阅读时，突然想到想去统计下这篇文章不同单词的个数，由于BobLee很忙，所以想让你帮忙统计

小咪咪/ 2022年10月25日 00:56/ 0 赞/ 213 阅读

相关 1181: 零起点学算法88——偶数求和(*)

Description 有一个长度为n(n<=100)的数列，该数列定义为从2开始的递增有序偶数，现在要求你按照顺序每m个数求出一个平均值，如果最后不足m个，则以实际数量

我不是女神ヾ/ 2022年10月24日 06:12/ 0 赞/ 218 阅读

相关 1180: 零起点学算法87——超级楼梯

Description 有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？ Input 输入数据首先包含一个整数N，表示

谁践踏了优雅/ 2022年10月24日 06:12/ 0 赞/ 175 阅读

相关 1176: 零起点学算法83——核反应堆

Description 某核反应堆有两类事件发生：高能质点碰击核子时，质点被吸收，放出3个高能质点和1个低能质点；低能质点碰击核子时，质点被吸收，放出2个高能

清疚/ 2022年10月24日 05:53/ 0 赞/ 207 阅读

相关 1171: 零起点学算法78——牛牛

Description 牛牛是一种纸牌游戏，总共5张牌，规则如下：如果找不到3张牌的点数之和是10的倍数，则为没牛；如果其中3张牌的点数之和是10的倍数，则为

﹏ヽ暗。殇╰゛Y/ 2022年10月24日 02:23/ 0 赞/ 192 阅读

相关 1166: 零起点学算法73——统计元音

1166: 零起点学算法73——统计元音 Time Limit: 1 Sec Memory Limit: 64 MB 64bit IO Format: %lld Su

短命女/ 2022年01月12日 09:13/ 0 赞/ 218 阅读