高中信息技术选择性必修一2-2贪心算法教学设计方案

高中信息技术选择性必修一22贪心算法教学设计方案一、教材分析本课选自浙教版高中信息技术选择性必修一《数据与数据结构》第二章第二节，是学习算法与算法实现模块中极具思想价值的一课。贪心算法既是枚举算法、递推算法之后学生接触的第一种具有明确策略思想的算法，也是后续动态规划、回溯算法学习的重要铺垫。教材以零钱兑换、活动安排等经典问题为线索，引导学生理解“每一步都做出当前看来最优的选择，从而希望得到全局最优解”这一核心思想，并通过对比分析认识贪心选择并不总能获得最优解，培养学生的批判性思维。本节内容在知识体系中处于承上启下的位置。向前看，学生已经掌握了Python基础语法、列表等数据结构以及枚举算法的基本实现方法，具备了编写一定规模程序的能力；向后看，贪心思想中的“问题分解”与“最优子结构”意识，将直接影响学生对动态规划等高级算法的理解深度。因此，本课不能只停留在教会学生套用模板解决经典问题的层面，而应当引导学生经历“发现问题、提出策略、验证策略、反思策略”的完整思维过程。二、学情分析授课对象为高二选修信息技术的学生。从知识基础看，学生已经完成了必修一的学习，能够熟练使用Python基本语句、循环与选择结构，掌握了列表的操作方法，具备将简单算法思路转化为代码的能力。从思维特点看，高二学生抽象逻辑思维日趋成熟，但面对算法策略性问题时，仍存在两个典型障碍：一是容易满足于“看起来正确”的局部策略，缺乏验证意识；二是对“为什么贪心策略在这个问题中有效”的论证感到困难，往往只能举例说明，不能进行逻辑推断。从生活经验看，学生对找零钱、排队、安排日程等场景并不陌生，贪心选择其实是他们日常生活中的一种直觉行为。这种直觉既是教学的宝贵起点，也是教学中需要警惕的陷阱——直觉的正确性需要理性检验。本课正是要利用这种生活直觉与算法严谨性之间的张力，制造认知冲突，推动学生思维向深处发展。三、教学目标1.理解贪心算法的基本思想：在解决问题的过程中，每一步都做出当前状态下的最优选择，以期得到问题的整体最优解。2.能够识别适合贪心策略的问题，掌握贪心算法解决问题的一般流程：分析问题结构、确定贪心策略、验证策略有效性、编码实现。3.通过编程实现零钱兑换和活动安排问题，提升抽象建模与代码实现能力，在调试与对比实验中发展计算思维。4.通过“贪心策略失效”案例的探究，认识算法选择需要严谨论证，养成大胆猜想、小心求证的科学态度，体会算法设计中策略权衡的辩证观。四、教学重难点教学重点：贪心算法的基本思想；运用贪心策略编程解决典型问题。教学难点：判断一个问题是否能够运用贪心策略求得最优解；理解贪心策略有效性背后的最优子结构与贪心选择性质。五、教法与学法本课采用情境教学、任务驱动与对比探究相结合的方法。教师创设贴近生活的问题情境，组织“提出策略—编程验证—反例冲击—修正认识”的探究主线；学生以小组协作的方式完成任务单，经历从直觉猜想到程序验证再到逻辑思辨的完整过程。教学环境为计算机网络教室，每学期安装Python3.10及以上版本与常用编辑器，电子教室系统支持作品广播与屏幕分享。六、教学准备教师准备：教学课件、任务探究单、半成品代码框架、零钱兑换与活动安排的测试数据集、课堂即时评价量表。学生准备：复习列表排序、循环遍历相关代码，预习教材第2章第2节内容。七、教学过程（一）情境导入：一次“聪明”的付款（约6分钟）上课伊始，教师呈现这样一个场景：小周去超市付款，收银员需要找给顾客81元零钱。柜台里有面值为100元、50元、20元、10元、5元、1元的纸币若干，收银员希望给出的纸币张数最少，他该怎么做？学生很快给出答案：先找一张50元，再看剩下的31元，先找一张20元，剩下11元，再找一张10元，剩下1元，再找一张1元，共4张纸币。教师追问：你为什么先拿50元，而不是先拿两张20元？学生回答：先拿大的，拿得最快，钱数凑得最快。教师顺势在黑板上画出决策链条：每一步，人们都本能地选择“当前最有利”的那张纸币，并不提前考虑后面几步会怎样，但结果却是最优的。教师点题：这种“每步都选当前最优，期望得到整体最优”的策略，就是今天要研究的贪心算法。教师板书课题，明确本课的核心任务：什么时候可以贪心，怎样贪心，贪心失败时怎么办。设计意图：用学生极为熟悉的找零场景切入，让“贪心策略”直接对接生活直觉，降低抽象概念的理解门槛；追问“为什么先拿50元”，引导学生在无意识的选择行为中觉察策略的存在，为接下来精确表述算法思想埋下伏笔。（二）概念建构：贪心算法的思想与流程（约8分钟）教师引导学生将刚才的找零过程形式化。首先明确：贪心算法在求解问题时，把问题的求解过程看作一个决策序列，每一步都在可选方案中，依据某个贪婪准则做出局部最优选择，做出选择后不再改变，逐步构造出问题的解。教师结合找零过程讲解贪心算法的三个关键要素。其一，贪心准则，即每一步选择的依据，找零问题中的准则是“不超过剩余金额的最大面值”。其二，可行性约束，每一步选择必须满足问题条件，不能超支。其三，不可撤销性，做出的选择不回退、不调整，这与后续要学的回溯法形成本质区别。师生共同归纳贪心算法解题的一般流程：第一步，分析问题，建立数学模型；第二步，选择贪心准则；第三步，按准则逐步做出局部最优选择，构造解；第四步，检验所得解是否确为最优。教师特别强调第四步的存在——贪心算法的特殊性恰恰在于，策略的有效性必须先质疑、后确认。设计意图：从具体过程抽象出算法思想，符合“从特殊到一般”的认识规律。在总结流程时突出“检验有效性”这一步骤，为后面的认知冲突预设接口，避免学生形成“贪心一定能够最优”的错误定势。（三）任务一：编程实现找零问题（约10分钟）学生打开教师下发的半成品代码框架，完成找零问题的编程实现。核心代码由学生补全，教师屏幕巡视，重点指导。任务要求：面值数组coins=[100,50,20,10,5,1]（已按从大到小排列），输入找零金额n，输出各种面值的张数与总张数。学生完成后，教师广播典型代码：defchange(n):coins=[100,50,20,10,5,1]count=0forcincoins:num=n//cifnum>0:print(c,"元:",num,"张")count+=numn=numcreturncount教师请两位学生讲解代码逻辑，重点理解取整除得张数、更新剩余金额这两行。随后用多组数据测试：n=81时输出4张，n=66时输出4张……学生发现，对于现行人民币面值体系，贪心策略始终给出最少张数。教师此时埋下伏笔：是不是所有的面值体系都能这么幸运？请同学们保留这份代码，我们马上回来改造它。设计意图：让学生亲手把生活策略翻译成代码，完成第一次“直觉—代码”的映射。半成品框架降低语法负担，保证课堂重心落在算法逻辑上；保留代码、预告改造的环节设置悬念，维持探究的延续性。（四）认知冲突：贪心策略的失效（约12分钟）教师呈现一个新情境：某虚构国家的货币面值只有1元、5元、11元三种。现在需要找零15元，用刚才的贪心程序会得到什么结果？学生在代码中将coins改为[11,5,1]，输入15，程序输出：11元1张，1元4张，共5张。教师追问：这是最优解吗？学生动手试算后发现，3张5元也是15元，只需3张，比贪心结果更优。教室里出现明显的惊讶反应——第一步选择11元是“当前最有利”的，却因为占用了太大金额，导致后续只能用1元凑，反而整体变差。教师组织学生讨论：贪心策略为什么在这里失效？师生达成共识：贪心算法每一步只看眼前，没有全局视角。一个策略能否追求到全局最优，取决于问题本身是否具备某种良好性质——局部最优选择不会破坏后续的选择余地，即问题具有贪心选择性质与最优子结构。人民币面值体系经过精心设计，恰好满足这一性质；而1、5、11的体系不满足。教师进一步引导学生比较：如果我们坚持要正确解，1、5、11体系找15元怎么办？学生提出枚举所有组合。教师指出，这正是后续动态规划擅长解决的问题。贪心算法用自己的简单高效换来了适用范围的限制，算法选择本质上是一种权衡。设计意图：这是本课的关键环节。通过同一套代码在新数据上的“失败”，人为制造强烈的认知冲突，让学生切身体验“直觉可能出错、验证必不可少”。由失效反推有效条件，学生对贪心算法适用性的理解由记忆性的结论上升为有依据的判断。（五）任务二：活动安排问题（约12分钟）教师提出新问题：学校报告厅一天内收到如下活动的借用申请，每个活动有开始时间与结束时间，报告厅同一时刻只能安排一个活动。怎样安排，才能使报告厅承办的活动数量最多？教师给出数据（序号：开始—结束）：1号8:00—10:00、2号9:00—11:00、3号10:00—12:00、4号11:00—13:00、5号8:30—9:30、6号12:00—14:00。学生小组讨论贪心准则。课堂上通常会出现三种主张：选最早开始的、选历时最短的、选最早结束的。教师不急于表态，让学生用给定数据逐一手工验证。验证结果：按最早开始选，选中1号之后只能再选4号、6号，共3个；按历时最短选可能出现与多数活动冲突的情况；按最早结束选，依次选中5号（9:30结束）、1号（8:00开始不行，10:00结束？此处学生发现1号开始时间早于9:30不可选）、3号、6号，最终可安排5号、3号、6号共3个，更换数据后可明显体现最早结束策略的最优性。教师调度各组扩大数据集继续比较，学生确认“按结束时间最早优先”是可行的贪心准则。学生依据准则编程实现，核心步骤为：将活动按结束时间升序排序；选入第一个活动；依次检查其余活动，若其开始时间不早于上一个入选活动的结束时间，则选入。参考实现：acts=[(8,10),(9,11),(10,12),(11,13),(8.5,9.5),(12,14)]acts.sort(key=lambdax:x[1])chosen=[acts[0]]forainacts[1:]:ifa[0]>=chosen[1][1]:chosen.append(a)print("共安排",len(chosen),"个活动：",chosen)学生运行并换用更大规模的随机数据测试，统计安排数量。教师组织学生小结两个问题在算法结构上的共性：都需要先确定度量标准的排序（面值大小、结束时间先后），都在一个遍历过程中做出不回头的选择。设计意图：活动安排问题比找零问题前进了一步——贪心准则不是题目明示的，而是需要提出和甄别的。让学生经历“多方案竞争—数据验证—确认准则”的过程，体现算法思维的严谨性；排序与遍历的代码结构，直击贪心算法的典型实现模式。（六）课堂小结与升华（约4分钟）教师引导学生从三个层面回顾本课。思想层面：贪心算法每步做当前最优选择、选择后不回头，简单而高效。方法层面：贪心解题的关键在于准则的确定与有效性的验证，直觉可以提出策略，只有论证与测试才能确认策略。价值层面：人民币面值体系的精心设计让贪心策略可靠，说明了数学设计与工程标准的力量；而1、5、11面值的反例提醒人们，面对任何“显然正确”的捷径，都应当保持求证的习惯。教师布置分层作业。基础作业：完成教材课后练习，用贪心算法求解“区间覆盖点”问题。拓展作业：探究01背包问题中“按单位重量价值优先”的贪心策略为何失效，并用一组反例数据加以说明，为下一节动态规划的学习做铺垫。设计意图：小结不止于知识罗列，而是沿“思想—方法—价值”三个维度收束，回应课标对学科核心素养的要求。分层作业中的背包问题探究，为前后知识建立连接，使贪心算法的适用边界问题在课后继续发酵。八、板书设计主板书：贪心算法——每步选当前最优，选择不回头。核心流程：建模→定准则→逐步选择→检验有效性。典型案例：找零（面值由大到小）、活动安排（按结束时间排序）。警示：贪心准则必须经过验证（反例：1、5、11找15元）。九、教学评价设计本课评价采用过程性评价与结果性评价结合的方式。过程性评价依托任务单完成度、小组讨论发言质量、代码调试过程记录展开，教师随堂填写观察记录；结果性评价以两个编程任务的运行结果与测试数据表现为依据。评价标准突出三个区分度：能正确实现算法但说不清准则的，为中等等级；能解释准则并能举出反例的，为良好等级；能主动讨论准则有效性条件、并将贪心与枚举、动态规划做横向比较的，为优秀等级。即时评价采用电子教室投票功能，在认知冲突环节收集学生对“贪