无理想的闲鱼 发表于 2022-11-11 11:13:48

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

本帖最后由 无理想的闲鱼 于 2022-11-11 12:26 编辑

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

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


static/image/hrline/4.gifstatic/image/hrline/4.gif


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

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

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

**** Hidden Message *****

人造人 发表于 2022-11-11 11:59:08

#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 发表于 2022-11-11 12:00:14

1. 递归（有递归次数限制）nums = {1:1, 2:2}

import functools
@functools.cache
def dp(n):
    try:
      return nums
    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
    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_, nums_ = 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 =
    i = 2
    while i < n:
      nums.append(nums + nums)
      i += 1
    print(nums[-1])

人造人 发表于 2022-11-11 12:01:28

>>> 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
>>>

嘉岳呀 发表于 2022-11-11 13:25:05

感觉有点类似斐波那契

C++递推：
#include <iostream>
using namespace std;
int a;
int main()
{
    a=1;
    a=2;

    for(int i=3;i<=12;i++)
    {
      a=a+a;
    }

    cout<<a;

    return 0;
}

嘉岳呀 发表于 2022-11-11 13:28:05

递归：

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

    cout<<fib(13);

    return 0;
}

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

嘉岳呀 发表于 2022-11-11 13:30:39

题目 2：

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

    cout<<fib(n+1);

    return 0;
}

无理想的闲鱼 发表于 2022-11-11 13:33:18

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

C++递推：

是的，类似 斐波那契数列{:10_298:}

zhangjinxuan 发表于 2022-11-11 14:42:11

你似乎没有给数据范围
C++
#include <cstdio>
using namespace std;

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

int main() {
        scanf("%d", &n);
        printf("%lld", solve(n));
        return 0;
}
Python:
res = {}
res = 1
res = 2
def solve(num):
    if res.get(num): return res;
    res = solve(num - 1)
    res = solve(num - 2)
    return res + res
n = int(input())
print(solve(n))

lxping 发表于 2022-11-11 20:24:31

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

findMethod(12)
233

hellometa 发表于 2022-11-13 21:49:43

打卡学习，顺便领个币{:10_256:}
页: [1]
查看完整版本: 【简单数学小问题7】楼梯走法问题（编辑ing）