高中二年级信息技术教学设计：贪心算法的策略建构与实践应用

高中二年级信息技术教学设计：贪心算法的策略建构与实践应用一、教材分析本课选自浙教版高中信息技术选择性必修一《数据与数据结构》第二章第二节，是算法思想模块中继枚举、递推之后的重要专题。贪心算法的核心在于每一步都做出当前看来最优的选择，期望通过局部最优的累积达到全局最优。教材以找零问题、活动安排问题为线索，呈现了贪心策略"选择—验证—迭代"的基本范式。与此前学习的枚举法相比，贪心算法在效率上有质的跃升，但它并不保证所有问题都能得到最优解，这一"不完美性"恰恰是本课最具教学价值的生长点。学生在学习本课之前，已经掌握Python基本语法、列表操作与简单排序，具备将算法思想转化为代码的基础能力。本课承担着承上启下的功能：向上承接问题解决的一般过程，向下为动态规划的学习埋下认知冲突的伏笔。二、学情分析授课对象为高二年级学生。经过必修模块的学习，学生能够编写基础程序，对"算法效率"有初步体感，但思维方式仍偏向"穷举一切可能"的朴素路径。日常经验中，学生其实早已在使用贪心思维——排队打饭选最短的队伍、购物凑单先用大额优惠券——只是从未将其抽象为可陈述、可迁移的算法策略。学生的困难集中在三点：其一，难以从具体问题中提炼"贪心选择标准"；其二，默认"局部最优必然导致全局最优"，缺乏反例意识；其三，将策略转化为代码时，对排序、迭代的组织方式不够熟练。基于此，本课采用"情境冲突—策略提炼—代码实现—反例证伪—边界辨析"的递进路径，让学生在亲历策略失效的过程中建立对贪心算法的完整认识。三、教学目标信息意识方面：学生能够从找零、活动安排等真实问题中抽象出数据特征，识别其中蕴含的优化需求，体会算法策略与现实决策的深层关联。计算思维方面：学生能够归纳贪心算法"确定贪心策略—按策略选择—迭代求解"的一般步骤，能用自然语言与流程图描述算法过程；能够构造反例判断贪心策略的适用边界，经历"提出猜想—验证—修正"的完整思维过程。数字化学习与创新方面：学生能够用Python实现找零问题与活动安排问题，通过对比贪心算法与枚举法的运行规模，量化感知算法效率的差异。信息社会责任方面：学生能够认识到"看似聪明的选择未必总是正确"，在算法选择中养成严谨求证的态度，理解推荐系统等现实应用中贪心策略可能带来的偏差。四、教学重点与难点教学重点：贪心算法的基本思想与求解步骤；用Python实现典型贪心动问题。教学难点：贪心策略的选择依据；判断贪心算法能否得到最优解的验证意识。五、教学方法与准备采用情境教学法、任务驱动法与对比实验法。课前准备：网络机房、Python运行环境、导学单、模拟钱币卡片、"活动安排"数据表、在线评测小工具。课时安排为两课时连排，共90分钟。六、教学过程环节一：情境导入——收银员的速度之争（8分钟）上课伊始，教师播放一段超市收银的短视频：顾客应付67元，递出100元，收银员需要找零33元。视频中两位收银员，一位几乎是下意识地抽出一张20元、一张10元、一张5元、两张1元；另一位则迟疑翻找。教师提问：第一位收银员为什么不用思考？他是怎么做到"又快又对"的？学生讨论后发现，人的直觉做法是"先拿最大的，不超过剩余金额就行"。教师在黑板上板书这一过程：33→选20，余13→选10，余3→选5不行，选2元（可用两张1元表述），逐步归零。教师追问：这种"每次都拿当前能拿的最大面值"的做法，隐含了一种怎样的决策规则？如果把它交给计算机执行，需要哪些步骤？学生初步口述：从大到小排序→依次尝试→够减就减，直到为零。教师顺势揭示课题：这就是今天要研究的一种经典算法策略——贪心算法。设计意图：从学生熟悉的生活场景切入，让"贪心"这一抽象概念附着于具体经验之上，降低认知门槛。同时"快"与"对"的双重评价维度，为后续探讨效率与正确性埋下引线。环节二：抽象建模——贪心算法的思想提炼（12分钟）教师引导小组完成找零问题的形式化描述：给定面值集合{20，10，5，1}，求组成金额n所需的最少张数。各小组在导学单上填写三要素：问题的目标是什么（张数最少）、每一步可以选择什么（选一张某种面值）、选择的依据是什么（不超过剩余金额的最大面值）。教师汇总并给出贪心算法的定义性表述：在求解问题时，每一步都做出当前状态下的最优选择，不回溯、不反悔，希望通过一系列局部最优选择得到全局最优解。其一般框架为：第一步，确定贪心选择标准；第二步，按标准对数据进行排序或组织；第三步，依次做出选择并更新问题状态；第四步，重复直至问题求解完毕。教师强调"贪心"一词的双刃剑含义：它既是"抓住眼前最优"的策略描述，也暗示着这种策略可能"因小失大"。设计意图：让学生亲历从具体问题到抽象模型的提炼过程，三要素导学单为学生提供了可操作的思维支架，避免定义的枯燥灌输。环节三：编程实现——让贪心策略落地（15分钟）学生在导学单的半成品代码基础上补全找零程序。核心代码如下：coins=[20,10,5,1]defchange(n):count=0forcincoins:whilen>=c:n=nccount=count+1returncount学生输入不同金额测试：33、57、100，程序均快速给出结果。教师选取两个学生的实现进行投屏讲评，重点辨析两处细节：一是为什么面值列表必须从大到小排列，二是用count=count+n//c与n=n%c的改进写法如何减少循环次数，体会代码层面的进一步优化。随后布置即时练习：学校的会议室一天内有若干社团申请使用，每个社团给出使用起止时间，如何安排才能让当天举办的社团活动场次最多？学生先不编程，只在数据表上用笔画出选择过程，归纳贪心标准——每次选择"结束时间最早且与已选活动不冲突"的活动。学生尝试编程，核心逻辑为按结束时间排序后扫描：acts=sorted(acts,key=lambdax:x[1])end=0num=0forainacts:ifa[0]>=end:num=num+1end=a[1]设计意图：先实现一个"必然正确"的贪心案例建立信心，再借活动安排问题训练"从排序到扫描"的贪心代码范式"。半成品代码与手写推演相结合，兼顾不同层次学生的节奏。环节四：认知冲突——贪心永远是对的吗（15分钟）教师抛出新情境：某国货币面值为1元、5元、8元，需凑出11元。学生沿用刚才的策略：先选8，余3，再选三张1，共4张。教师请学生检查：还有没有更优的方案？很快有人发现：5+5+1只用3张。教室里出现了短时间的安静——刚才"又快又对"的策略，在这里失效了。教师组织学生分组讨论：为什么同样的策略，在面值{20,10,5,1}上正确，在{8,5,1}上失败？引导学生发现：后者中，"眼前最优"的8元挤占了本可以由两个5元更灵活组合的空间，局部最优破坏了全局最优。教师由此明确贪心算法的关键性质：贪心策略只对满足特定条件的问题有效，使用时必须验证其正确性，常见方法包括数学证明或构造反例尝试推翻。教师补充介绍：对于找零问题失效的情形，需要借助后续将要学习的动态规划才能稳定求解最优解，本课先建立这一认知接口。课堂小实验：学生用程序对比面值{8,5,1}下贪心结果与枚举结果，亲眼看到11元时贪心输出4、枚举输出3，用数据固化认知冲突。设计意图：此环节是本课的灵魂。通过精心设计的反例制造认知失衡，让学生从"会用贪心"跃升为"会判断何时能用贪心"，培养严谨求证的科学态度，这正是计算思维的高阶表现。环节五：对比深化——算法效率的量化体验（12分钟）教师布置对比任务：分别用枚举法和贪心法求解"01背包的近似版本"——有n件物品，每件有重量与价值，背包限重W，枚举所有组合求最优，贪心按"单位重量价值最大"依次装入。当n较小时两者都瞬时完成；教师将n调至25，枚举程序明显卡顿，贪心程序依然瞬间响应。教师引导学生估算枚举法的规模：n件物品，每件只有装与不装两种状态，组合总数为2的n次方，n=25时约三千多万种，n=40时突破一万亿。学生记录对比数据并填写结论：贪心算法以线性或接近线性的代价换取解的速度，枚举以指数级代价换取解的保证。教师总结算法选择的三问：问题规模多大？答案必须最优吗？贪心策略是否经受住了反例检验？设计意图：通过可感知的运行对比，把抽象的"时间复杂度"转化为学生的真实体验，同时渗透"没有万能算法，只有合适的算法"的工程思维。环节六：迁移应用——分层任务挑战（15分钟）基础层任务：完成"分发饼干"问题——若干孩子胃口不同、饼干尺寸不同，一块饼干最多满足一个孩子，求最多能满足多少孩子。学生独立确定贪心标准（先满足胃口最小的孩子）并编程实现。提高层任务：参加区间覆盖问题——数轴上给定目标区间和若干小区间，求覆盖目标区间所需的最少区间数。小组协作完成，要求先写出贪心策略的伪代码并互相审查反例，再动手编程。挑战层任务：为校运动会设计"最短等候时间"的检录排序方案，思考按什么标准排队能让所有运动员的平均等待时间最短，并说明理由。教师巡视指导，重点关注学生是否先陈述策略再写代码。对提前完成的小组，要求其向其他组讲解自己的贪心标准并接受"反例质询"，扮演"算法评审员"。设计意图：三层任务覆盖不同能力水平，"先策略、后代码"的流程要求强化本节的方法论主线，"反例质询"机制把环节四形成的验证意识迁移到新情境。环节七：总结提炼与评价（8分钟）师生共同梳理本课知识脉络，完成思维导图：贪心算法的定义→求解四步骤→典型应用（找零、活动安排、分发饼干）→适用条件与反例→与枚举法的效率对比。学生完成课堂自评表，从"我能说清贪心策略""我能判断贪心是否适用""我能独立编程实现"三个维度打星，并写下一条仍未解决的疑问贴到班级问题墙。教师收集典型疑问，预告下一课动态规划将从"贪心失效的地方"讲起。设计意图：总结不止于知识罗列，更在于暴露遗留问题，让课堂的终点成为下一课的起点。七、作业设计基础性作业：完成导学单上活动安排问题的完整代码与三组测试数据截图。实践性作业：观察家庭或校园生活中一个"每次挑当前最好"的决策场景（如零钱搭配、自助餐取餐、行李装箱），用文字说明其贪心标准，并尝试构造一个它会失败的例子，下节课分享。八、板书设计主板书分三栏：左栏为课题与定义——"每一步取当前最优"；中栏为求解四步骤与找零问题的推演过程；右栏为警示区，记录{8,5,1}反例与"先验