【简单数学小问题7】楼梯走法问题（编辑ing）

无理想的闲鱼

题目1：有一段楼梯，一共12级台阶，规定每一步只能跨一级或者两级台阶，要登上12级台阶有多少种不同的走法？

【答案】233
答案仅供判断代码最后运行结果是否正确，代码块中不允许出现

                               
登录/注册后可看大图

                               
登录/注册后可看大图

如果你完成了第一道题，可以尝试做做下面的变式
拓展题目2：一共有n级台阶，要登上n级台阶有多少种不同的走法？
【输入示例1】有多少级台阶：12
【输出示例1】233或者233.0

【输入示例2】
【输出示例2】

如果你有更优的解法或者建议，欢迎评论！我会看实际情况给你评分

游客，如果您要查看本帖隐藏内容请回复

[/hide]

人造人

#include <stdio.h>

size_t stair(size_t s, size_t n, size_t init) {
    if(s > n) return init;
    if(s == n) return init + 1;
    return stair(s + 1, n, init) + stair(s + 2, n, init);
}

int main(void) {
    printf("%zu\n", stair(0, 12, 0));
    return 0;
}

tommyyu

1. 递归（有递归次数限制）

nums = {1:1, 2:2}

import functools
@functools.cache
def dp(n):
    try:
        return nums[n]
    except:
        return dp(n-1) + dp(n-2)

print(dp(int(input())))

2.递归（无递归次数限制）

nums = {1:1, 2:2}

import functools
@functools.cache
def dp(n):
    try:
        return nums[n]
    except:
        return dp(n-1) + dp(n-2)

count = 500
n = int(input())
while True:
    if n < count:
        print(dp(n))
        break
    nums_ = dict()
    nums_[count], nums_[count-1] = dp(count), dp(count-1)
    nums = nums_
    count += 500

3.循环

n = int(input())
if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    nums = [1, 2]
    i = 2
    while i < n:
        nums.append(nums[i-2] + nums[i-1])
        i += 1
    print(nums[-1])

人造人

>>> def stair(s, n, init):
...     if s > n: return init
...     if s == n: return init + 1
...     return stair(s + 1, n, init) + stair(s + 2, n, init)
...
>>> stair(0, 12, 0)
233
>>>

嘉岳呀

感觉有点类似斐波那契

C++递推：

#include <iostream>
using namespace std;
int a[10001];
int main()
{
    a[1]=1;
    a[2]=2;

    for(int i=3;i<=12;i++)
    {
        a[i]=a[i-1]+a[i-2];
    }

    cout<<a[12];

    return 0;
}

嘉岳呀

递归：

#include <bits/stdc++.h>
using namespace std;
int a[1001];
int fib(int n)
{
    if(a[n])
    {
        return a[n];
    }
    else
    {
        a[n]=fib(n-1)+fib(n-2);
        return a[n];
    }
}
int main()
{
    a[1]=1;
    a[2]=1;

    cout<<fib(13);

    return 0;
}

fib(12)的时候是144，可能是有个bug

嘉岳呀

题目 2：

#include <bits/stdc++.h>
using namespace std;
int a[1001];
int fib(int n)
{
    if(a[n]){
        return a[n];
    }
    else{
        a[n]=fib(n-1)+fib(n-2);
        return a[n];
    }
}
int main()
{
    int n;
    cout<<"有多少级台阶："
    cin>>n;
    a[1]=1;
    a[2]=1;

    cout<<fib(n+1);

    return 0;
}

无理想的闲鱼

嘉岳呀 发表于 2022-11-11 13:25
感觉有点类似斐波那契

C++递推：

是的，类似 斐波那契数列

zhangjinxuan

你似乎没有给数据范围
C++

#include <cstdio>
using namespace std;

long long res[100001] = {0, 1, 2}, n;
long long solve(int num) {
        if (res[num]) return res[num];
        res[num - 1] = solve(num - 1);
        res[num - 2] = solve(num - 2);
        return res[num - 1] + res[num - 2];
}

int main() {
        scanf("%d", &n);
        printf("%lld", solve(n));
        return 0;
}

Python:

res = {}
res[1] = 1
res[2] = 2
def solve(num):
    if res.get(num): return res[num];
    res[num - 1] = solve(num - 1)
    res[num - 2] = solve(num - 2)
    return res[num - 1] + res[num - 2]
n = int(input())
print(solve(n))

lxping

def findMethod(tj):
    basic_num = {1:1,2:2}
    if tj in basic_num.keys():
        return basic_num[tj]
    else:
        return findMethod(tj-1) + findMethod(tj-2)

findMethod(12)
233

hellometa

打卡学习，顺便领个币