"""
题目：
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级，...，它也可以跳上 n 。
此时该青蛙跳上一个 n 级的台阶总共有多少种跳法。

思路：
设 f(n) 为跳上 n 级台阶的跳法。

分情况讨论：
1. 第一步跳 1 步，剩下的台阶有 f(n-1) 种跳法
2. 第一步跳 2 步，剩下的台阶有 f(n-2) 种跳法
...
n-1. 第一步跳 (n-1) 步，剩下的台阶有 f(1) 种跳法
n. 第一步跳 n 步，剩下的台阶有 1 种跳法

得到：f(n) = f(n-1) + f(n-2) + ... + f(1) + 1
同理：f(n-1) = f(n-2) + f(n-3) + ... + f(1) + 1
所以：f(n) = f(n-1) + f(n-1) = 2 * f(n-1)
"""

# 递归
def super_frog_jump1(n):
    if n == 1:
        return 1
    else:
        return 2 * super_frog_jump1(n - 1)


# 根据公式算
def super_frog_jump2(n):
    return 2 ** (n - 1)


if __name__ == '__main__':
    n = 3
    print(f'跳{n}级台阶的跳法有：{super_frog_jump1(n)}种')
    print(f'跳{n}级台阶的跳法有：{super_frog_jump2(n)}种')

"""
跳3级台阶的跳法有：4种
跳3级台阶的跳法有：4种
"""
