第三章 第二节 用穷举法解决问题

第三章第二节 用穷举法解决问题

【教学目标】

1、知识与技能

   (1)．认识程序调试的意义。

   (2)．基于计算机解决问题的调整，穷举法是计算机求解问题的基本算法。

   (3)．穷举法也是人们常用的解决问题的方法，计算机的出现大大提升了这种方法的意义。

   (4)．掌握用穷举法设计程序的基本思路。

   (5)．通过调试不同的例程，掌握穷举法穷举技巧(变量安排、穷举方案的确定)。

   (6)．计算机只是人类的工具，穷举方案的确定得靠人脑来完成，但穷举过程的实施计算机却比人脑有效。

   (7)．通过深入研究穷举的技巧，积累程序设计的经验，提升自己设计程序求解问题的能力。

   (8)．对于多种解决问题的方案，学会评价它们的好坏。

【能力目标】

本节以“百钱买百鸡问题”入手，由浅入深讲解了穷举算法的思路。通过讨论、对比、总结，熟练掌握穷举算法的求解问题方法。在编程实践之后，对各种方案进行对比试验，加深穷举算法的理解。

【情感态度和价值观】

通过本节内容的学习，学生对设计算法求解问题有了进一步的认识，对设计算法的步骤更加熟练，思考问题更加严密和有条理，程序编制和调试更有经验。本节的学习对算法知识的积累，对继续学习的激发有更加强烈的愿望，培养学生的爱国主义精神。

【重点难点】

1、教学重点

    (1)建立正确的数学模型，确定穷举方案。

    (2)根据命题确定可解空间（即变量的取值范围）。

    (3)正确表达“符合条件”的判断。

2、教学难点

    (1)如何确定穷举方案。

    (2)如何评价各种穷举方案的优劣。

【教学安排】

1课时

【教学过程】

新课导入：

   问题1：

公元前5世纪，我国数学家张丘建在《算经》一书中提出了一个“百钱买百鸡问题”。问题如下：鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？

学生们利用所学的用解析法设计程序的方法很快就列出了解析式：

设公鸡数为x，母鸡数为y，小鸡数为z，则有方程：

X+y+z=100

5*x+3*y+z/3=100

学生产生议论，三个未知数，两个方程，如何求解？

老师引出穷举法的基本思想。

穷举法（枚举法）的基本思想是：列举出所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的全部解答。即将x、y、z的各种可能的值代入方程，看是否满足两个方程，如果满足，就是一组解。

老师巡查发现同学们做出来的答案有两类错误。

　　第一类错误如下程序所示：（可以得出正确的答案，但程序执行的效率较低，错误原因是没有排除不存在的情况,红色部分为出错所在）

Private Sub Command1_Click()

Dim x, y, z As Integer

  For x = 0 To 100

    For y = 0 To 100

       z = 100 - x - y

       If 5 * x + 3 * y + 1 / 3 * z = 100

Then Print x, y, z

    Next y

  Next x

End Sub

运行结果：

图　第一类错误程序运行的结果

第二类错误如下程序所示：（得出的答案不完整，错误原因是：没有考虑到公鸡、母鸡均有可能不买。）

Private Sub Command1_Click()

Dim x, y, z As Integer

  For x = 1 To 20

    For y = 1 To 33

       z = 100 - x - y

       If 5 * x + 3 * y + 1 / 3 * z = 100 Then Print x, y, z

    Next y

  Next x

End Sub

运行结果：

二、 用穷举法求解问题的基本过程

1.百钱买百鸡问题的求解

正确的算法：

（1）    分析问题

设公鸡数为x，母鸡数为y，小鸡数为z，则有方程：

X+y+z=100

5*x+3*y+z/3=100

根据题目意思可知：

0 ≤ X ≤ 100

0 ≤ Y ≤ 100

0 ≤ Z ≤ 100

根据题目意思上式可优化为：

0 ≤ X ≤ 100 / 5

0 ≤ y ≤ 100 / 3

（2）设计算法

① X=0

② Y=0

③ z = 100 - x – y

④ 判断5 * x + 3 * y + 1 / 3 * z = 100成立，则打印x,y,z

⑤ 如果y ≤ 33，则 y = y + 1返回 ③

⑥ 如果x ≤ 20，则x = x + 1返回 ②

⑦ 结束

（3）编写程序

Private Sub Command1_Click()

Dim x, y, z As Integer

  Print "公鸡", "母鸡", "小鸡"

  Print

  For x = 0 To 20

    For y = 0 To 33

       z = 100 - x - y

       If 5 * x + 3 * y + 1 / 3 * z = 100

Then Print x, y, z

    Next y

  Next x

End Sub

（4）调试程序

正确程序运行的结果

（5）    检测结果

探究：

　　可不可以先对小鸡进行选择，如果可以程序代码如何改变，与程序4－4比较，哪个程序执行的次数多些，为什么？