【华为机试真题详解】小兔子繁殖详解

---

前言

《华为机试真题详解》专栏含牛客网华为专栏、华为面经试题、华为OD机试真题。

如果您在准备华为的面试期间有想了解的可以私信我我会尽可能帮您解答也可以给您一些建议

本文解法非最优解即非性能最优。

讲解试题

题目	详情
DP2 跳台阶	一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法先后次序不同算不同的结果。
【机试题】小兔子繁殖	有一只兔子从出生后第3个月起每个月都生一只兔子小兔子长到第三个月后每个月又生一只兔子假如兔子都不死问到达 M 月时有几只兔子。

如何写一个递归函数

看过上一篇文章的同学可能也发现了递归函数是求解动态规划问题的一个很好的方法那我们要如何写一个递归函数呢

如果一个函数在执行过程中直接或者间接的调用自己我们称之为递归函数。

递归的应用场景链表操作、二叉树操作、排列组合问题和动态规划问题等他们有一个特点就是随着递归深度的增加问题规模在不断减小。

比如我们在学校汇报演出的大礼堂里你想知道你在第几排时会怎么做呢
方案一 走到第一排再一排一排的数到你所在的这一排。
方案二 问前一排的同学是第几排在他的基础上+1就是当前的排数前一排也不清楚的话重复问他的前一排直到问到第一排的同学。

这就是一个简单的递归函数

def dfs(n):
    if n == 1:
        return 1
    return dfs(n-1) + 1

递归问题难实现很重要的一个问题是如何确认递归的终止条件我们在跳台阶问题深入学习

DP2 跳台阶

牛客网入口 DP2 跳台阶简单

一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法先后次序不同算不同的结果。

分析问题时我们考虑从问题规模小的情况入手

当只有一级台阶时只能跳一级也就只有一种跳法
当只有二级台阶时可以一次能跳二级也可以分两次跳一级就有二种跳法
当只有三级台阶时可以先跳二级再跳一级先跳一级再跳两级也可以分三次跳都一级就有三种跳法

再想一下
从三层楼开始
不管是有几层楼梯都是要选择先跳一层还是先跳两层
假如我先跳一层子问题就变成了f(n-1)个跳法的问题
假如我先跳两层子问题就成了f(n-2)个跳法的问题。
往下层子模块叠加

转换下公式:
f(1) = 1
f(2) = 2
f(3) = f(3-1) + f(3-2)
f(4) = f(4-1) + f(4-2)
f(n) = f(n-1) + f(n-2)

想到这里时递归函数的必要条件就都有了

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

到这步就完成了平时常提到的暴力破解也就是没有考虑重复计算问题

这时我们按在上一节提到的优化方式进行优化。

cache = {}
def dfs(n):
    if n in cache:
        return cache[n]
    elif n == 1:
        return 1
    elif n == 2:
        return 2
    cache[n] = dfs(n-1) + dfs(n-2)
    return cache[n]

下面拿一道华为真题练习一下。

小兔子繁殖

【华为机试真题 Python实现】小兔子繁殖

有一只兔子从出生后第3个月起每个月都生一只兔子小兔子长到第三个月后每个月又生一只兔子假如兔子都不死问到达 M 月时有几只兔子。

例如 4 月有 2 只 5 月有 3 只。。。 7 月有 6 只。

转换下公式:
f(1) = 1
f(2) = 1
f(3) = 1
f(4) = f(3) + f(1)
f(5) = f(4) + f(2)
f(6) = f(5) + f(3)
f(7) = f(6) + f(4)

状态转移方程*
f(n) = 1 # n <= 3
f(n) = f(n-1) + f(n-3) # n > 3

暴力递归

def dfs(n):
    if n <= 3:
        return 1
    return dfs(n-1) + dfs(n-3)


while 1:
    try:
        k = int(input())
        print(dfs(k))
    except Exception as e:
        break

加缓存递归

cache = {}

def dfs(n):
    if n in cache:
        return cache[n]
    if n <= 3:
        return 1
    cache[n] = dfs(n - 1) + dfs(n - 3)
    return cache[n]

while 1:
    try:
        k = int(input())
        print(dfs(k))
    except Exception as e:
        break

递归问题是不是一下子就简单了