高中二年级信息技术粤教版选修一“用穷举法求解问题的实践”教学设计

高中二年级信息技术粤教版选修一“用穷举法求解问题的实践”教学设计本课对应粤教版高中信息技术选修一《算法与程序设计》第四章第二节第二课时，核心落在“把问题边界说清楚，把候选对象列穷尽，把判断条件写准确，把循环次数控得住”。穷举法在教材中并非单纯讲述for循环，而是要求学生把一个现实问题转译为有限状态集合，再用重复结构逐个验证，进而体会“算得对”与“算得快”之间的张力。教学设计面向高中二年级学生，学生已经掌握顺序、分支、循环三类基本结构，能读懂Python中的range、if、变量累加与布尔表达式，但对“候选解空间”的抽象仍不稳定，常把题意中的隐含限制漏掉，或在嵌套循环里重复枚举、错误开闭区间。本课用连续的实践任务推动学生从会写一段穷举，走向能解释为什么这样穷举、凭什么停止、还能怎样少算。一、教学内容定位本节内容处在算法思想由“明白步骤”走向“评估代价”的关键节点。穷举法的价值不在“笨”，而在其可靠：当解空间有限且可判定，逐一枚举能保证不漏解；它的局限也同样清楚：规模一膨胀，时间代价迅速失控。课堂要把这种双面性摆在学生面前，让学生亲手测出n变大时运行次数的增长，而不是背诵概念。教材线索可拆成四层：问题是否能穷举，等价于候选对象是否有限、可编号、可判定；怎样穷举，等价于循环变量、区间端点、步长与嵌套维度如何设定；穷举是否正确，依赖判定条件与题意约束的一一对应；穷举是否可取，取决于复杂度估计与剪枝策略。四层之中，第一层最容易被忽视，学生常急于敲代码，把“密码由四位数字组成”写成允许前导零与不允前导零两种答案，把“鸡兔同笼”的头数脚数写成未取整的浮点比较。本课所有活动都围绕“先把数学边界钉牢，再让计算机重复劳动”展开。二、学情分析高二学生的优势是程序阅读速度快，能模仿示例完成累加、计数、条件过滤；短板是问题建模粗放，遇到“每位数字互不相同”“百钱买百鸡”“恰好用完”“不重不漏”这类约束时，容易把注意力集中在输出结果而不是生成规则。部分学生会把数学中的经验公式误当成算法，例如求1到100的和直接套用5050，却不能说明当条件变为“只统计能被3整除且个位为6的数”时该如何枚举。还有学生能写出三重循环，却说不出循环体到底执行了多少次，更无法解释为什么把内层上界从n改成i会减少重复。班级内部差异明显。编程基础好的学生容易满足于“跑出答案”，不愿写复杂度说明；基础弱的学生卡在索引边界，见到range(1,100)与range(1,101)就犹豫。教学组织采用“同一任务三档产出”：底线是能跑通并验证样例，中层是能画出候选空间表格，高层是能给出优化前后的执行次数对比。评价不奖励花哨语法，奖励可复现的解释与可检验的数据。三、教学目标学生能够判断一个具体问题是否适合穷举，说出候选集合有限、判定标准明确、单次验证代价可承受三条依据，并能举出不宜直接穷举的反例，如无限实数区间求精确零点、超大整数因数分解在无附加条件时不可贸然全试。学生能够把文字条件转化为枚举变量、取值区间、约束表达式和输出规则，做到区间端点开闭一致、整数除法与余数语义清楚、重复计数有标记。完成“三位水仙花数”“百钱百鸡”“四位回文日期”“数字密码还原”四类任务中至少三类，代码能处理边界样例。学生能够用计数器估算循环体执行次数，写出形如T≈n或T≈n²的量级判断，解释优化手段为何不改变结果只改变访问顺序，例如把a、b、c三重循环改为枚举a、b后由总量推出c并校验，或利用对称性只枚举一半。学生能够在小组中完成“问题重述—候选空间—判定条件—程序—测试用例—优化说明”六栏实验单，接受同伴质询时能用证据回答“漏没漏”“重没重”“快在哪”。四、教学重点与难点教学重点是穷举三要素的程序化表达：枚举对象、约束条件、终止规则。三者必须同时出现，缺一则穷举失去保证。课堂以“写代码前先填三栏”作为硬性门槛，任何小组未完成候选空间表不得上机运行，迫使学生把思考前置。教学难点是从“枚举所有”走向“聪明地枚举所有”。难点不在技巧本身，而在学生要承认优化前后答案集合完全一致，这需要数学论证支撑。例如鸡兔同笼中枚举鸡i从0到总头数，兔j由总头数减i得到，脚数校验2i+4j=总脚数；这里的j不是再自由枚举，而是被等式约束生成，循环维度下降但解集不变。学生必须说明这种替换的合法性，否则优化只是碰巧正确。五、教学准备机房预设Python运行环境，关闭无关网络页面，提供计时代码模板time.perf_counter()与计数器变量cnt=cnt+1的埋点方法。教师准备四张任务卡、两类数据增长曲线空白图、若干故意含错的程序片段。任务卡A为基础枚举，任务卡B为约束补全，任务卡C为降维优化，任务卡D为开放问题。板书区固定三列：左列写“候选空间”，中列写“判定条件”，右列写“次数证据”。学生任何一次发言都可被归入三列之一，形成可视化思维轨迹。多媒体不播放长演示，只在关键节点投出两组运行次数：枚举一千万次与优化后几万次的实测差异，让数字自己说话。六、教学过程环节一：用一道“眼会手不会”的题激活冲突。上课伊始给出问题：一把四位数字自行车锁，车主记得各位数字互不相同，且四位之和为14，第二位比第一位大1，问最少要试多少次保证打开。多数学生脱口说从0000到9999都试，思路安全但粗糙；有学生注意到首位不能等同处理，因为自行车锁允许0在任意位，而若改说“四位整数密码”则0008不算四位数。教师不急着评判，要求把这句话改写成候选集合：四元组(a,b,c,d)，每个分量∈{0,…,9}，a≠b≠c≠d，a+b+c+d=14，b=a+1。学生看到b被a牵制，立即发现“全枚举一万次”只是上限，真实可解空间被条件削掉大半。此处的教学动作是逼问三句话：谁在变，变到哪，凭啥留。谁在变对应循环变量；变到哪对应range端点；凭啥留对应if条件。学生把答案写进三栏后才可以打开编辑器。基础组直接枚举10000次并统计通过数；提高组先由b=a+1与和为14推出c+d=13−2a，再枚举a、c、d或进一步枚举a、c后定d。两组答案必须一致，教师只问“你们少了哪些没有可能的组合”，不夸快组，而追问快组是否证明被删组合确实不满足。环节二：从教材原型回到程序骨架。以“枚举1到n中满足性质的数”建立最小模型，板书可视化为：cnt←0；对i←1到n：若P(i)成立，则输出i，cnt←cnt+1。学生要改写成Python并保持三处可检查：range(1,n+1)体现包含n；P(i)必须布尔值明确；cnt位置在通过判断之后而非循环结束。故意展示错误片段把cnt放在if外，导致cnt恒为n，学生用n=10、P为“偶数”手算对照，立刻定位错误。随后引入运行次数感知。对n=100、10000、1000000分别只做空循环计数，让学生预测再实测。多数学生低估一百万次在现代机房仍可完成，却对一亿次嵌套失去直觉。教师给出量级直觉：单层约n次记作O(n)，两重独立循环约n²记作O(n²)，三重约n³记作O(n³)。此处不追求严格定义，只要求能用“规模乘十倍，单层约十倍，双层约百倍”做工程判断。公式以所见即所得呈现：当n由10⁴变为10⁵，双层循环次数约由10⁸涨到10¹⁰，等待从可忍变成不可忍。环节三：任务卡A“三位水仙花数”完成精确边界。题目为寻找所有三位数abc，使100a+10b+c=a³+b³+c³。学生易错点有三：把三位数枚举成range(100,1000)写成range(100,999)，漏掉999；从字符拆位时未转回整数；把立方和写成a3+b3+c3。课堂要求先写数学表达再写语句，立方统一为a3，禁止含糊。完成基础版后追加约束：不用把数拆成字符串，只能用整除与取余，迫使学生写出a=num//100，b=num//10%10，c=num%10，并说明//与/在Python中的差别。同伴互查采用“反例投递”。每组给邻组送一个应被接受或拒绝的边界值，接受样例如153，拒绝样例如100、001、999。若对方程序把001当三位数，说明枚举起点错误；若把370误判，多半是位权拆解错误。教师收集高频故障，归纳成一句可执行规则：凡谈“几位数”，先问最高位能不能为0；凡拆数字，先定用字符串还是算术；凡比较大量幂次，先防类型与优先级漂移。环节四：任务卡B“百钱百鸡”训练隐含约束。经典表述为鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一，百钱买百鸡，问翁母雏各几何。学生常见第一版是公鸡x从0到100，母鸡y从0到100，小鸡z从0到100，三重循环后判断x+y+z=100且5x+3y+z/3=100。这个版本能跑但粗劣：z/3带来浮点，z未限定可被3整除，购买数量还隐含钱不能为负。修订路径分两步：先保持三重枚举但改成3(5x+3y)+z=300，避免小数；再由x+y+z=100推出z=100−x−y，只枚举x与y，并加z≥0且z%3==0。关键问答落在“z消失是不是少查了”。学生需证明：在x、y确定且总数固定为100时，z唯一确定；若z为负或非三的倍数则该(x,y)不可行；所有可行三元组都能被某个(x,y)生成。教师板书对应关系：原空间大小约101³≈1.03×10⁶，降维后约101²≈1.02×10⁴，再叠加x≤20、y≤33的钱数上界，实际更少。学生亲眼看见“数学约束先于循环剪枝”，这比空洞强调效率更有说服力。环节五：任务卡C“不超时的回文日期”引出范围设计与表示差异。给出任务：统计2000年至2099年中形如ABCDDCBA的八位日期是否真实存在，先不直接写程序，要求学生列候选方案。方案一枚举每一天，从20000101到20991231，转为字符串判断是否回文再校验日期，约三万余次，稳而慢。方案二枚举前四位ABCD，反推后四位DCBA，再拼成月日校验，候选仅一万个，且其中大量不合法。方案三直接枚举合法月日：年可由回文倒推，月只有01到12，日受月与闰年限制，候选缩到366以内，且每年若存在则回文日期唯一与否可做讨论。此环节价值不在结论，而在让学生比较三种“同样正确”的枚举对象：日期对象、数字串对象、月日对象。选择不同对象，程序长度、可证性、速度全改。教师强调工程判断顺序：先选最能贴近问题本体的对象，再让语言去迁就它；若本体是日期，就不要沉迷字符串技巧；若本体是对称数字，则对称性应进入生成规则而非事后过滤。学生把方案三写成闰年表days={1:31,2:28,…}，二月按(y%4==0andy%100!=0)ory%400==0修正，输出YYYYMMDD格式。环节六：错误诊疗室。屏幕展示四段有代表性的病码：区间少一，条件与题意错位，重复计数，优化后漏解。学生不直接改代码，先写“病灶处方”：这段代码把哪一类候选漏了或重了，用哪个输入能当场抓住。比如数字互不相同的条件写成a!=bandb!=c，漏掉a!=c；比如回文判断用int(s)==int(s[::1])会把前导零差异吞掉；比如把嵌套循环上界改成i+1却没说明为何对称，导致只查一半。每组完成一张处方后交换执行，班上集中标注“最阴险错误奖”，奖励发现最隐蔽语义偏差的小组。诊疗环节特别强调测试先行的习惯。穷举看似机械，实际上测试样例要覆盖最小界、最大界、临界整除、全不合法、恰好一个解、多个解六类。学生为水仙花数设计n=99无输出、n=100起出现153，为百鸡设计钱数改为99时无可行或可行集合变化，为回文日期设计闰年20000229与平年1900229对照。样例不是附属品，是对候选空间是否画对的探针。环节七：小组实战“运动会检录号”。开放情境为：学校用三位编号给运动员检录，编号从100到999，要求个位是奇数，十位数字大于百位数字，三位数字和为12，且同一个号码不会被两名运动员重复使用。学生需输出所有号码并按百位升序，给出总数，说明若不限制“三位数字和为12”，枚举次数由多少变为多少。基础要求完成正确程序；进阶要求不用三重循环拆位直接枚举整数；挑战要求估计若编号扩展为六位、约束同类，直接枚举是否仍现实，并给出一种生成式思路。组内角色固定为建模员、编码员、测试员、说明员，四人都须能接替邻役解释。建模员负责把口语条件改成集合语言；编码员保证变量名表达含义，不用m、n、kk无意义符号；测试员维护用例表；说明员在路演中接受班级提问。教师巡视只问三类问题：这个变量还有没有别的可能值，这个if删掉会多输出谁，这个循环提前结束会不会少一个答案。此类问题把注意拉回穷举本质，而非界面与技巧。环节八：展示与anti展示。各组投屏不念代码，先报候选空间大小、实测循环次数、解的数量、最危险测试样例。随后进行anti展示，即要求另一组当场给出一个让程序露怯的新输入。若某组把个位奇数写成num%10==1，只认1而漏3、5、7、9，立即暴露；若把十位大于百位写成b>=a，边界混入相等，反例112在和不满足时需另造215类；若排序依赖默认输出而不是显式sorted，说明员要承认枚举顺序本身已保证还是偶然保证。课堂气氛允许紧张，但不允许以“反正能跑”结束。环节九：归纳成可迁移的穷举工作流。师生共同沉淀为六步：复述题意至无异议；定义元组与每分量域；写出必须同时成立的条件；确定枚举顺序并标明区间；加计数与测试；评估规模并做不改动解集的化简。每一步都对应一句自检：域有限吗，条件等价吗，端点对齐吗，重复会吗，次数估吗，优化守恒吗。学生把这张卡片贴进实验册，后续学习回溯、二分、贪心时都回看它，理解穷举是许多高级算法的最朴素底座。七、板书设计主板书中间写课题“用穷举法求解问题的实践”，左侧竖排三词：枚举、判定、守恒。中央流程写成：现实对象→候选元组→约束条件→循环结构→测试证据→次数估计。右侧放两列对比：百钱百鸡原始约101³次，降维约101²次；回文日期按日约3×10⁴次，按月日约366次。底部留一条“易错带”：前导零、range开闭、浮点等值、隐含的整除、重复计数、优化漏证。整板不出现长句，全部服务于学生抬头即可复述。八、作业设计基础作业为完成“四位平方数”检索：找出所有四位数abcd，使其本身是平方数，且前两位组成的数与后两位组成的数之差为7。要求提交程序、三栏表、五条测试。评价看能否正确处理1000到9999、平方根范围32到99、差值有正负两种解读时如何依据题意取舍。提升作业为分析“完美数与盈数”：枚举1到10000，计算真因子和，分类deficient、perfect、abundant。禁止直接调用现成函数，要求用ii<=n控制因子枚举到平方根并补成对因子，使单层约√n而非n。学生要解释为什么枚举到√n不重不漏，以及1这个特殊因子如何处理。挑战作业为“自助找零的整除约束”：面额为1、2、5、10的纸币，给总额S=50，求用不超过18张纸币凑出S的方案数，要求张数最少方案排在前面。学生可枚举四种张数但要用方程消元降到三重以内，且说明为什么从小到大面值枚举不等于张数最少，输出排序键必