问题:假设一段楼梯共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 cdef 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
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: ImageIO的应用 (AWT和Swing初接触)
ImageIO的应用 一、关于IO流 在讲imageio之前,我们先来复习一下IO流的使用。 这里我建立一个Java类,用来实现读取文档中的内容,并且能够识别换行,话不多说,上代码: package com.Evan.demo; import java.io.…