python代码实现递归和循环-变态跳台阶

【变态跳台阶】

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

思路

1)假设跳上第n级台阶的跳法为a(n)，跳上第n级台阶可以从前面所有已有的台阶上直接一次跳到第n级台阶，以及直接1次从原地跳到第n级台阶,a(1)=1, a(2)=a(1)+1=2,当n>=2时,a(n)=a(n-1)+a(n-2)+…+a(2)+a(1)+1 (式1),最后加1就是从原地跳到第n级台阶。a(n+1)=a(n)+a(n-1)+…+a(2)+a(1)+1 (式2),两式相减得a(n+1)-a(n)=a(n),即a(n+1)=2a(n),n>=2时为等比数列, a(n)=a(2)*q^(n-2)=2^(n-1),又a(1)=1也满足通项，因此a(n)=2^(n-1)。

2) n>2时，要跳上第n级台阶，则第n级台阶是必选的，从原地到第n级中间还有n-1级台阶，其中每一级可以有跳上或不跳两种选择，因此n>2时，a(n)=2^(n-1)，a(1)也满足，因此a(n)=2^(n-1)。

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number == 0:
            return 0
        return 2**(number-1)

测试:

s=Solution()num=10print('青蛙跳到{}级台阶共有{}种跳法'.format(num,s.jumpFloorII(num)))# result青蛙跳到10级台阶共有512种跳法

# -*- coding:utf-8 -*-class Solution:    def jumpFloorII(self, number):        # write code here        if number == 0:            return 0        return 2**(number-1)

转载请注明：XAMPP中文组官网 » python代码实现递归和循环-变态跳台阶