穷举法算法案例《用穷举法解决问题》教学设计
教学分析 1.教学目标知识与技能：了解什么是穷举法及其特点，以及用穷举法设计算法的基本过程；能够根据具体问题的要求，使用穷举法设计算法。

过程和方法：运用观察、发现、归纳、应用的方法，发展学生的归纳思维；培养学生独立探究与自主发现的学习能力。

情感态度与价值观：了解算法和程序设计在计算机解决问题过程中的重要性；体验将算法转变为程序的过程，享受计算机解决问题的快乐。

2.教学重点和难点
重点：用穷举算法解决问题的一般步骤；能根据具体问题的要求，提高运用穷举算法解决问题的能力。

难点：通过观察、类比多种方式培养学生归纳思维。

教学过程
1.创设情境激趣引入
教师活动：某同学用自己的QQ号登录，可他记不清密码了，你能帮他找回密码吗？他的密码是一个5位数，67□□8，其中百位和十位上的数字他不记得了，但他还记得该数能够被78整除，也能被67整除。

你能帮他设计一个算法求出该密码吗？希望大家能在学习完下面这个例子后就可以解决这个问题。

设计意图：成功的教学不是强制，而是激发学生的学习兴趣，该导入正是从学生感兴趣的事情着手的。

2.观察―发现―归纳―应用
(1)观察。

教师活动：逐语句调试以下程序，分析程序的执行过程，让学生填写下表，指出此程序功能。

For i=100 to 999
a=int(i /100)
b=int(i /10) mod 10
C=i mod 10
If a^3+b^3+c^3=ithen
Printi
Endif
Next i
(2)发现。

教师引导：在分析上一程序过程中，你能发现什么？
学生发现：①通过分析程序的执行过程，可看出变量a存放的
是一个三位的自然数百位上的数字，变量b存放的是其十位上的数字，变量c存放的是其个位上的数字；②一个三位的自然数，若满足百位的立方、十位的立方与个位的立方之和等于它本身，就输出；③此程序的功能是输出100～999之间的自然数。

教师总结：此程序的特点是将求解对象一一列举出来，然后逐
一加以分析、处理，并验证结果是否满足给定的条件。

当穷举完所有对象，问题将最终得以解决。

我们把这种算法称之为穷举法。

教师引导：对于此题，某同学给出了另一种解法，请分析程序
的执行过程，说出他采用的是什么算法，比较哪一种方法的效率更高，为什么？
For a=1 to 9
For b=0 to 9
For c=0 to 9
If a^3+b^3+c^3=a*100+b*10+c then
Print a*100+b*10+c
Endif
Next c
Next b
Next a
学生发现：第二种方法依然采用的是穷举算法。

在第一个程序中，循环的次数是900次，每次循环要执行四条语句。

而在第二个程序中，循环的次数是9×10×10=900次，但每次循环只执行一条语句，所以第二个程序的执行效率高。

(3)归纳。

教师活动：通过“输出自然数”这一例子，能归纳出用穷举法解决问题的步骤吗？
学生归纳：①确定穷举对象及搜索范围：用循环或循环嵌套实现；②写出符合问题解的条件：用IF语句实现；③尽可能缩小搜索
范围，减少程序运行时间，提高程序的执行效率。

(4)应用。

教师活动：现在我们反回头来看刚开始时让大家思考的那道找
回QQ密码的题，在编程实现之前，我们先来分析回答以下几个和此
题相关的问题：①穷举的对象是什么？其搜索的范围是什么？②符合问题解的条件是什么？③你有方法减小搜索范围，提高程序的执行效率吗？
学生活动：①穷举的对象是密码，其搜索的范围是67008～67998；
②符合问题解的条件是：此数既能被78整除，也能被67整除。

学生活动：在用自然语言描述其算法后，编程实现，帮助某同
学找回QQ密码。

师生互动：在编程过程中，你遇到哪些困难？你是如何解决的？
设计意图：从一个学生熟悉的例子着手，让学生在观察中发现，在发现中质疑，在质疑中归纳，在归纳中解决问题。

学生增长知识的过程是轻松愉快的。

3.对比归纳，深化思维
(1)判断下列两题能否用穷举算法解决，为什么？通过分析，你能归纳出哪些能用穷举法解决，哪些不能用穷举法解决？
①在一个直角三角形中，三条边a、b、c的长度都为整数，且
一条直角边a的长度已确定，斜边c的长度不能超过某数I，找出满足条件的所有直角三角形。

②使用一根长度为L厘米的铁丝，制作一个面积为S的矩形框，要求，计算出满足这种条件的矩形的高h和宽w。

学生归纳：通过两题的对比分析，穷举算法适用的条件是：有
明显的穷举范围且求解对象应该是有限的；可以按某种规则列举对象；有穷举规则；一时找不出解决问题的更好途径时。

(2)《孙子算经》中有许多有趣的数学题，“鸡兔同笼”问题就是一个典型的例子。

原题是：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”
①此题能用穷举算法解决吗？若能，请编程实现。

学生活动：首先用自然语言描述用穷举算法解决，然后在此基础上编程实现。

②此题还可以用其他算法解决吗？若能，请编程实现。

问题分析：此题可用现在的方程来解，可以设鸡有x只，兔有y只。

根据题目条件，因为1只鸡有1个头和2只脚，一只兔有1个头和4只脚，所以可列出这样一个二元一次方程组。

学生活动：用解析法编程实现。

③通过以上问题分析，归纳穷举算法的优点与缺点。

学生活动：比较两种不同算法，归纳出穷举算法的优点及缺点。

设计意图：学生的头脑不是一个需要填满的容器，而是一个需要燃烧的火把。

通过对比、分析、归纳，引导学生的思维活动向纵深发展，由表及里，培养学生良好的思维习惯。

内容仅供参考。