1. 贪心算法到底是什么——先弄清楚找零问题的本质很多朋友第一次听“贪心算法”这四个字第一反应是“这又是哪个竞赛选手发明的高深玩意儿”。其实你把名字拆开就明白了贪心就是每一步都贪心地选当前最好的那个选项不考虑后面会不会后悔。放在金额找零问题里意思就是要凑出某个金额时每次先拿面值最大的硬币能拿几张拿几张然后换次大的面值继续拿直到金额归零。这里关键来了为什么说“if 解题”因为贪心算法的每一次抉择本质上就是一个“条件判断”当前剩余金额够不够我拿这张大面值够就拿下不够就跳到下一档。你不用实现什么复杂的搜索、回溯也不用维护一张二维表只要根据金额大小一层一层判断就行。这恰恰是新手最容易接受的理解方式。有人可能会问这么简单的策略也能算一种“算法”是的它不但算而且是算法竞赛和工程实践中非常基础的一种思想。找零、区间调度、哈夫曼编码、最小生成树背后都有它的影子。而在教学场景里“金额找零”是公认最好的贪心入门案例因为需求直观、不需要数学前置知识代码量又少一节课就能让学生体会到“策略设计”的乐趣。我需要提前说明一点贪心算法不是万能的。它对问题的性质有要求有些找零场景它给出的是最优解有些场景它给出的只是“可行解但未必最优”。这个坑我会在第4章专门讲因为这是新手最容易误解的地方。现在你先记住一句话贪心的本质是“局部最优推导全局最优”这个推导成立是有条件的。这节内容适合谁如果你正在学习算法但被动态规划劝退过如果你准备带学生入门编程但找不到合适的教学案例或者你只是好奇“if 还能这么玩”这篇文章都能给你一个完整、可复制的方案。我会把教学台词、代码、习题、坑点全部摆出来你拿来就能用。2. 教案设计思路——为什么找零问题适合用“if 判断”做教学切入点2.1 教学目标的拆解不是教语法是教思维我在设计这节教案时首要目标不是让学生背下来“贪心算法”的定义而是让他们通过一次真实的编程练习体会到“策略选择”是如何转化为“代码逻辑”的。如果一上来就抛概念、贴伪代码学生很容易陷入“听懂了但不会写”的困境。所以我把目标拆成了三个层次第一层能用 if 语句描述“当前金额是否足够使用某面额”的判断逻辑。第二层能手动模拟贪心选择的每一步理解“从大到小逐个尝试”的合理性。第三层能识别贪心算法的适用边界知道它在某些场景下会失效。这样的目标设计有一个好处即使学生基础薄弱也能在第一个层次获得成就感而基础好的学生可以在第三层做延伸思考避免“一节课下来啥也没学到”的感觉。我建议你在实际教学中把这三点目标直接写在黑板或课件首页让学生带着目标去听课效果会好很多。2.2 为什么用“if”而不是一上来就写 while 循环我见过很多教材讲找零问题时直接上 while 循环配合取整和取余运算代码确实简洁但对新手并不友好。原因在于循环体里的“反复执行”逻辑会掩盖掉贪心策略本身。学生看代码时满脑子都是“这个循环什么时候停”反而忽略了“每次循环在做什么决策”。用 if 判断的好处是透明的。你把每一种面额单独写一个判断块代码虽然啰嗦但每一行都对应着一句人话“如果剩下的钱还够付一张100就给一张100。”这种一一映射的关系对学生来说是极大的认知减负。等他们把 if 版本跑通了、理解透了再去封装成 while 循环那就是水到渠成的事甚至你自己不讲他们也能猜出来。2.3 教学节奏安排一节课45分钟的全程拆解我在实际教学中把这一节课分成四个阶段每个阶段都有明确的时间分配和产出物情境导入5分钟抛出“假设你是收银员收到一张100元需要找零83元手头有50、20、10、5、1元面额最少给几张”这个问题。先让学生凭直觉回答再追问“你为什么先拿50而不是先拿1元”引导他们说出“先拿大的”这个朴素策略。手动模拟10分钟在黑板上或白板上手动走一遍83元的找零过程。50元拿1张剩余33元20元拿1张剩余13元10元拿1张剩余3元1元拿3张结束。每一步都在旁边标注“当前剩余金额”和“使用了哪个 if 判断”让学生看到完整的推导链路。代码实现20分钟让学生跟着敲代码。这一步我会要求他们先写 if 版本运行通过后再引导他们重构为循环版本。这两个版本我都会在这篇文章里给出完整代码和解释。总结与挑战10分钟抛出两个思考题。第一题把面额换成 [1, 5, 10, 20, 50, 100] 之外的其他组合贪心还成立吗第二题如果新增一张 7 元面额要找零 14 元贪心会给出什么答案这题留到下节课讲动态规划时用。这个节奏我测试过多次学生对前三个阶段的反馈都很好只有最后一个思考题会让不少人卡壳。但卡壳是好事它制造了认知冲突为后面的动态规划学习埋下了伏笔。3. 核心代码实现——先写 if 版本再讲循环重构3.1 最简单的 if 版代码一行判断对应一个动作下面这段代码是我上课用的第一版目的是让学生把“算法策略”和“代码结构”一一对应起来。这里我用 Python 写因为语法最接近自然语言适合新人上手。# 金额找零问题——if 版本教学用 amount 83 # 要找回的金额 coins [100, 50, 20, 10, 5, 1] # 从大到小排列的面额列表 result {} # 用一个字典记录每种面额使用了多少张 # 注意这里故意不写循环全部用 if 逐层判断 if amount 100: result[100] amount // 100 amount amount % 100 if amount 50: result[50] amount // 50 amount amount % 50 if amount 20: result[20] amount // 20 amount amount % 20 if amount 10: result[10] amount // 10 amount amount % 10 if amount 5: result[5] amount // 5 amount amount % 5 if amount 1: result[1] amount // 1 amount amount % 1 print(找零方案, result)运行结果找零方案 {50: 1, 20: 1, 10: 1, 1: 3}注意这段代码里我用了//整除和%取余这两个运算符是找零问题的灵魂。amount // 50的意思是“83 里面最多有几个 50”结果是 1amount % 50的意思是“拿走这些 50 之后还剩多少”结果是 33。每一次 if 判断其实都在回答一个问题“当前这档面额我能用几张”能用几就取几剩下零头留给下一档处理。为什么要强调 if 而不是 while因为 if 是一次性的判断判断完就往下走不回头。这恰好模拟了贪心算法的“单次决策”特性。学生如果一上来就用 while很容易在循环条件上纠结反倒忽略了“每次循环其实就是一句 if”的本质。3.2 重构为循环版本让学生看到重复代码的“压缩”过程当学生确认 if 版本的逻辑没有问题后我会引导他们观察这六个 if 块除了面额数字不同结构完全一样。这种“结构重复”是重构的绝佳信号也是理解循环抽象的好机会。# 金额找零问题——循环版本 amount 83 coins [100, 50, 20, 10, 5, 1] result {} for coin in coins: if amount coin: result[coin] amount // coin amount % coin print(找零方案, result)这段代码一行循环就把上面六个 if 块全部包揽了。引导学生一行行对比他们会发现循环版本的每一次迭代其实就是在执行原来那个“if amount coin”的判断。coin这个变量依次取列表里的每个面额代码的本质没有变只是把重复的“手工展开”变成了“自动遍历”。这一步教学的核心不是让学生记住循环怎么写而是帮助他们建立“对于重复结构用循环去压缩”的直觉。这个直觉对后续学习数组遍历、函数封装乃至递归都很有价值。我通常在课堂上让学生自己动手把 if 版本改成循环版本改完再对比运行结果是否一致这种“重构验证”体验会让他们的理解更扎实。3.3 代码讲解的“口播台词”参考手把手教你怎么说很多新老师在课堂上讲代码时容易陷入逐行翻译的陷阱比如“这一行是定义变量那一行是打印输出”。这种讲法效果很差因为学生记住的是语法碎片而不是逻辑脉络。我建议用“策略式口播”的方式来讲也就是每一行代码都和学生确认“这一步在落实什么策略”。以循环版本为例我的讲法是“同学们看这个 for 循环。for 每拿到一个面额就进入循环体循环体第一句问现在剩下的钱够不够这张面额注意这个‘够不够’用的是 if 判断。如果够我就算一算能拿几张然后把对应的张数记到 result 里同时把剩余金额更新为拿完之后剩下的零头。如果不够就直接跳过去试下一个更小的面额。大家想一下这样一轮一轮下来金额是不是一定在减小减到零的时候循环就处理完了方案也就出来了。”这段口播的重点是让学生把“amount coin”理解成“当前钱还够不够做这个选择”而不是“一个大于等于的比较表达式”。语言的力量在教学中比很多人想象的要大换一种说法学生的理解路径就会完全不一样。4. 贪心算法的适用边界——什么时候“贪心”会失灵4.1 一个反例加入 7 元面额后的找零测试贪心算法有一个天然的软肋它只做局部最优决策从不回头。这意味着它依赖一个前提——每一步的“大额优先”策略必须保证不会把后续步骤推入死胡同。遗憾的是这个前提在有些货币体系下并不成立。我上课时最常用的反例是假设一个国家发行了 1 元、5 元、7 元、10 元四种面额的硬币现在要找零 14 元。按贪心思路优先选 10 元剩余 4 元然后选 1 元 × 4总张数是 5 张。但如果换成 7 元 × 2只需要 2 张。贪心方案 5 张最优方案 2 张差距非常明显。还有另一个经典反例面额 [1, 3, 4]找零 6。贪心会先拿 4剩余 2然后拿两张 1一共 3 张。但实际上用 3 元 3 元只需 2 张。这个例子数值更小口算就能算出来特别适合课堂板书演示。4.2 如何判断一个面额体系是否适用贪心直觉与规律看到这里你可能会问那到底什么样的面额体系贪心算法才能给出最优解严格来讲这个问题有数学上的充分条件判断标准但新手阶段不需要掌握那么深的形式化方法。课堂上我会教学生一个直观判断法观察大面额是不是小面额的整数倍关系。比如人民币体系50 是 20 的 2.5 倍20 是 10 的 2 倍10 是 5 的 2 倍5 是 1 的 5 倍。整套体系虽然不完全成倍数但整体看任意大面额能覆盖若干个小面额的组合空间。这种情况下贪心策略通常不会出错。而像 1、5、7、10 这种7 和 10 之间没有整除关系也不存在“7 能被若干个更小面额完全代替”的性质贪心就容易翻车。如果学生刨根问底想知道为什么整数倍关系能保证贪心正确性我给出的解释是当小面额能整除大面额时“换成若干张小面额”不会比“直接用一张大面额”更省张数因此先拿大面额永远不会亏。一旦这个条件不成立先拿大面额就可能错过更优解就需要动态规划登场。4.3 动态规划法是什么时候才需要的——给新手的差异说明动态规划法和贪心算法的核心区别在于贪心只维护一个决策路径走完即结束速度快但可能错过全局最优动态规划会把“所有可能的决策路径”都记录下来通过状态转移方程逐步推导保证最终结果是全局最优代价是时间和空间复杂度更高。回到找零问题如果要求“绝对最优”且面额体系不满足贪心条件就该用动态规划。经典做法是定义dp[i]表示凑出金额 i 需要的最少硬币数然后用两层循环外层遍历金额内层遍历面额列表更新dp[i] min(dp[i], dp[i - coin] 1)。这段内容我在教案里只做科普性引入不要求新手当堂掌握。我的建议是先把贪心思路彻底吃透对动态规划有一个印象就行了。等你面对更复杂的优化问题时自然会有动力去系统学习动态规划。在入门阶段贪心算法配合 if 判断已经能解决掉大部分身边的实际问题。5. 新鲜教案课堂活动设计、练习与作业的完整闭环5.1 课堂互动游戏把“找零”变成计算思维训练为了让学生对贪心算法产生“肌肉记忆”我会在代码实操之外设计一个不碰电脑的互动环节。这个环节耗时短、道具简单但对理解贪心策略非常有帮助。游戏规则如下准备一叠卡片分别标记 100、50、20、10、5、1 面额数量不限。随机抽一名学生扮演收银员老师或另一位学生扮演顾客由顾客随机说出一个 1 到 100 之间的金额收银员需要在 10 秒内从卡片堆中挑出能凑出该金额的最小张数组合。计时完毕后全班一起验证组合是否成立、张数是否最少。这个游戏的巧妙之处在于它把“算法执行”从代码层面拉回到了动作层面。学生每次抽卡内心都在做一次“当前金额还够不够这张大面额”的判断这与 if 语句的逻辑完全一致。玩过几轮之后你会发现学生在写代码时明显更流畅因为他们已经在大脑里“跑”过很多次贪心流程了。5.2 分层作业设计基础题、进阶题和挑战题作业设计我坚持“分层”原则目的是让不同水平的学生都能在自己的舒适区边缘练习。基础题面向全体学生进阶题面向中等以上的学生挑战题则是给学有余力的学生准备的。基础题给定 amount 67用循环版本代码求找零方案并对比 if 版本和循环版本的输出是否一致。进阶题扩展面额列表加入 2 元面额得到 coins [100, 50, 20, 10, 5, 2, 1]分别测试 amount 为 98、73、36 时的找零方案并检查贪心策略是否依然合理。挑战题设计一组面额和金额使贪心算法给出非最优解并用自己的话解释为什么贪心会失败。这道题直接对接下节课的动态规划内容能写出正确答案的同学说明真正理解了贪心的边界。5.3 验收标准怎么判断学生真的学会了判断学生是否掌握不能只看代码能不能跑通。我总结了一套简单的验收标准供你参考能用自己的话解释“为什么先拿大面额”是合理的理解策略动机。能独立写出 if 版本和循环版本的代码掌握实现。能口算出常见金额的最优找零方案建立数感。能说出至少一个贪心算法失效的反例理解边界。如果以上四条全部满足这节课的核心目标就达成了。不要强求学生记住“贪心算法”这个名词只要他们能做出这些事名词迟早会内化。6. 常见问题与排查技巧——新手写代码最容易踩的坑6.1 面额列表没有“从大到小”排最隐蔽的坑我在课上见过最多的错误就是把 coins 列表写成[1, 5, 10, 20, 50, 100]也就是从小到大排列。这样一来代码会优先使用 1 元面额跑出来的结果虽然也能凑出金额但张数会多到离谱。比如找零 83 元如果先从 1 元开始那 result 里会有一大堆 1完全看不出贪心策略的影子。这个坑为什么隐蔽因为程序不会报错结果也能凑出正确金额只有张数不对。新手很难发现问题还以为自己写对了。我在课堂上会专门让学生做一次对比实验把 coins 顺序反着写跑同一个金额观察结果差异。这个对比能非常直观地让学生理解“面额顺序本质上决定了决策优先级”。6.2 整除和取余弄混//和%的区别总被忽略很多新手第一次接触取整和取余时会混淆两者的含义。amount // coin求的是“商”也就是能拿几张amount % coin求的是“余数”也就是拿完剩下的钱。如果你把两个运算符写反了代码要么报错要么输出完全不对的结果。我推荐一个记忆技巧//像一把刀把数切成整数份%像一个漏勺只留下漏下去的零头。上课时我会让学生分别打印83 // 20和83 % 20让他们亲眼看到一个是 4、一个是 3比口头解释一百遍都管用。6.3 金额最终不为零遗漏了最小面额 1另一种常见错误是面额列表里写了各种大面额唯独漏掉了 1 元。如果 amount 最后剩余一个无法处理的零头代码就“卡住”了——不是报错而是静默地少了几个硬币。这种情况下调试技巧是在代码运行结束后打印一下 amount看它是否归零。只要金额不是零就说明还有没覆盖到的面额。这个问题的排查思路其实可以用到更多场景任何“处理完数据后检查状态是否符合预期”的习惯都是新手应该尽早养成的。我会建议学生在找零问题里显式添加一行print(amount)来确认结果这个习惯以后排查复杂 bug 时会非常有用。6.4 找零方案的记录方式字典、列表还是直接打印有些学生喜欢在 if 判断里直接print这样做的问题在于“每次输出的结果是即时性的不容易复核”。我建议把找零方案记录到一个字典里最后统一打印。这样既能清晰地看到每种面额用了几张也方便后续写测试代码来验证结果的正确性。顺带提一句如果用列表存储方案也可以写成[50, 20, 10, 1, 1, 1]这种形式每条记录就是一张真实选中的硬币面额。字典的好处是紧凑列表的好处是贴近实际找零的“展开过程”两种风格各有千秋你选一种顺手的就行。7. 教案的延伸价值——不只是找零还能继续玩出什么花样7.1 从固定面额到动态面额体会“抽象”的力量基础教案做完后我喜欢额外布置一个开放性的小任务把代码改造成“由用户输入面额列表和金额”的版本。也就是说不把 coins 写死在代码里而是用input()接收用户输入。这是一个很好的抽象能力训练。学生会发现只要保证面额列表从大到小代码本身几乎不用改就能适用于任意货币体系。这个体验对新手理解“函数”“参数”“输入输出”都有帮助。代码大致长这样# 动态面额版本 amount int(input(请输入需要找零的金额)) coins_input input(请输入面额列表用逗号分隔必须从大到小) coins [int(x) for x in coins_input.split(,)] result {} for coin in coins: if amount coin: result[coin] amount // coin amount % coin print(找零方案, result) print(剩余未找零金额, amount)我特意在最后加了一行打印剩余金额方便学生检查是否所有金额都被成功兑换。这行小小的打印语句其实就是“程序自检”思维的雏形对后续学习非常有价值。7.2 与现实的连接收银台场景、零钱分配和日常生活有些学生会问现在都用手机支付了找零问题还有什么实际意义这个问题问得好。我通常会回应两点第一移动支付普及不意味着现金场景消失自动售货机、投币洗衣机、停车场缴费机仍然大量存在第二找零问题在本质上是一个“资源分配”问题不止硬币可以用纸钞、票券、时间片、带宽分配全都可以套用同样的策略框架。现实中最贴近的应用是自动售货机设计硬币找零模块时需要在“硬件可找零的硬币种类有限”和“顾客等待时间要短”之间做权衡。这和课程里“怎么样用最少张数找零”的目标有天壤之别但底层逻辑依然是“在有限资源下做决策”。这种迁移视角能让新手看到算法的通用性而不仅仅把它当成一道考试题。7.3 下一步学习路径从贪心走向动态规划如果学生做完了找零问题并且对“最优方案”产生了兴趣那下一站动态规划就是顺理成章的事。找零问题恰好是动态规划教材里的经典案例和 Fibonacci 数列、背包问题并列。我建议的后续学习路径是先用找零问题搞懂“递归记忆化搜索”的写法再做“自底向上的递推写法”最后把这个流程迁移到背包问题上。这样一路学下来算法思维会非常扎实。这里给你一个动态规划的参考实现供学有余力的学生课后钻研# 金额找零问题——动态规划版本求最少硬币数 def min_coins_dp(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i - coin 0: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1 coins [1, 5, 7, 10] print(min_coins_dp(coins, 14)) # 输出 2对应 7 7这段代码和贪心版本最大的不同是它不再“先选最大面额”而是对所有可能的“最后一枚硬币”做比较取最小。学生如果能亲手跑通这段代码再回去看贪心版本就能体会两种算法的哲学差异这种对照学习的效果远比单学任何一个要好。8. 我的教学复盘与个人经验最后聊点我自己的体会。这节“贪心算法 if 解题”的教案我前后调整过三四轮。第一轮的时候我直接把循环版本甩给学生结果代码跑通了但让他们解释“为什么这么写”时几乎没有学生能说明白。后来我改成“先 if 后 while”的两步走理解率明显上来了这也验证了我一直坚持的教学信念新手学算法顺序比速度重要。找零问题最大的魅力在于它足够简单简单到可以用 if 一行一行写出来但它又足够深刻深刻到能牵出贪心算法的全部核心思想以及和动态规划的第一次相遇。我建议每一位带新人的老师或者自学的新手都认真走一遍“if 版 → 循环版 → 反例思考”的完整流程不要跳过任何一个阶段。如果你在实际授课或学习过程中遇到具体问题比如代码跑不通、反例设计不出来、或者在重构环节学生卡壳欢迎在评论区留言我看到都会回复。毕竟这套教案没有完美版本只有一次次和学生真实互动之后不断打磨出来的版本。教与学本来就是一场双向优化希望这份教案能让你少走一些弯路。