课后作业

chao_smile 2024/9/5

# 第三十五课

本次上传使用 cpp 文件上传，如无过程，上传 cpp 中使用注释阐明思路也可以，或者涉及哪些知识点，也可以写出来

# 1. 有 `10` 个顶点的无向图至少应该有( )条边才能确保是一个连通图?

✅
历史解析:
- 正确答案：9
- 无向图中，n个顶点的连通图至少有n-1条边，才能确保是一个连通图。因此，10个顶点的无向图至少应该有9条边才能确保是一个连通图。

# 2. 五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有( )种不同排列方法?

✅
历史解析:
- 正确答案：48
- 将双胞胎视为一个整体，那么一共有4个整体，即4!种排列方法。双胞胎内部又有2!种排列方法，所以总共有4!*2! = 48种不同排列方法。

# 3. 独根树的高度为 `1`。具有 `61` 个结点的完全二叉树的高度为多少?

"独根树"是一个描述树结构的术语，指的是只有一个根节点的树，其高度为1。也就是告诉你初始第一层的高度为1。

❌
历史解析:
- 正确答案：6
- 完全二叉树的结点数为2^h - 1，其中h为树的高度。根据题意，完全二叉树有61个结点，所以2^h - 1 = 61，解得h = 6，即完全二叉树的高度为6。
- 注意：2^5 = 32 < 61 < 2^6 = 64，所以完全二叉树的高度为6。

# 4. `10` 个三好学生名额分配到 `7` 个班级，每个班级至少有一个名额，一共有多少种不同的分配方案？

✅
历史解析:
- 正确答案：84
- 这个问题可以转化为一个经典的“隔板法”问题，即在 10 个名额中插入 6 个隔板，形成 7 个班级，并确保每个班级至少有 1 个名额
- 解决思路：
  1. 将问题转化为组合数求解：
    - 由于每个班级至少有 1 个名额，那么我们首先给每个班级分配 1 个名额，这样就已经分掉了 7 个名额，还剩 10 - 7 = 3 个名额需要分配。
    - 现在的问题变成了将这剩下的 3 个名额任意分配到 7 个班级（允许某些班级不再分配额外名额）。
    - 这是一个标准的“隔板法”问题：在 3 个名额中插入 6 个隔板，将其划分为 7 组。每组对应一个班级获得的额外名额。
  2. 组合数表示：
    - 我们的任务是从 3 + 6 = 9 个位置中选择 6 个隔板的位置，剩下的 3 个位置则是名额。
    - 这相当于计算组合数 C(9, 6) 或等价于 C(9, 3)。

点击查看动态规划结合二项式系数的解法

动态规划结合二项式系数的解法：我们可以使用动态规划来计算二项式系数。利用二项式系数的递推关系：

$C(n, k) = C(n-1, k-1) + C(n-1, k)$

并且初始条件为：
- $C(n, 0) = 1$
- $C(n, n) = 1$
步骤：
1. 创建二维数组 dp[n][k] 表示二项式系数 $C(n, k)$ 。
2. 根据递推关系填充该数组。
3. 最后，输出 dp[9][3] 的值，即为答案。
动态规划求解二项式系数的实现思路：
1. 状态定义：
  - 设 dp[n][k] 表示组合数 C(n, k)，即从 n 个物品中选 k 个的方法数。
2. 状态转移方程：
  - 根据二项式系数的递推关系：
  $dp[n][k] = dp[n-1][k-1] + dp[n-1][k]$
3. 边界条件：
  - 当 k == 0 或 k == n 时，dp[n][k] = 1，这是组合数的基本性质。
动态规划步骤：
- 创建二维数组 dp[n][k] 来保存二项式系数。
- 使用递推公式填充数组。
动态规划结合组合数的代码示例：

#include <iostream>
#include <vector>

using namespace std;

// 计算组合数 C(n, k)
int binomialCoefficient(int n, int k) {
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

    // 填充 dp 数组
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= min(i, k); ++j) {
            // 边界条件
            if (j == 0 || j == i) {
                dp[i][j] = 1;
            } else {
                // 状态转移方程
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
    }

    return dp[n][k];
}

int main() {
    int total = 10;
    int classes = 7;

    // 计算将 total - classes 个名额分配到 classes 个班级的组合数
    int n = total - 1;  // 名额和班级之间的隔板数
    int k = classes - 1; // 需要分配的隔板数

    int result = binomialCoefficient(n, k);
    cout << "将 " << total << " 个三好学生名额分配到 " << classes << " 个班级的方案数为: " << result << endl;

    return 0;
}

解释：
- 我们使用了递推公式来计算二项式系数 C(n, k)，并且用动态规划来保存中间结果，避免重复计算。
- 计算出 C(9, 6)（或 C(9, 3)），即从 9 个位置中选择 3 个隔板的位置，最终输出结果为 84。

# 5. 有五副不同颜色的手套(共 `10` 只手套，每副手套左右手各 `1` 只)，一次性从中取 `6` 只手套，请问恰好能配成两副手套的不同取法有多少种?

✅
历史解析:
- 正确答案：120
- 问题分析：
  - 我们有 5 副手套，每副手套包括 1 只左手和 1 只右手。
  - 任务是从这 10 只手套中选出 6 只，要求能配成 恰好 2 副完整的手套，即从 5 副手套中选出 2 副完整手套，并且再从剩余的 3 副手套中选 2 只手套（可以是 1 左 1 右，也可以是 2 左或 2 右）。
- 分步解法：
  - 第一步：从 5 副手套中选择 2 副完整的手套。这相当于从 5 副手套中选择 2 副的组合数 C(5, 2)。
  - 第二步：从剩下的 3 副手套中，随机取出 2 只手套。这可以是 2 只左手，也可以是 2 只右手，或者是 1 左 1 右。对于每一副手套，有 3 种选择：选左手、选右手，或两只都不选。我们只需要从这 3 副手套中选出 2 只不同的手套（不能配成完整的一副手套）。这个组合数是 C(3, 2)，并且在每种情况下，我们有 2 种选择：选左手或选右手。
- 解题思路总结：
  - 首先从 5 副手套中选择 2 副完整的手套，方式数为 C(5, 2)。
  - 然后，从剩下的 3 副手套中挑出 2 只不配对的手套。对于每副手套，可以选择左手或右手手套，方式数是 C(3, 2) * 2^2。

点击查看使用二项式系数和动态规划来解决

使用二项式系数和动态规划来解决：
为了计算组合数 C(n, k)，我们可以使用二项式系数的递推公式：

$C(n, k) = C(n-1, k-1) + C(n-1, k)$

初始条件为：
- $C(n, 0) = 1$
- $C(n, n) = 1$
动态规划的实现步骤：
1. 创建二维数组 dp[n][k] 表示组合数 $C(n, k)$ 。
2. 根据递推关系填充该数组。
3. 计算问题所需的组合数 C(5, 2) 和 C(3, 2)，并根据组合规则计算最后的结果。
动态规划求解代码示例：

#include <iostream>
#include <vector>

using namespace std;

// 计算组合数 C(n, k)
int binomialCoefficient(int n, int k) {
    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

    // 填充 dp 数组
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= min(i, k); ++j) {
            // 边界条件
            if (j == 0 || j == i) {
                dp[i][j] = 1;
            } else {
                // 状态转移方程
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
    }

    return dp[n][k];
}

int main() {
    // 步骤1: 计算从 5 副手套中选出 2 副完整手套的组合数 C(5, 2)
    int completePairs = binomialCoefficient(5, 2);

    // 步骤2: 计算从剩下的 3 副手套中选出 2 只手套的组合数 C(3, 2) * 2^2
    int incompletePairs = binomialCoefficient(3, 2) * (1 << 2);  // 2^2 表示每副手套的左右手选择

    // 总取法数
    int totalWays = completePairs * incompletePairs;

    cout << "恰好配成两副手套的不同取法有: " << totalWays << endl;

    return 0;
}

解释：

binomialCoefficient 函数使用动态规划计算组合数 C(n, k)。
计算 C(5, 2) 得到选 2 副完整手套的组合数。
计算 C(3, 2) 并乘以 2^2，得到从剩余 3 副手套中选出 2 只手套的组合数。
最终乘积结果为 120。

第三十四课第三十六课

讲义

Choose mode

课后作业

课后作业

# 第三十五课

# 1. 有 `10` 个顶点的无向图至少应该有( )条边才能确保是一个连通图?

# 2. 五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有( )种不同排列方法?

# 3. 独根树的高度为 `1`。具有 `61` 个结点的完全二叉树的高度为多少?

# 4. `10` 个三好学生名额分配到 `7` 个班级，每个班级至少有一个名额，一共有多少种不同的分配方案？

# 5. 有五副不同颜色的手套(共 `10` 只手套，每副手套左右手各 `1` 只)，一次性从中取 `6` 只手套，请问恰好能配成两副手套的不同取法有多少种?

讲义

课后作业

课后作业

# 第三十五课

# 1. 有 10 个顶点的无向图至少应该有( )条边才能确保是一个连通图?

# 2. 五个小朋友并排站成一列，其中有两个小朋友是双胞胎，如果要求这两个双胞胎必须相邻，则有( )种不同排列方法?

# 3. 独根树的高度为 1。具有 61 个结点的完全二叉树的高度为多少?

# 4. 10 个三好学生名额分配到 7 个班级，每个班级至少有一个名额，一共有多少种不同的分配方案？

# 5. 有五副不同颜色的手套(共 10 只手套，每副手套左右手各 1 只)，一次性从中取 6 只手套，请问恰好能配成两副手套的不同取法有多少种?

# 1. 有 `10` 个顶点的无向图至少应该有( )条边才能确保是一个连通图?

# 3. 独根树的高度为 `1`。具有 `61` 个结点的完全二叉树的高度为多少?

# 4. `10` 个三好学生名额分配到 `7` 个班级，每个班级至少有一个名额，一共有多少种不同的分配方案？

# 5. 有五副不同颜色的手套(共 `10` 只手套，每副手套左右手各 `1` 只)，一次性从中取 `6` 只手套，请问恰好能配成两副手套的不同取法有多少种?