python算法:青蛙跳台阶

1，题目

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

青蛙一次可以跳1级，也可以跳2级

1，台阶只有一级时:
台阶有1级时，只有1种跳法

台阶有1级时，只有1种跳法

2，台阶有2级时，有2种跳法:
a, 先跳1级，后跳1级
b, 一次跳2级

上图：先跳1级后跳1级,下图：1次跳2级

3,台阶有3级时，分两种情况:
第一种情况:
先跳1级，再跳后2级即:f(n-1)：先跳一级，后跳一级:

3级台阶时：一次1级跳3次

先跳1级，再跳后2级即:f(n-1)：一次跳2级:

先跳1级，后2级一次跳2级

第二种情况:先跳2级，后跳1级:即:f(n-2):

先跳2级，后跳1级

4，总结:

当青蛙第一次跳一级台阶时，
有f(n-1)种跳法,
当青蛙第一次跳二级台阶时，
有f(n-2)种跳法
所以在n>2时，
返回f(n-1) f(n-2)即可

1,递归思路:
n = 0: 返回0
n = 1: 返回1
n = 2: 返回2
n>2时:返回 f(n-1) f(n-2)
可以得到如下的方程式，
有终止递归的条件，有对自身的调用，这是很典型的递归形式,

方程式

2，循环的思路
因为已知第1，2个数据的值，
所以可以得到一个数列，
注意它的形式:
1,2,3,5,8,13,21, 34,55,89…
与斐波那契数列很相似，
它也可以用循环来解决

1,递归函数实现：

# 递归函数 # n: 要跳的台阶数 def jump(n): if n <= 0: # 值小于等于0时，返回0，递归终止 return 0 elif n == 1: # 值小于等于1时，返回1，递归终止 return 1 elif n == 2: # 值小于等于2时，返回2，递归终止 return 2 else: # 值大于2时，返回跳n-1级和跳n-2级时的和 return jump(n - 1) jump(n - 2) num = int(input("请输入青蛙要跳的台阶数:")) print(f"跳{num}级台阶，共有跳法{jump(num)}种")

运行结果:

请输入青蛙要跳的台阶数:8 跳8级台阶，共有跳法34种

2，循环实现：

# n: 要跳的台阶数 def jump(n): if n == 1: return 1 elif n == 2: return 2 pre1 = 1 # 前两个数中的第1个 pre2 = 2 # 前两个数中的第2个 res = 0 # 跳法的数量 for i in range(3, n 1): res = pre1 pre2 # 得到数列中的当前值 pre1 = pre2 # 迭代变量，前2个数中的第2个变为前2个数中的第1个 pre2 = res # 迭代变量，当前数变为前2个数中的第2个 return res num = int(input("请输入青蛙要跳的台阶数:")) print(f"跳{num}级台阶，共有跳法{jump(num)}种")

运行结果:

请输入青蛙要跳的台阶数:8 跳8级台阶，共有跳法34种