讲义

课后作业

2023/12/24

# 一只青蛙从地面开始起跳,它一次可以跳1级台阶，也可以一次跳2级台阶，但是出于体力因素不允许连着两次跳2级台阶。求这只青蛙跳上一个n级台阶总共有多少办法？

不允许连着两次跳 2 级台阶,规定了在任意连续两步中，至少有一步是跳 1 级台阶。

// 输入输出示例：
// 为详细展示示例，所有的输入都添加了换行，实际编写输入打印可以不换行

// 示例 1：
// 输出
请输入台阶的级数 n:
// 输入
3
// 输出
青蛙跳上 3 级台阶的方法总数为: 3

// 示例 2：
// 输出
请输入台阶的级数 n:
// 输入
6
// 输出
青蛙跳上 6 级台阶的方法总数为: 9

# 思路

  • 令 f[n] 为跳 n 级台阶的方法数。
  • 用 g[n] 表示最后一步不是跳 2 级的走法数目，h[n] 表示最后一步跳 2 级的走法数目。
  • 显然有：f[n] = g[n] + h[n]
  • h[n] = g[n-2]，因为在不能连着两次跳 2 级的情况下，倒数第二步不是跳 2 级，最后一步跳 2 级。
  • g[n] = g[n-1] + h[n-1]，即倒数第二步的走法加上最后 1 级台阶的走法减去先 g[n-1] 再 1 级和先 h[n-1] 再 1 级。
  • f[n] = g[n] + h[n] = g[n-1] + g[n-3] + g[n-2]
  • f[n-1] = g[n-1] + h[n-1] = g[n-1] + g[n-3]
  • f[n] = f[n-1] + g[n-2]
  • g[n-2] = g[n-3] + h[n-3] = f[n-3]
  • 因此，有f[n] = f[n-1] + f[n-3]

# 已知条件

  • f[0] = 1
  • f[1] = 1
  • f[2] = 2
  • f[3] = 3
  • f[n]：跳上一个n级台阶的总方法数。
  • g[n]：最后一步不跳2级台阶的方法数。
  • h[n]：最后一步跳2级台阶的方法数。

根据题目条件，有以下关系：

  1. f[n] = g[n] + h[n]

    这是因为跳上n级台阶的方法可以分为两种：最后一步跳1级或者最后一步跳2级。

  2. h[n] = g[n-2]

    这表示如果最后一步跳2级台阶，那么倒数第二步不能跳2级（因为不能连续两次跳2级），所以h[n]的方法数等同于g[n-2]的方法数。

  3. g[n] = g[n-1] + h[n-1]

    这表示最后一步跳1级台阶的方法数。它可以从n-1级台阶的任何一种方法（g[n-1]）跳上来，或者从n-2级台阶通过最后一步跳2级（h[n-1]）达到。

将这些关系式联立起来，得到：

  1. f[n] = g[n] + h[n] = (g[n-1] + h[n-1]) + g[n-2]

  2. 因为h[n-1] = g[n-3]，所以f[n] = g[n-1] + g[n-3] + g[n-2]

  3. 又因为f[n-1] = g[n-1] + h[n-1] = g[n-1] + g[n-3]，所以：

  4. f[n] = f[n-1] + g[n-2]

  5. 又因为g[n-2] = f[n-3]（因为g[n-2] = g[n-3] + h[n-3]，而h[n-3] = g[n-5]，递归下去会发现g[n-2]包括了所有f[n-3]的情况），所以：

  6. f[n] = f[n-1] + f[n-3]

这个递推公式表示，要跳到第n级台阶，可以从第n-1级台阶跳上来，或者从第n-3级台阶通过最后一步跳2级台阶跳上来。

基本情况是：

  • f[0] = 1：没有台阶的情况，默认为1种方法。
  • f[1] = 1：跳1级台阶只有1种方法。
  • f[2] = 2：跳2级台阶有两种方法：一次跳2级或两次各跳1级。
  • f[3] = 3：跳3级台阶有3种方法：三次各跳1级，一次跳1级后跳2级，或先跳2级后跳1级。

我们可以详细探讨一下为什么 h[n] = g[n-2] 这个等式成立。在这个问题中，h[n] 表示的是跳上第 n 级台阶，并且最后一步跳 2 级台阶的方法数。

为了理解这个等式，我们需要考虑在最后一步跳 2 级台阶的情况下，前面的跳跃方式。由于题目的约束是不能连续两次跳 2 级台阶，所以在最后一次跳 2 级台阶之前，青蛙必须在第 n-2 级台阶上。更重要的是，在第 n-2 级台阶上的最后一步不能是跳 2 级台阶的方式，否则就会违反“不能连续两次跳 2 级台阶”的规则。

因此，我们可以将问题转化为：有多少种方法可以跳到第 n-2 级台阶上，并且保证在那里的最后一步不是跳 2 级台阶的方式。而这正是 g[n-2] 的定义 —— 即跳到第 n-2 级台阶，并且最后一步不跳 2 级的方法数。

综上所述，h[n] = g[n-2] 的含义是：跳到第 n 级台阶，且最后一步跳 2 级的方法数，等同于跳到第 n-2 级台阶，且最后一步不跳 2 级的方法数。这是因为从第 n-2 级台阶到第 n 级台阶的最后一跳必须是 2 级，且符合题目条件，不违反“不能连续两次跳 2 级台阶”的规则。

让我们更详细地探讨 g[n] = g[n-1] + h[n-1] 这个等式。在这个问题中，g[n] 表示的是跳到第 n 级台阶，且最后一步不是跳 2 级台阶的方法数。

要理解这个等式，我们需要考虑跳到第 n 级台阶的两种不同情况，其中最后一步都不是跳 2 级台阶：

  1. 最后一步是从第 n-1 级台阶跳上来的：在这种情况下，我们只需考虑跳到第 n-1 级台阶的所有可能方法。因为最后一步是跳 1 级，所以不管之前是怎样跳到第 n-1 级台阶的（无论最后一步是跳 1 级还是跳 2 级），都可以通过再跳 1 级到达第 n 级台阶。因此，这部分的方法数就是 g[n-1]。

  2. 最后一步是从第 n-2 级台阶跳上来的，但倒数第二步不是跳 2 级台阶：这种情况下，青蛙最后一步跳了 2 级台阶到达第 n 级台阶，但由于我们在考虑的是 g[n]，即最后一步不能是跳 2 级的情况，所以这种方式实际上是不可能的。因此，这部分的贡献是 0。

综合这两种情况，我们得到 g[n] = g[n-1]。但注意，这里我们没有考虑的是，如果在第 n-1 级台阶的最后一步是跳 2 级台阶，由于题目中的限制，这意味着在第 n-1 级台阶之前的一步（即在第 n-3 级台阶上）不能是跳 2 级的。这正是 h[n-1] 的定义 —— 跳到第 n-1 级台阶，且最后一步是跳 2 级台阶的方法数。因此，我们也需要把这部分方法加入到 g[n] 中。

所以，最终我们得到的公式是 g[n] = g[n-1] + h[n-1]。这个等式的含义是：跳到第 n 级台阶，且最后一步不是跳 2 级的方法数，等于跳到第 n-1 级台阶的方法数（最后一步跳 1 级）加上跳到第 n-1 级台阶且最后一步是跳 2 级的方法数（此时第 n-1 级台阶之前的一步不能是跳 2 级）。

了解 h[n-1] = g[n-3] 这个等式，我们需要考虑在跳到第 n-1 级台阶时最后一步跳 2 级台阶的情况。

h[n-1] 表示的是跳到第 n-1 级台阶，并且最后一步跳 2 级台阶的方法数。由于最后一步跳了 2 级台阶，青蛙在此之前必须在第 n-3 级台阶上。关键点在于，根据题目的限制，青蛙不能连续两次跳 2 级台阶。这意味着，在第 n-3 级台阶上的最后一步不能是跳 2 级台阶的方式。

现在的问题转化为：有多少种方法可以跳到第 n-3 级台阶，并且保证在那里的最后一步不是跳 2 级台阶的方式。这正是 g[n-3] 的定义 —— 即跳到第 n-3 级台阶，并且最后一步不跳 2 级的方法数。

所以，h[n-1] = g[n-3] 的含义是：跳到第 n-1 级台阶，且最后一步跳 2 级的方法数，等同于跳到第 n-3 级台阶，且最后一步不跳 2 级的方法数。这是因为从第 n-3 级台阶到第 n-1 级台阶的最后一跳必须是 2 级，且符合题目条件，不违反“不能连续两次跳 2 级台阶”的规则。

让我们详细探讨 f[n-1] = g[n-1] + h[n-1] = g[n-1] + g[n-3] 这个等式。在这个问题中，f[n-1] 表示的是跳到第 n-1 级台阶的所有可能方法数。

这个等式的理解需要从 f[n] 的定义开始，即跳到第 n 级台阶的所有方法数。这可以被分解为两部分：

  1. g[n]: 跳到第 n 级台阶，且最后一步不是跳 2 级台阶的方法数。
  2. h[n]: 跳到第 n 级台阶，且最后一步是跳 2 级台阶的方法数。

因此，有 f[n] = g[n] + h[n]。

同样的逻辑也适用于 f[n-1]，即跳到第 n-1 级台阶的所有方法数，可以分为：

  1. g[n-1]: 跳到第 n-1 级台阶，且最后一步不是跳 2 级台阶的方法数。
  2. h[n-1]: 跳到第 n-1 级台阶，且最后一步是跳 2 级台阶的方法数。

因此，有 f[n-1] = g[n-1] + h[n-1]。

接下来，根据我们之前的讨论，我们知道 h[n-1] = g[n-3]。这是因为，如果最后一步是跳到第 n-1 级台阶的 2 级台阶，那么青蛙之前必须在第 n-3 级台阶上，且那时的最后一步不能是跳 2 级台阶（以避免连续两次跳 2 级台阶）。

将 h[n-1] 替换为 g[n-3]，我们得到 f[n-1] = g[n-1] + g[n-3]。这个等式的含义是，跳到第 n-1 级台阶的所有方法数等于跳到第 n-1 级台阶且最后一步不是跳 2 级台阶的方法数加上跳到第 n-3 级台阶且最后一步不是跳 2 级台阶的方法数。

# 参考答案

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入台阶的级数 n: ";
    cin >> n;

    int ways;

    if (n == 0 || n == 1) {
        ways = 1;
    } else if (n == 2) {
        ways = 2;
    } else {
        int fn_minus_1 = 2;  // f[n-1]
        int fn_minus_2 = 1;  // f[n-2]
        int fn_minus_3 = 1;  // f[n-3]

        int fn = 0;

        for (int i = 4; i <= n; ++i) {
            fn = fn_minus_1 + fn_minus_3;
            fn_minus_3 = fn_minus_2;
            fn_minus_2 = fn_minus_1;
            fn_minus_1 = fn;
        }

        ways = fn_minus_1 + fn_minus_3;
    }

    cout << "青蛙跳上" << n << "级台阶的方法总数为" << ways <<  endl;

    return 0;
}

# 复习知识点

  • # 负数的定义：

  1. 整数的拓展： 负数的引入是为了扩展整数的概念。在自然数和整数的基础上，引入了负数，使得数学体系更加完备。

  2. 小于零的实数： 从数轴的角度来看，负数位于零的左侧。对于实数集合，负数是小于零的实数。

  3. 符号表示： 负数通常用负号（-）表示，紧接在一个数值之前，例如-3，-5，-10 等。这个负号表示这个数在数轴上的位置相对于零是在左侧。

  4. 相反数： 一个数的相反数是与它在数轴上对称的数。例如，对于任何实数 x，其相反数是-x，而-x 的相反数是 x。相反数的引入使得负数在运算中更加灵活，同时满足加法的封闭性。

  • # 负数的运算规则：

  1. 加法： 负数与负数相加，结果为负数；正数与负数相加，结果可能为正数、负数或零，取决于它们的相对大小。

  2. 减法： 减去一个负数相当于加上它的相反数；负数减去正数，结果为负数。

  3. 乘法： 两个负数相乘，结果为正数；正数与负数相乘，结果为负数。

  4. 除法： 负数除以正数，结果为负数。

负数和正数关系
  1. 定义

  • 正数（Positive Numbers）： 正数是大于零的实数。在数轴上，它们位于零的右侧。正数用正号表示，例如 3，5，100 等。

  • 负数（Negative Numbers）： 负数是小于零的实数。在数轴上，它们位于零的左侧。负数用负号表示，例如-2，-7，-50 等。

  1. 数轴
  • 数轴（Number Line）： 数轴是一个水平直线，通常从左到右排列，代表了所有实数的有序集合。零位于数轴的中心，正数在右侧，负数在左侧。
  1. 相反数
  • 相反数（Opposite or Additive Inverse）： 一个数的相反数是与它在数轴上对称的数。例如，对于任何实数 x，其相反数为-x，而-x 的相反数为 x。
  1. 数学运算

  • 加法： 正数与正数相加，结果仍然是正数；负数与负数相加，结果仍然是负数；正数与负数相加，结果可能是正数、负数或零，取决于它们的相对大小。

  • 减法： 减去一个正数相当于加上它的相反数；减去一个负数相当于加上它的相反数；负数减去正数，结果为负数。

  • 乘法： 两个正数相乘，结果为正数；两个负数相乘，结果为正数；正数与负数相乘，结果为负数。

  • 除法： 正数除以正数，结果为正数；负数除以负数，结果为正数；正数除以负数，结果为负数。

  1. 应用

  • 方向与位移： 在物理学和工程学中，正数和负数可用于描述方向和位移，其中正方向通常表示向右或向上，而负方向表示向左或向下。

  • 温度： 温度的正负号表示相对于冰点的温度高低，正数表示高于冰点，负数表示低于冰点。

  • 财务： 正数通常表示收入、盈利等正面变化，而负数表示支出、亏损等负面变化。

  • # 次幂

次幂指的是幂函数中指数的值，表示对一个数进行多次相同的乘法运算。具体表示如下：

  1. 零次幂： a0 = 1，任何数的 0 次幂都等于 1。

  2. 一次幂： a1 = a，任何数的一次幂都等于它自身。

  3. 二次幂： a2 = a * a，也写作 a 的平方。表示将 a 乘以自身一次。

  4. 三次幂： a3 = a * a * a，也写作 a 的立方。表示将 a 乘以自身两次。

  5. 四次幂： a4 = a * a * a * a，表示将 a 乘以自身三次。

  6. 通用形式： an * am=a(n+m)，当 n 和 m 不等于 0 时，此等式成立。

  • # 列项相消

"列项相消" 是一个数学概念，通常用于化简代数表达式。有时需要对多项式进行简化或整理，这时可以使用列项相消法。

列项相消法的基本思想是，如果两个或多个代数表达式相加（或相减）的各项中，包含相同的代数项（或相反的代数项），那么这些相同的项可以彼此相消，从而简化表达式。

假设有表达式：

3x + 5y - 2x - 7y

这个表达式中包含 (3x) 和 (-2x)，以及 (5y) 和 (-7y)，这些项可以相消。

通过列项相消，我们可以简化这个表达式：

(3x - 2x) + (5y - 7y)

进行相加运算：

x - 2y

这就是列项相消的结果。

通过这种方法，我们去掉了相同的项，使表达式更加简洁。

  • # 合并相消

"合并相消"是列项相消中对于多个方程式的处理应用

两个式子时，我们通常是指将两个代数表达式相加或相减，并利用相同的项进行合并和简化。

以下是一个例子：

考虑两个表达式：

A = 3x + 5y - 2z

B = 2x - 4y + 2z

现在我们想要将这两个表达式相加：

A + B = (3x + 5y - 2z) + (2x - 4y + 2z)

通过列项相消法，我们可以合并相同的项：

(3x + 2x) + (5y - 4y) + (-2z + 2z)

进行相加运算：

5x + y

在这个例子中，(A + B) 的结果是 (5x + y)，通过合并相消，我们去掉了相同的项 (-2z + 2z)。这就是列项相消的应用。

上次更新: 2024-10-19 10:01:51

第九课