首页 ›存档› 技术 › 查看内容

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

2018-3-30 13:00 |来自: 互联网 2634 0

摘要: 问题：假设一段楼梯共15个台阶，小明一步最多能上3个台阶，那么小明上这段楼梯一共有多少种方法？解析：从第15个台阶上往回看，有3种方法可以上来（从第14个台阶上一步迈1个台阶上来，从第13个台阶上一步迈2个台阶 ...

问题：假设一段楼梯共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)，更多微信文章请扫描关注公众号:

声明：文章版权归原作者所有部分文章转自互联网如有侵权请联系 [邮箱地址] 删除

路过

雷人

握手

鲜花

鸡蛋

收藏分享邀请

上一篇：Python爬虫入门（一）：爬虫基本结构下一篇：最难搞的python“反面”代码

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

相关分类