课后作业

第二十六课

1. 名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力，0 < N < 20）。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：

• 如果 N = 1，则名名第1天就吃掉它，共有1种方案；
• 如果 N = 2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；
• 如果 N = 3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有 2 + 1 = 3 种方案；
• 如果 N = 4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有 3 + 2 = 5 种方案。

现在给定 N，请你写C++程序求出名名吃巧克力的方案数目。

// 示例输入：
请输入巧克力的块数N: 4

// 示例输出：
5

• ✅

• 历史解析

  • 整体思路正确,本题考察使用动态规划，没有问题💯
  • 你的思路是
    • 创建一个长度为 N + 1 的向量 dp，其中 dp[i] 表示吃完 i 块巧克力的方法数
    • 初始化 dp[0] = 1，因为吃完 0 块巧克力只有 1 种方法（什么都不做）
    • 通过遍历 1 到 N，累加 dp[i - 1] 和 dp[i - 2] 来求 dp[i]
  • 还有一种思路，其实此题推导类似于斐波那契数列，考虑最后一步名名可以吃1块或者2块，因此有：f(n) = f(n-1) + f(n-2)
    • 其中：
    • 当 n = 1 时， f(1) = 1
    • 当 n = 2 时， f(2) = 2

• 参考答案

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    // 动态规划数组，考虑到 0 < N < 20，所以大小为 21 以确保边界
    int dp[21] = {0};
    
    // 初始化前两个值
    dp[1] = 1; // 1 块巧克力只有一种吃法
    dp[2] = 2; // 2 块巧克力有两种吃法
    
    // 根据递推关系计算方案数
    for (int i = 3; i <= N; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    // 输出结果
    cout << dp[N] << endl;
    
    return 0;
}

2. 将M个相同的苹果放入N个相同的盘子中，允许有的盘子空着不放，问共有多少种不同的分法？注意，不同的分法是指苹果的分配情况不同，而不是盘子的排列顺序不同。例如，5个苹果放入3个盘子时，分法（5, 0, 0）和（0, 5, 0）被认为是同一种分法

小提示

1. 理解第二类斯特林(Stirling)数

第二类斯特林数 S(n, m) 表示将 n 个有区别的球放入 m 个无区别的盒子中，且每个盒子至少有一个球的分法数。递推关系为： S(n, m) = m * S(n-1, m) + S(n-1, m-1)

解释这个关系：

• 第一项 m * S(n-1, m) 表示将一个球放入 m 个已有的任意一个盒子中，剩下的 n-1 个球放入 m 个盒子。
• 第二项 S(n-1, m-1) 表示将一个球放入一个新的盒子中，剩下的 n-1 个球放入剩下的 m-1 个盒子。

2. 转换问题

将 M 个苹果放入 N 个盘子中的问题可以分为两部分：

1. 至少有一个盘子为空（相当于将 M 个苹果放入 N-1 个盘子中）。
2. 每个盘子至少有一个苹果（相当于将 M-N 个苹果放入 N 个盘子中，因为每个盘子至少有一个苹果）。

3. 应用球的思想

我们可以将问题分解为两部分：

1. 部分盘子为空的情况：

   • 如果允许部分盘子为空，那么问题可以转换为将 M 个苹果放入 N-1 个盘子中。这种情况的分法数是 K(M, N-1)。

2. 无一盘子为空的情况：

   • 如果要求无一盘子为空，我们可以先将每个盘子放一个苹果，那么还剩 M-N 个苹果需要放入 N 个盘子中。这种情况的分法数是 K(M-N, N)。

于是，我们可以得到递推关系： K(M, N) = K(M, N-1) + K(M-N, N)

4. 特殊情况

• 当 N > M 时，显然有多余的盘子，空盘子不影响结果，相当于将 M 个苹果放入 M 个盘子： K(M, N) = K(M, M)

• 边界条件：

  • 当 M = 0 时，无论有多少盘子，只有一种分法，即都不放苹果： K(0, N) = 1

  • 当 N = 0 时，苹果数大于盘子数，没有合法分法： K(M, 0) = 0

// 示例输入：
请输入苹果的个数M: 5
请输入盘子的个数N: 3

// 示例输出：
5

• ✅
• 历史解析
  • 整体思路正确,本题考察使用递推关系以及递归函数求解，没有问题💯
  • 注意阅读题目推导关系过程，理解第二类斯特林数的定义，以及将问题转换为球的问题，这样可以更好的理解问题的本质

3. 给定一个正整数序列，在每个数之前都可以插入 + 号或 - 号，然后计算它们的和。例如，序列 1, 2, 4 有以下 8 种可能的和：

• (+1) + (+2) + (+4) = 7
• (+1) + (+2) + (-4) = -1
• (+1) + (-2) + (+4) = 3
• (+1) + (-2) + (-4) = -5
• (-1) + (+2) + (+4) = 5
• (-1) + (+2) + (-4) = -3
• (-1) + (-2) + (+4) = 1
• (-1) + (-2) + (-4) = -7

如果所有可能的和中至少有一个可以被整数 k 整除，我们称此正整数序列可以被 k 整除。例如，上述序列可以被 3、5、7 整除，而不能被 2、4、6、8 整除。

注意：0、±3、±6、±9 等都可以认为是 3 的倍数。

• 第一行包含两个整数 N 和 k（2 < N < 10000, 2 < k < 100），其中 N 表示数的个数，k 表示被除数。

• 第二行包含 N 个整数，这些整数的取值范围都在 1 到 10000 之间（可能重复）。

• 如果序列中存在一个和可以被 k 整除，则输出 YES，否则输出 NO。（注意：输出均为大写字母）

// 示例输入：
请输入整数的个数 N 和被除数 k（空格分隔）: 3 3
请输入 N 个整数（空格分隔）: 1 2 4

// 示例输出：
YES

• ✅
• 历史解析
  • 整体思路正确,本题核心思想是通过遍历所有可能的符号组合来计算所有可能的和，然后检查这些和是否可以被 k 整除，没有问题💯
  • 你的思路是
    • 通过位移操作符来计算，例如：(1 << N) 是用来计算有多少种符号组合的。对于一个长度为 N 的整数序列，每个整数前面可以有 + 或 -，共有 2^N 种组合。1 << N 恰好等于 2^N
  • 思考一下如果不使用位移操作符，你会如何计算这个值呢？