题解 | #HJ37 统计每个月兔子的总数#

方法1-递归

 def f(n):
     if n == 1 or n == 2:
         return 1
    return f(n-1) + f(n-2)

while True:
    try:
        n = int(input())
        print(f(n))
    except:
        break


# 最开始的分析思路：
# 出生满2月的兔子后面每次会生育小兔子，即上上月及之前新增的兔子，每过一个月都要累加进去。
# f(1) = 1
# f(2) = 1
# f(3) = 2
# f(4) = 2+(1-0)=3
# f(5) = 3+(1-0)+(2-1)=5
# f(6) = 5+(1-0)+(2-1)+(3-2)=8
# 这里(1-0)+(2-1)可以用5-3表示
# 所以，f(6) = 5+(5-3)+(3-2) = 5+5-2 = 2*f(5)-f(3) = 13
# ...
# f(n) = 2*f(n-1) - f(n-3)

'''
def f(n):
    if n==1 or n==2:
        return 1
    elif n==3:
        return 2
    else:
        return int(2*f(n-1) - f(n-3))
'''

方法2-动态规划

while True:
    try:
        n = int(input())
        n0 = 1  # 刚出生的兔子数
        n1 = 0  # 满一个月的兔子数
        n2 = 0  # 满二个月及以上的兔子数

        for n in range(1, n):
            n2 += n1
            n1 = n0
            n0 = n2
        print(n0 + n1 + n2)
    except:
        break

方法3-斐波那契

这是斐波那契数列问题，从第2项开始，每一项都是前两项的和。

这里是从第3个月开始，每个月的兔子总数是前两个月兔子总数的和。

def f(n):
    if n <= 2:
        return 1
    a, b = 1, 1
    for i in range(3, n + 1):
        a, b = b, a + b
    return b

n = int(input())
print(f(n))