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

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

宋巍巍任静曹恒来

●学习内容分析

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

●学习者分析

●学习目标

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

●教学过程

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）其枚举范