python详解分治算法

课堂笔记分治算法——像“分蛋糕”一样解决问题--彭彭老师一、什么是分治一句话概括“大事化小小事化了”——把大问题拆成小问题逐个解决再合并结果生活中的例子分蛋糕一个大蛋糕太难切先切成小块再分给每个人整理书包书本太多太乱先分类语文、数学、英语再分别整理大扫除教室太大打扫不完分组负责不同区域最后汇总二、分治的三步魔法第一步分解把一个大问题拆成几个相似的小问题✅ 例如把“整理全班同学的作业”拆成“整理第一组、第二组……的作业”第二步解决解决最简单的小问题通常是“不用再拆”的时候✅ 例如整理一个同学的作业直接放进书包第三步合并把小问题的答案组合成大问题的答案✅ 例如把每个小组整理好的作业收齐就是全班的作业三、经典例子汉诺塔可视化游戏游戏规则3根柱子A、B、C从小到大的一叠圆盘在A柱上目标把所有圆盘移到C柱规则①一次只能移动一个圆盘②大盘不能压在小盘上分治解法分解把“移动N个盘子”拆成把上面(N-1)个盘子移到B柱临时存放把最大的盘子移到C柱把(N-1)个盘子从B柱移到C柱解决当只剩1个盘子时直接移动合并重复以上步骤直到全部完成课堂互动游戏道具用纸盘和三个纸杯模拟挑战3个盘子最少需要几步答案7步口诀“小的让大的空的先帮忙一步一步别着急”四、分治在生活中的应用场景如何“分治”找单词在字典中找“apple”先翻到中间看是在前面还是后面再对半查找拼图游戏先拼四个角再拼边缘最后填中间组织运动会分成“跑步组”“跳绳组”“颁奖组”每组负责自己的任务五、练习分治练习1数一数教室里的椅子分解先数第一排再数第二排……解决每排有几把椅子直接数合并把所有排的数字加起来练习2画一棵大树分解树干 树枝 树叶解决先画树干再画几根大树枝最后画树叶合并组合成一棵完整的树六、分治 vs. 蛮力对比理解方法做法适合场景分治先拆解再逐个击破复杂问题如汉诺塔、整理图书馆蛮力直接硬做从头开始简单问题如数10个苹果✅分治就像用“乘法口诀”算数学题蛮力就像“一个一个数”七、总结口诀大问题别慌张分成小块好解决。 小问题很简单解决之后拼回来。 像拼图像分糖分治思维真厉害板书大问题 → 像大蛋糕 ↓ 切一刀 中等问题 → 变成几大块 ↓ 再切 小问题 → 变成许多小块 ↓ 解决 每人一块 → 问题解决✨最终总结一张图看懂分治遇到大问题 ↓ 问自己能分成几个相似的小问题吗 ↓ 能 → 分解 → 解决小问题 → 合并结果 ↓ 不能 → 直接解决可能问题本来就不大