首页 > 代码库 > Python求解登楼梯问题(京东2016笔试题)

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种上法。

Python实现

1.递推法

技术分享
1 def climbStairs1(n):
2     a = 1
3     b = 2
4     c = 4
5     for i in range(n-3):
6         c, b, a = a+b+c, c, b
7     return c
技术分享

2.递归法

技术分享
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)
技术分享

看起来,问题似乎解决了。但是再多考虑一点,方法2中使用递归效率非常低,不仅因为递归时上下文的保存和恢复比较耗时,还因为涉及大量的重复计算。

因此进一步改进,可使用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)
技术分享

 

 

Java实现

1.递推法

技术分享
public static int climbStairs1(int n){
        int a = 1;
        int b = 2;
        int c = 4;
        for(int i=0;i<n-3;i++){
            c = a + b + c;
            b = c - a - b;
            a = c - b - a;
        }
        return c;
    }
技术分享

2.递归法

技术分享
public static int climbStairs2(int n){
        int first[] = new int[3];
        first[0] = 1;
        first[1] = 2;
        first[2] = 4;
        if(n<=3){
            return first[n-1];
        }
        else{
            return climbStairs2(n-1) + climbStairs2(n-2) + climbStairs2(n-3);
        }
    }
技术分享

 

参考资料:微信号:Python_xiaowu

Python求解登楼梯问题(京东2016笔试题)