《枚举法与算法的优化》教学设计

宋巍巍 任静 曹恒来

● 学习内容分析

作为一种常用算法，枚举法在生活中比较常见，如在一串钥匙中找到正确的一把开门，最直接的办法就是一把一把地去试，直到试出正确的一把。在计算机科学中，使用枚举法解决问题则是利用计算机运算速度快的特点，一一列举问题的所有可能答案，逐个验证，把符合条件的答案保留下来，它是对现实生活中解决问题方法的一种“直译”，因此比较直观、易于理解。但是枚举法需要对所有可能的答案一一列举，如果枚举的范围很大，运算量将会很大，所耗的时间就比较多，那么，如何改进算法，提高解决问题的效率就成了本节课的难点。

2018版的苏科版八年级信息技术教材，将《算法实例》移至了《程序设计语言》之前，仅通过流程图来描述和实现算法。在实际的教学过程中，笔者仍然把这部分内容移至《程序中的循环》之后，让学生用Visual Basic语言来描述算法，经历用计算机编程解决问题的过程，以帮助他们较为深刻地体验和理解算法。

● 学习者分析

本课的学习对象是八年级下学期的学生，与七年级学生相比，他们的逻辑思维能力有了较大的提高，能运用数学公式构建出解决问题的模型。在前面的学习中学生已经掌握了算法的三种基本控制结构，并能够在Visual Basic环境中编写程序解决生活中的一些简单问题，但对算法和算法效率的认识还不够，很少能意识到算法对程序的重要性。在学习风格上，八年级的学生喜欢动手实践，迫切希望能在计算机中验证解决问题的算法。

● 学习目标

①了解枚举法的概念，知道枚举法的优缺点，了解常用的枚举法优化策略，如缩小枚举范围、减少循环层数等。②通过解决多个个例问题归纳出枚举法的一般模式。③感受问题解决方案的多样性，在解决问题的过程中，能有意识地寻求优化的解决方案，形成高效解决问题的习惯。

● 教学过程

1.创设情境，引入枚举法

速算24点：从1～9中任选四个数字（数字可以有重复），快速计算这四个数字的和是否刚好是24。

（1）你能否一个不落地找出所有的数字组合？（将4个数字分别从1到9逐个尝试）

（2）请打开“试算24点”程序找出几组和为24的数字，感受一下手动逐个尝试方式的速度。（比较慢）

（3）这种逐个尝试工作可以由计算机自动完成，运行如上页图1所示程序，观察运行结果。

小结：这种一一列举问题的所有可能答案并进行检验，找出符合要求的答案的方法就是枚举法。

设计意图：学生比较熟悉算24点游戏，为方便后面学生模仿程序，这里将游戏简化为只做加法运算。通过口头试算将学生引向枚举法的思想，再通过程序手动试算24点，使学生对一一列举有更直观的体验，在此基础上再给出枚举法的范例代码并运行程序，帮助学生形成对枚举法的初步认识，并感受利用计算机高速运算解决问题的优越性。

2.模仿尝试，体验枚举法

活动1：模仿上例，分别完善程序，用枚举法解决3个问题。

（1）所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数本身，如153=13+53+33。求所有的水仙花数（如图2）。

（2）一张单据上有一个五位数的编码（如图3），但一位粗心的会计将千位数和百位数弄模糊了，只记得这个五位数是57或67的倍数，求单据上所有可能的号码（如图4）。

（3）有些数可以被它自己各位数字之和整除，如18，1+8=9，18可以被9整除，找出具有此特性的所有三位数（如下页图5）。

设计意图：模仿尝试是学习编程解决问题的一种有效方法。活动1中让学生模仿求24点的程序解决三个问题。为学生搭建三个半成品的程序支架，分别补充程序中的列举部分和检验部分，使其将注意力集中到枚举法的关键之处，一方面降低了学习的难度，另一方面通过对多个个例的模仿，为下面归纳出枚举法的模式做准备。

3.归纳提升，认识枚举法

观察：以上在运用枚举法解决问题时，它们都有一个共同的特点，程序主要由两大部分组成的，分别是哪两大部分？（列举和检验）枚举法解决问题的基本形式如下页图6所示。

小结：运用枚举法解决问题的一般模式是列举→检验。

设计意图：通过上面的模仿学习，学生对枚举法已经有了初步的感性的认识，这个环节通过观察模仿的代码，适时地归纳出枚举法解决问题的一般模式，让学生对枚举法有更深刻的理解，也为后面将该方法迁移到解决同类问题做准备。

4.问题解决，运用枚举法

活动2：运用枚举法解“百鸡问题”。中国古代算书《张丘建算经》中有著名的“百鸡问题”：公鸡每只5文钱，母鸡每只3文钱，而3只小鸡1文钱。用100文钱买100只鸡，问：这100只鸡中，公鸡、母鸡、小鸡各有多少只？

（1）分析问题。

列举：设公鸡的只数为gj，列举的范围是1～100;设母鸡的只數为mj，列举的范围是1～100;设小鸡的只数为xj，列举的范围是1～100。

检验条件：公鸡、母鸡、小鸡只数和是100且三种鸡的价钱和是100。

（2）根据分析完善代码，运行如图7所示程序并检查结果是否正确。

设计意图：在上面几个环节的学习中，学生已经基本了解枚举法的思想，建构起了枚举法的一般模式。方法的习得是为了解决生活中的实际问题，在分析“百鸡问题”过程中，有意识地引导学生思考列举的范围和检验的方法，这样能使学生在构建代码时自然想到可直接把范例代码拿来修改和使用。

5.改进算法，优化枚举法

活动3：优化百鸡问题算法。

（1）计算活动2中程序枚举的次数（1000000），有办法减少枚举的次数，以提高程序的效率吗？

小结：枚举法的优点是简单直观，缺点是效率不高。

（2）重新考察枚举的范围。

分析：总共有100文钱，公鸡每只5文钱，则最多可买多少只？（20）其枚举范围可縮小到1～20;母鸡每只3文钱，则最多可买多少只？（33）其枚举范围可缩小到1～33;要求买100只鸡，而3只小鸡1文钱，小鸡最多可买多少只？（100）枚举的范围是1～100。

修改并运行程序，看能否得到和原始算法一样的结果。试计算程序中枚举的次数（66000），看看算法的效率有没有提高。

小结：缩小枚举范围是优化枚举算法的一种策略。

（3）减少循环层数。

分析：因公鸡、母鸡、小鸡的只数和是100，在枚举公鸡和母鸡的只数后，小鸡的只数xj可怎么表示？（100-gj-mj）不需要再对小鸡枚举，所以第三层循环可舍去。

再次修改并运行程序，看能否得到和原始算法一样的结果。并再次计算枚举的次数（660），看看算法的效率有没有再次提高。

小结：减少循环层数能有效地减少枚举的次数。

设计意图：算法的优化是本课的难点。通过计算原始算法的枚举次数，学生会发现次数较多，自然会想到减少枚举的次数来优化算法。在分析的过程中搭建问题支架，重新考察三种鸡的枚举范围和三种鸡是否都要枚举，分别得出缩小枚举范围和减少循环层数两种常见的优化策略。使学生经历再思考再实践的过程，自觉形成通过技术方法高效解决问题的习惯。

6.思维导图，知识梳理（如图8）

设计意图：用思维导图梳理本课的知识点使学生在头脑中形成清晰的知识结构。

● 教学反思

本课采用案例模仿的教学方法，分别从感知、体验、归纳和运用四个层次引领学生由浅入深地认识了枚举法。在“速算24点”小游戏中，通过口算、手算让学生初步体验了一一列举并检验的思想。但对如何用程序设计语言实现枚举法依然不知晓。为了让学生对枚举法有更加直观的认识，直接给出范例程序让学生读一读，看一看运行结果，形成对枚举法的初步印象。活动1则是对范例模仿的过程，选取三个可用枚举法解决的典型问题，给出半成品程序，采用局部探究的方法，把关注的焦点集中在范例的“列举”和“检验”部分。在引导学生模仿范例解决三个个例问题之后，归纳出枚举法解决问题的一般模式，从而实现从“个”到“类”的提升。

枚举法需要对问题所有可能的解一一列举，枚举法的这一特点，导致其效率低下。因而，优化和提升算法，提高程序的效率就成了本课的难点。常见的优化策略有缩小枚举范围、减少循环层数、减少判断每种情况的时间等。考虑到学生初学枚举算法，这里选择减少枚举范围和减少循环层数两种比较好理解的优化策略，通过计算和比较循环的次数，让学生真切地感受算法优化对程序效率的提升。

点  评

“算法与程序设计”是江苏省初中信息技术课程中的独立模块，在教科书中虽然只有一章，但却占了全书的三分之一的篇幅，因而它对培养学生逻辑思维和创新能力的作用是不言而喻的。恰恰算法与程序设计也是中学信息技术学习的难点。教师感到难教，学生感到难学，其中一个重要的原因，是还没有找到行之有效的程序设计教学方法。传统的程序设计教学以程序设计语言的语句为教学单元，重视其语法描述和语义解释，而忽视了在具体语境中整体功用的表达，使得学生不能针对具体应用而编写出能够有效解决问题的代码。

仔细考察枚举、递归等常见的算法不难发现，它们都有相对固定的解决问题的框架，这其实就是程序设计领域“模式”的思想，“模式”是在前人经验中总结出的解决问题的一般方案。本课就是基于模式的程序设计教学方法的有益尝试，教者通过活动1中逐步递进的三个范例，帮助学生建构起枚举法解决问题的模式——列举和检验。这样学生就拥有了一组用枚举法解决问题的代码集合，当再遇到同类问题时，学生只需参考这个问题的代码模式，就能快速地构建出解决这个问题的高质量代码。因而，在解决“百鸡问题”这个问题时，学生自然会想到运用模式而不是再从语句和语法的层面去构建算法。