🧩 课堂笔记：分治算法——像“分蛋糕”一样解决问题

                                                     --彭彭老师

一、什么是分治？（一句话概括）

“大事化小，小事化了”——把大问题拆成小问题，逐个解决，再合并结果！

生活中的例子：

1. 分蛋糕：一个大蛋糕太难切？先切成小块，再分给每个人！
2. 整理书包：书本太多太乱？先分类（语文、数学、英语），再分别整理！
3. 大扫除：教室太大打扫不完？分组负责不同区域，最后汇总！

---

二、分治的三步魔法

第一步：分解

把一个大问题拆成几个相似的小问题

✅ 例如：把“整理全班同学的作业”拆成“整理第一组、第二组……的作业”

第二步：解决

解决最简单的小问题（通常是“不用再拆”的时候）

✅ 例如：整理一个同学的作业（直接放进书包！）

第三步：合并

把小问题的答案组合成大问题的答案

✅ 例如：把每个小组整理好的作业收齐，就是全班的作业！

---

三、经典例子：汉诺塔（可视化游戏）

游戏规则：

• 3根柱子（A、B、C）
• 从小到大的一叠圆盘（在A柱上）
• 目标：把所有圆盘移到C柱
• 规则：①一次只能移动一个圆盘；②大盘不能压在小盘上

分治解法：

1. 分解：把“移动N个盘子”拆成：
   • 把上面(N-1)个盘子移到B柱（临时存放）
   • 把最大的盘子移到C柱
   • 把(N-1)个盘子从B柱移到C柱
2. 解决：当只剩1个盘子时，直接移动！
3. 合并：重复以上步骤，直到全部完成

课堂互动游戏：

• 道具：用纸盘和三个纸杯模拟
• 挑战：3个盘子最少需要几步？（答案：7步）
• 口诀：“小的让大的，空的先帮忙，一步一步别着急！”

---

四、分治在生活中的应用

场景	如何“分治”
找单词	在字典中找“apple”：先翻到中间，看是在前面还是后面，再对半查找
拼图游戏	先拼四个角，再拼边缘，最后填中间
组织运动会	分成“跑步组”“跳绳组”“颁奖组”，每组负责自己的任务

---

五、练习：分治

练习1：数一数教室里的椅子

• 分解：先数第一排，再数第二排……
• 解决：每排有几把椅子？（直接数）
• 合并：把所有排的数字加起来！

练习2：画一棵大树

• 分解：树干 + 树枝 + 树叶
• 解决：先画树干，再画几根大树枝，最后画树叶
• 合并：组合成一棵完整的树！

---

六、分治 vs. 蛮力（对比理解）

方法	做法	适合场景
分治	先拆解，再逐个击破	复杂问题（如汉诺塔、整理图书馆）
蛮力	直接硬做，从头开始	简单问题（如数10个苹果）

✅ 分治就像用“乘法口诀”算数学题，蛮力就像“一个一个数”

---

七、总结口诀

大问题，别慌张，分成小块好解决。
小问题，很简单，解决之后拼回来。
像拼图，像分糖，分治思维真厉害！

---

板书

大问题 → 像大蛋糕
    ↓ 切一刀
中等问题 → 变成几大块
    ↓ 再切
小问题 → 变成许多小块
    ↓ 解决
每人一块 → 问题解决！

---

✨ 最终总结：一张图看懂分治

遇到大问题
    ↓
问自己：能分成几个相似的小问题吗？
    ↓
   能 → 分解 → 解决小问题 → 合并结果
    ↓
   不能 → 直接解决（可能问题本来就不大）

---