AcWing 821. 跳台阶

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 821. 跳台阶原题链接困难

作者：

蓝鲸 , 2020-04-05 11:20:04 , 所有人可见 , 阅读 8904

148

77

终于找到一个没有大佬的题，我来水篇题解~

题目描述

一个楼梯共有 $n$ 级台阶，每次可以走一级或者两级，问从第0级台阶走到第n级台阶一共有多少种方案。

输入格式
共一行，包含一个整数 $n$。

输出格式
共一行，包含一个整数，表示方案数。

数据范围
$1≤n≤15$

样例

输入样例：
5
输出样例：
8

解题思路

先自己手动列举一下，

台阶/级	步数/步
1	1
2	2
3	3
4	5
5	8
6	13

根据以上列举，不难发现，这TM就是一斐波那契数列！

算法1

递归

说人话就是到这一级的步数等于到上一级的方案数和上上级的方案数，
而第一级台阶方案数为1，第二级台阶方案数为2，后面的步骤就是有手就行了。

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n;

int dg(int dep)
{
    if (dep == 1)  return 1;
    if (dep == 2)  return 2; //终止条件
    return dg(dep - 1) + dg(dep - 2);
}

int main()
{
    scanf("%d", &n);
    printf("%d\n", dg(n)); //用递归
    return 0;
}

算法2

for循环

C++代码

#include <bits/stdc++.h>
using namespace std;

int a[20], n;

int main()
{
    a[1] = 1;
    a[2] = 2;
    for (int i = 3; i <= 15; i++) //不要管他丫的，一共就15个，肝就对了
        a[i] = a[i - 1] + a[i - 2];
    scanf("%d", &n);
    printf("%d\n", a[n]);
    return 0;
}

点个赞再走呗【可爱】

39 评论

图灵酱 2023-06-14 16:44

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==1)cout<<"1";
    if(n==2)cout<<"2";
    if(n==3)cout<<"3";
    if(n==4)cout<<"5";
    if(n==5)cout<<"8";
    if(n==6)cout<<"13";
    if(n==7)cout<<"21";
    if(n==8)cout<<"34";
    if(n==9)cout<<"55";
    if(n==10)cout<<"89";
    if(n==11)cout<<"144";
    if(n==12)cout<<"233";
    if(n==13)cout<<"377";
    if(n==14)cout<<"600";
    if(n==15)cout<<"987";
    return 0;
}

图灵酱 2023-06-14 16:44

菲波那切数列

银鹰 2023-07-19 10:07

好家伙，够粗暴（doge）

all4u 2023-12-21 18:38

哈哈哈哈哈

R_75 10个月前

逆天

doilion 10个月前

整笑了哈哈哈

时间的灰烬 10个月前

哈哈哈就喜欢你这样的哈哈哈

枫_99 9个月前

哈哈哈哈

Walkway 9个月前

14是610，我说我写的怎么对不上

tongzan015 4个月前回复了图灵酱的评论

暴力打表

xyj23 2022-07-06 19:43

这不是小学奥数题嘛

zyfzyf 2022-08-03 20:47

# 大佬牛逼

Crazyboy 2023-02-04 12:43

排列组合法

#include<iostream>
using namespace std;
int Combation(int m,int n){
    int a=1,b=1;
    for(int i=0;i<n;i++){
        a*=m-i;
        b*=i+1;
    }
    return a/b;
}
int main(){
    int x;
    cin>>x;
    int y=x/2+1,sum=0;
    for(int i=0;i<y;i++) sum+=Combation(x-i,i);
    cout<<sum;
    return 0;
}

Crazyboy 2023-02-04 12:49

这个问题让我想起了当年看电影《少年班》时，孙红雷找到神人王大法时问的问题：二十层的台阶每次走一步或两步共多少步。王大法当然是脱口而出，而我后来算了半天。。。。

Cherish_6 12个月前回复了 Crazyboy 的评论

不明觉厉

Enchanter 2022-04-12 16:35

有和我一样用排列组合做的么....

drgeek 2022-05-10 16:19

我也是这么想的，但是不知道怎么做

Enchanter 2022-05-10 16:42 回复了 drgeek 的评论

朋友我用公式做出来了，我发给你

面向AI编程 2022-06-08 20:08

大佬，也给我发一份呗

lucy让我夜不能寐 2022-10-13 23:03

我也是，用两个函数来实现排列组合的C几几

Enchanter 2022-10-14 13:11 回复了 lucy让我夜不能寐的评论

头像不是lucy，差评

秋水不想起名 2022-11-14 16:27

#include<iostream>

using namespace std;

int i,step_1,k=i+step_1;

int foo(int k,int i, int step_1)
{
    if(k==1) return 1;

    return k*foo(k-1);

    if(i==1) return 1;

    return i*foo(i-1);

    if(step_1==1) return 1;

    return (step_1*foo(step_1-1);
}

int main()
{
    int n;

    cin>>n;

    int  k=n%2,  s=0;

    for(;i<k;i++)
    {

        step_1=(n-2*i)/1;

        s+= foo(k) / (foo(i)*foo(step_1));

    }
    cout<<s;
    return 0;

}

大佬帮我看看这个代码怎么改进呗，我也是用排列组合的，但不知道怎么用递归表示多个阶乘

Enchanter 2022-12-03 19:15 回复了秋水不想起名的评论

刚看到，我估计你已经解决了hh

秋水不想起名 2022-12-03 21:14 回复了 Enchanter 的评论

哈哈，确实，现在在学算法了

zshzsh 9个月前

华罗庚讲过这道题awa，困难的问题简单化，先从一个台阶开始

bensonzhan 10个月前

新思路

#include <iostream>

using namespace std;
int ans = 0;

void solution(int step, int n) {
    if (step == n) ans++;
    if (step > n) return;

    solution(step + 1, n);
    solution(step + 2, n);

}

int main() {
    int n;
    cin >> n;
    solution(0, n);
    cout << ans << endl;
    return 0;
}

ManoCode 5个月前

牛

十六16 2023-03-25 00:21

xhs 2021-09-18 18:45

太强了，萌新膜拜

烤肠哥+order丸子 2021-05-23 13:39

太棒了

蓝鲸 2021-06-01 13:01

蟹蟹支持

北京欢迎您 2021-03-29 20:39

hhhhhh

灿若小天狼星 2020-12-08 12:55

666666

adcage-始祖 2020-12-08 12:46

wow好帅哦

长街与风 2个月前

牛啊

NULL_549 2023-09-14 18:21

同样的思路不过你的快我的比你多判断
佩服
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
int jump(int n){
if(n==-1)
return 0;
if(n==0)
return 1;
return jump(n-1)+jump(n-2);
}

int main(){
int n;
cin>>n;
cout<<jump(n);
return 0;
}