最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

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

XAMPP案例 admin 49浏览 0评论

【变态跳台阶】


题目描述

一只青蛙一次可以跳上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代码实现递归和循环-变态跳台阶