Python两种方法求解登楼梯问题(京东2016笔试题)

问题:假设一段楼梯共15个台阶,小明一步最多能上3个台阶,那么小明上这段楼梯一共有多少种方法?

解析:从第15个台阶上往回看,有3种方法可以上来(从第14个台阶上一步迈1个台阶上来,从第13个台阶上一步迈2个台阶上来,从第12个台阶上一步迈3个台阶上来),同理,第14个、13个、12个台阶都可以这样推算,从而得到公式f(n) = f(n-1) + f(n-2) + f(n-3),其中n=15、14、13、...、5、4。然后就是确定这个递归公式的结束条件了,第一个台阶只有1种上法,第二个台阶有2种上法(一步迈2个台阶上去、一步迈1个台阶分两步上去),第三个台阶有4种上法(一步迈3个台阶上去、一步2个台阶+一步1个台阶、一步1个台阶+一步2个台阶、一步迈1个台阶分三步上去)。

有了公式和结束条件,可以使用递推递归两种方法来解决这个问题,代码如下:

def climbStairs1(n): #递推法 a = 1 b = 2 c = 4 for i in range(n-3): c, b, a = a+b+c, c, b return c

def climbStairs2(n): #递归法 first3 = {1:1, 2:2, 3:4} if n in first3.keys(): return first3[n] else: return climbStairs2(n-1) + \ climbStairs2(n-2) + \ climbStairs2(n-3)

看起来是完美的,不过需要注意的是,上面这个递归算法貌似简洁明了,但效率非常非常低,不仅因为递归时上下文的保存和恢复比较耗时,还因为涉及大量的重复计算。在Python中,可以使用functools标准库提供的缓冲修饰器lru_cache来缓解这个问题。下面的函数和上面的递归函数完全一样,只是在外面加了个缓冲器。

@functools.lru_cache(maxsize=64) def climbStairs3(n): #带缓冲的递归法 first3 = {1:1, 2:2, 3:4} if n in first3.keys(): return first3[n] else: return climbStairs3(n-1) + \ climbStairs3(n-2) + \ climbStairs3(n-3)

下面是测试代码

n = 25 for f in (climbStairs1, climbStairs2, climbStairs3): start = time.time() for i in range(1000): result = f(n) delta = time.time() - start print(f.__name__, result, delta)

下面是测试结果,可以看出,普通的递归函数效率非常低,应慎重使用。

climbStairs1 2555757 0.0 climbStairs2 2555757 458.8922302722931 climbStairs3 2555757 0.0

原文发布于微信公众号 - Python小屋(Python_xiaowu)

原文发表时间:2017-02-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

算法:最短路径之弗洛伊德(Floyd)算法

为了能讲明白弗洛伊德(Floyd)算法的主要思想,我们先来看最简单的案例。图7-7-12的左图是一个简单的3个顶点的连通网图。 ? 我们先定义两个二维数组D[3...

8337
来自专栏尾尾部落

[剑指offer] 变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1082
来自专栏ml

HDUOJ--1874 畅通工程续

畅通工程续 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

34311
来自专栏数据结构与算法

点双连通分量与割点

前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双连通分量 双连通分量一般是指点双连通分量 当然,还有一种叫做边双连通分量 点双连通分量 对于一个...

3758
来自专栏小特工作室

基于iTextSharp的PDF文档操作

  公司是跨境电商,需要和各种物流打交道,需要把东西交给物流,让他们发到世界各地。其中需要物流公司提供一个运单号,来追踪货物到达哪里?!   最近在和DHL物流...

27410
来自专栏技术随笔

LIDC-IDRI肺结节公开数据集Dicom和XML标注详解数据来源解析结果数据分析

8518
来自专栏空间大数据可视化

GIS基础算法之Kruskal算法(2015.10.15)

1235
来自专栏数据结构与算法

边双联通分量与割边

前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双联通分量 双联通分量一般是指点双连通分量 当然,还有一种叫做边双连通分量 边双联通分量 对于一个...

3826
来自专栏calmound

ZOJ 3631 Watashi's BG(01dp)

01dp不过由于数组过于大,开不开,学了搜索过了,先记录下 还有一种方法 #include<stdio.h> #include<algorithm> using...

3767
来自专栏开发与安全

数据结构:图的存储结构之邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息...

6868

扫码关注云+社区

领取腾讯云代金券