【练习】青蛙跳井

项目简介

读写文件

知识模块

Python 编程语言

知识点

类和对象
递归
封装

受众

初级测试开发工程师
初级Python开发工程师

作业要求

编写一个Python程序:青蛙跳台阶，共有10阶台阶，青蛙每次可以选择跳一阶或者两阶，

问：青蛙跳上这10个台阶共有多少种跳法。

解题思路

我们可以发现，跳上第 n 个台阶的跳法数只与跳上前两个台阶的跳法数有关。如果我们知道了跳上第 n-1 个台阶和跳上第 n-2 个台阶的跳法数，就可以得到跳上第 n 个台阶的跳法数。
特殊情况下，当只有 1 个台阶时，只有一种跳法；当有 2 个台阶时，有两种跳法。
因此，我们可以使用递归的方式解决这个问题。递归的终止条件是当台阶数为 1 或 2 时，直接返回相应的值。
在递归的过程中，通过递归调用 jump 方法计算跳上前两个台阶的跳法数，并将结果相加得到跳上第 n 个台阶的跳法数。
为了避免重复计算，我们可以使用一个字典 memo 来记录已经计算过的结果，每次先检查字典中是否已经计算过当前台阶的跳法数。如果有，则直接返回对应的结果，否则进行计算并保存到字典中。这样，通过递归调用和记录已计算结果的方法，我们可以得到青蛙跳上任意数量的台阶的跳法数。

完整代码

class Frog:
    def __init__(self):
        self.memo = {}                   # 用字典记录已经计算过的结果

    def jump(self, n):                   # 跳跃方法接受一个参数表示台阶数
        if n in self.memo:               # 如果该台阶的跳法已经计算过
            return self.memo[n]          # 直接返回计算结果
        if n == 1:                       # 如果只有一阶台阶
            return 1                    # 返回 1 种跳法
        if n == 2:                       # 如果有两阶台阶
            return 2                    # 返回 2 种跳法
        # 递归调用 jump 方法计算 n-1 和 n-2 台阶的跳法数
        res = self.jump(n-1) + self.jump(n-2)
        self.memo[n] = res               # 将计算结果保存到字典中
        return res                       # 返回计算结果

frog = Frog()                           # 创建 Frog 类的实例对象
num_of_ways = frog.jump(10)             # 调用 jump 方法计算青蛙跳上 10 个台阶的跳法数
print(f"青蛙跳上这10个台阶共有 {num_of_ways} 种跳法。")   # 打印结果

代码讲解

定义一个名为 Frog 的类，并在类的构造方法 __init__ 中初始化一个空的字典 memo，用于记录已经计算过的结果。
在跳跃方法 jump 中，首先检查字典 memo 中是否已经计算过台阶数 n 的跳法数。如果是，则直接返回已经计算过的结果。
然后判断特殊情况，如果台阶数 n 为 1，则直接返回 1 种跳法；如果台阶数 n 为 2，则返回 2 种跳法。
如果不是以上两种情况，递归调用 jump 方法计算 n-1 和 n-2 台阶的跳法数，并将结果相加得到 n 台阶的跳法数。
将计算得到的结果保存到字典 memo 中，并返回该结果。
创建一个 Frog 类的实例对象 frog，通过调用 frog.jump(10) 方法，计算青蛙跳上 10 个台阶的跳法数。
使用 print 函数打印出结果。