少儿Python每日一题(23):楼梯问题

原题解答

本次的题目如下所示:

楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,走完n阶台阶共有多少种不同的走法?

输入格式:

输入楼梯的阶梯数n

输出格式:

输出不同走法的个数

输入样例:

10

输出样例:

89

这是一道非常经典的题目,我们可以先寻找一下上楼梯的规律。

题目告诉了我们,一次可以上1阶,也可以上2阶。如果楼梯只有1阶,那很明显只有1种方法;如果楼梯有2阶,我们可以先跨1阶、再跨1阶,也可以直接跨2阶,有2种方法。

当有3个台阶的时候,我们要么先上到第1阶,然后再上2阶;要么先上2阶(上2阶有2种方法),再上1阶。因此一共有3种方法。

当有4个台阶的时候,我们要么先上到第2阶,然后再上2阶;要么先上3阶,再上1阶。

……

通过以上的规律,我们可以发现以下规律:

f(x)=\begin{cases} 1 & \text{ if } x= 1\\ 2 & \text{ if } x= 2\\ f(x-1) +f(x-2) & \text{ if } x\geqslant 3 \end{cases}

这样,我们就可以看出,如果我们写成函数的递归,这道题就很容易做出来了。

def stair(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return stair(n-1) + stair(n-2)

n = int(input())
print(stair(n))

当然,我们知道递归的代码效率比较低,如果想要提高代码的效率,我们可以使用递推的方式优化代码:

n = int(input())
a, b = 1, 2 # a, b分别代表n-2和n-1级的方法数,初始值为1阶和2阶的方法数
for i in range(1, n + 1):
    if i == 1:
        c = a
    elif i == 2:
        c = b
    else:
        c = a + b
        a, b = b, c
print(c)

本题拓展

本题考查的是递推算法和递归调用,题目难度★★★★★

本题的难度在于找到规律,如果找到规律了,程序本身并不难。楼梯问题的拓展有很多,如小马过河、密室逃脱等等,都是在楼梯问题的基础上进行深化的,它的基本思路一直保持不变,依然是先找规律,然后列出递推公式。

这里我们以密室逃脱为例子看看题目如何在原来的基础上进行改动(题目出处:蓝桥杯):

提示信息:

有一个密室逃脱游戏,有100间密室连在一排,密室编号是从1开始连续排列一直排到100间密室,如下图:

游戏规则:

  1. 玩家初始位置在1号密室
  2. 每次玩家可以进入右边的一个密室,也可以跳过一个密室进入下个密室(如:当玩家当前在3号密室,他可以进入4号密室也可以进入5号密室)
  3. 有毒气的密室不能进入要避开。

编程实现:

给定三个正整数X,Y,M(X<Y<M≤100),表示三个密室编号。X号密室和Y号密室有毒气泄漏,不能进入,玩家需要进入到M号密室,按照游戏规则进入M号密室有多少种路线方案。

例如:X=2,Y=4,M=7,进入M号密室有2种路线方案,分别是1->3->5->6->7和1->3->5->7路线。

输入描述:输入三个正整数X,Y,M(X<Y<M),X和Y表示有毒气密室编号,M表示需要进入到密室编号,且三个正整数之间以英文逗号隔开

输出描述:输出进入M号密室有多少种路线方案

样例输入:2,4,7

样例输出:2

本道题如果没有两个毒气泄露的密室,那就跟楼梯问题完全相同了。同样是一次能够前进1个或2个,我们只是增加了一个条件,有毒气泄漏的两个密室不能进入。

那很明显,毒气泄漏的密室不能进入就意味着进入毒气泄漏的密室的方法为0种。因此,我们只需要在原来程序的基础上加入条件判断就可以完成这道题了。 即n == x or n == y时,返回值为0。具体代码如下:

def g(x, y, m):
    if m == x or m == y:
        return 0
    else:
        if x == 1:
            return 1
        elif x == 2:
            return 2
        else:
            return g(x, y, m-1) + g(x, y, m-2)

x, y, m = map(int, input().split(','))
print(g(x, y, m))

同样,我们可以使用递推的方法书写程序,提高代码的执行效率,避免因为函数的递归调用造成的效率低下。这里留一个思考题给大家,大家可以自己写一个这个题目的非递归的程序。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/1040.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Unity学习日记12(导航走路相关、动作完成度返回参数)

目录 动作的曲线与函数 创建遮罩 导航走路 设置导航网格权重 动作的曲线与函数 执行动作&#xff0c;根据动作完成度返回参数。 函数&#xff0c;在代码内执行同名函数即可调用。在执行关键帧时调用。 创建遮罩 绿色为可效用位置 将其运用到Animator上的遮罩&#xff0c;可…

嵌入式学习笔记——STM32寄存器编程实现外部中断

外部中断前言EXTI的介绍EXTI是什么EXTI的主要特性数量对应中断源的命名EXTI的框图配置流程寄存器介绍编程思路编程效果前言 上一篇中&#xff0c;介绍了关于STM32的中断管理以及具体配置&#xff0c;本文就使用之前的配置流程来实现一下外部中断的功能。 EXTI的介绍 EXTI是什…

SDIO读写SD卡速度有多快?

前两天测试了SPI方式读写SD卡的速度《SPI方式读写SD卡速度测试》&#xff0c;今天来测试一下SDIO方式的读写速度。测试条件&#xff1a;单片机&#xff1a;STM32F407VET6编译环境&#xff1a;MDK 5.30HAL库SD卡&#xff1a;闪迪32GB/64GB TF卡文件系统&#xff1a;FatFS R0.12c…

SpringCloud详解01-SpringCloudAlibaba、Nacos

文章目录前言一、架构演进1、web1.0阶段2、web2.0阶段3、垂直架构4、分布式架构二、SpringCloud基本概念1.特点2.SpringCloud和SpringCloudAlibaba3.SpringCloudAlibaba体系核心组件三、SpringCloudAlibaba1、注册中心Nacos2、Nacos安装和启动总结前言 本篇记录一下SpringClou…

ChatGPT研究分享:机器第一次开始理解人类世界

0、为什么会对ChatGPT感兴趣一开始&#xff0c;我对ChatGPT是没什么关注的&#xff0c;无非就是有更大的数据集&#xff0c;完成了更大规模的计算&#xff0c;所以能够回答更多的问题。但后来了解到几个案例&#xff0c;开始觉得这个事情并不简单。我先分别列举出来&#xff0c…

每日学术速递3.17

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.CV 1.Breaking Common Sense: WHOOPS! A Vision-and-Language Benchmark of Synthetic and Compositional Images 标题&#xff1a;打破常识&#xff1a;哎呀&#xff01;合成和合成图像…

【Redis】搭建哨兵集群

目录 集群结构 准备实例和配置 启动 测试 集群结构 这里我们搭建一个三节点形成的Sentinel集群&#xff0c;来监管之前的Redis主从集群。如图&#xff1a; 三个sentinel实例信息如下&#xff1a; 节点IPPORTs1192.168.150.10127001s2192.168.150.10127002s3192.168.150.…

python并发编程多线程

在传统操作系统中&#xff0c;每个进程有一个地址空间&#xff0c;而且默认就有一个控制线程 线程顾名思义&#xff0c;就是一条流水线工作的过程&#xff0c;一条流水线必须属于一个车间&#xff0c;一个车间的工作过程是一个进程 车间负责把资源整合到一起&#xff0c;是一个…

C语言指针操作(十)动态内存分配与指向它的指针变量

目录 一、什么是内存的动态分配 二、怎样建立内存的动态分配 2.1用malloc函数开辟动态存储区 2.2用calloc函数开辟动态存储区 2.3用realloc函数重新分配动态存储区 2.4用free函数释放动态存储区 三、void指针类型 四、举例说明 一、什么是内存的动态分配 全局变量是分…

redis持久化的几种方式

一、简介 Redis是一种高级key-value数据库。它跟memcached类似&#xff0c;不过数据可以持久化&#xff0c;而且支持的数据类型很丰富。有字符串&#xff0c;链表&#xff0c;集 合和有序集合。支持在服务器端计算集合的并&#xff0c;交和补集(difference)等&#xff0c;还支持…

【蓝桥杯专题】 贪心(C++ | 洛谷 | acwing | 蓝桥)

菜狗现在才开始备战蓝桥杯QAQ 文章目录【蓝桥杯专题】 &#xff08;C | 洛谷 | acwing | 蓝桥&#xff09;1055. 股票买卖 IIAcWing 104. 货仓选址传递糖果AcWing 112. 雷达设备付账问题乘积最大AcWing 1247. 后缀表达式P【蓝桥杯专题】 &#xff08;C | 洛谷 | acwing | 蓝桥&…

Flink 应用案例——求网页访问量Top N 实时计算(附可执行代码)

在学习了Flink之后&#xff0c;笔者通过以下案例对Flink API 进行简单复习 目录 案例要求 前置准备 编写主程序&#xff08;点此跳转至代码&#xff09; 运行截图 案例要求 以下数据 为某网站的访问日志 现要求通过以下数据 统计出最近10s内最热门的N个页面&#xff08;即…

【3.17】MySQL索引整理、回溯(分割、子集问题)

3.1 索引常见面试题 索引的分类 什么是索引&#xff1f; 索引是一种数据结构&#xff0c;可以帮助MySQL快速定位到表中的数据。使用索引&#xff0c;可以大大提高查询的性能。 按「数据结构」分类&#xff1a;Btree索引、Hash索引、Full-text索引。 InnoDB 存储引擎创建的聚簇…

漫画:什么是快速排序算法?

这篇文章&#xff0c;以对话的方式&#xff0c;详细着讲解了快速排序以及排序排序的一些优化。 一禅&#xff1a;归并排序是一种基于分治思想的排序&#xff0c;处理的时候可以采取递归的方式来处理子问题。我弄个例子吧&#xff0c;好理解点。例如对于这个数组arr[] { 4&…

优思学院|六西格玛DMAIC,傻傻搞不清?

DMAIC还是搞不清&#xff1f; DMAIC是一个用于过程改进和六西格玛的问题解决方法论。它是以下五个步骤的缩写&#xff1a; 定义&#xff08;Define&#xff09;&#xff1a;明确问题&#xff0c;设定项目的目标和目的。绘制流程图&#xff0c;并收集数据&#xff0c;以建立未来…

基于bearpi的智能小车--Qt上位机设计

基于bearpi的智能小车--Qt上位机设计 前言一、界面原型1.主界面2.网络配置子窗口模块二、设计步骤1.界面原型设计2.控件添加信号槽3.源码解析3.1.网络链接核心代码3.2.网络设置子界面3.3.小车控制核心代码总结前言 最近入手了两块小熊派开发板,借智能小车案例,进行鸿蒙设备学…

01背包问题c++

问题 问题介绍 有 N 种物品和一个容量是 V 的背包&#xff0c;每种物品都有无限件可用。 第 i 种物品的体积是 vi&#xff0c;价值是 wi。 求解将哪些物品装入背包&#xff0c;可使这些物品的总体积不超过背包容量&#xff0c;且总价值最大。 输出最大价值。 输入格式 第…

基于Transformer的交通预测模型部分汇总【附源代码】

交通预测一直是一个重要的问题&#xff0c;它涉及到交通运输系统的可靠性和效率。随着人工智能的发展&#xff0c;越来越多的研究者开始使用深度学习模型来解决这个问题。其中&#xff0c;基于Transformer的交通预测模型在近年来备受关注&#xff0c;因为它们具有优秀的建模能力…

设计模式之桥接模式(C++)

作者&#xff1a;翟天保Steven 版权声明&#xff1a;著作权归作者所有&#xff0c;商业转载请联系作者获得授权&#xff0c;非商业转载请注明出处 一、桥接模式是什么&#xff1f; 桥接模式是一种结构型的软件设计模式&#xff0c;将抽象部分与实现部分分离&#xff0c;使他们可…

像ChatGPT玩转Excel数据

1.引言 最近ChatGPT的出现&#xff0c;把人工智能又带起了一波浪潮。机器人能否替代人类又成了最近热门的话题。 今天我们推荐的一个玩法和ChatGPT有点不一样。我们的课题是“让用户可以使用自然语言从Excel查询到自己想要的数据”。 要让自然语言可以从Excel中查数据&#…
最新文章