一、课上练习

编程练习

1. 汉诺塔问题：L3101

二、知识总结

✨ 核心思想

分治法（Divide and Conquer）的核心思想就是"分而治之"。将一个复杂的大问题拆分为多个规模较小但结构相同的子问题，分别解决后再将结果合并，从而得到原问题的解。分治法是算法设计中最重要的策略之一，许多经典算法（如归并排序、快速排序）都基于分治思想。

✨ 适用问题

分治法适用于那些可以自然地分解为重复子问题的问题，具体来说，一个问题适合用分治法解决需要满足以下条件：

• 问题可以被拆解为多个相同结构的小问题
• 子问题之间互相独立，不存在依赖关系
• 子问题的解可以合并为原问题的解
• 存在明确的基案（最小子问题可以直接求解）

✨ 解题思路

分治法的解题思路通常遵循以下三个步骤：

1. 分解（Divide）：将原问题分解为几个规模较小的相同问题。这些子问题互相独立且与原问题形式相同。
2. 解决（Conquer）：递归地解决这些子问题。如果子问题的规模足够小（达到基案），那么可以直接求解，不再继续分解。
3. 合并（Combine）：将子问题的解合并为原问题的解。合并步骤的效率往往决定了整个分治算法的效率。

✨ 执行示例

以经典的汉诺塔问题为例，展示分治法的完整执行过程。

问题：将 3 个盘子从柱子 A 移动到柱子 C，可以借助柱子 B，规则是每次只能移动一个盘子，且大盘子不能放在小盘子上面。

分治思路：把"移动 n 个盘子从 A 到 C"拆分为三步：

1. 把上面 n-1 个盘子从 A 移到 B（借助 C）
2. 把最大的盘子从 A 移到 C
3. 把 n-1 个盘子从 B 移到 C（借助 A）

1hanoi(3, A, B, C)  — 把3个盘子从A移到C
2├── hanoi(2, A, C, B)  — 先把上面2个从A移到B
3│   ├── hanoi(1, A, B, C)  — 把1个从A移到C
4│   │   └── 移动：A → C        （第1步）
5│   ├── 移动：A → B              （第2步）
6│   └── hanoi(1, C, A, B)  — 把1个从C移到B
7│       └── 移动：C → B        （第3步）
8├── 移动：A → C                  （第4步）★ 移动最大盘
9└── hanoi(2, B, A, C)  — 再把2个从B移到C
10    ├── hanoi(1, B, C, A)  — 把1个从B移到A
11    │   └── 移动：B → A        （第5步）
12    ├── 移动：B → C              （第6步）
13    └── hanoi(1, A, B, C)  — 把1个从A移到C
14        └── 移动：A → C        （第7步）

总共 7 步（2^3 - 1 = 7）。可以看到，n 个盘子需要 2^n - 1 步，每次递归都将问题规模减少 1。

✨ 解题步骤详解

遇到一个问题时，判断是否适合用分治法并设计解法：

1. 判断是否可分治：问题能否拆成若干个结构相同的子问题？子问题之间是否独立？子问题的解能否合并为原问题的解？如果三个条件都满足，就可以用分治法。
2. 确定分解方式：通常是将数据从中间分成两半（如归并排序），或选择一个基准将数据分成两组（如快速排序）。
3. 确定基案：问题规模缩小到什么程度可以直接求解？例如数组只剩一个元素时天然有序。
4. 设计合并步骤：这往往是分治法中最关键也最难的部分。例如归并排序中"合并两个有序数组"就是合并步骤。
5. 分析时间复杂度：分治法的时间复杂度可用主定理（Master Theorem）分析。常见结论：分成 2 份、合并 O(n) → 总 O(n log n)。

✨ 常见错误

• 子问题不独立却用分治：如果子问题之间有重叠（如斐波那契数列的递归），直接分治会导致大量重复计算，应该用动态规划代替。
• 基案处理不当：忘记写基案会导致无限递归。基案条件太早（如 n<=2 直接返回）可能遗漏边界情况。
• 合并步骤错误：合并是分治法的核心，如果合并逻辑有误，即使子问题都解对了，最终结果也会错。
• 分解不均匀：如果每次分解都极不均匀（如总是分成 1 和 n-1），时间复杂度会从 O(n log n) 退化到 O(n^2)。这就是快速排序最坏情况的成因。
• 递归栈空间不足：分治法递归深度通常为 O(log n)，一般不会栈溢出。但如果分解不均匀，递归深度可能达到 O(n)。

三、课后练习

编程练习

1. 循环比赛日程表：L3102