用穷举法解决问题

1、第三章 算法的程序实现 3.2 用穷举法设计程序用穷举法设计程序 教学重点 (1)建立正确的数学模型，确定穷举方案。 (2)根据命题确定可解空间（即变量的取值范围） (3)正确表达“符合条件”的判断。 教学难点 o(1)如何确定穷举方案。o(2)如何评价各种穷举方案的优劣。穷举法o 穷举法也是人们常用的解决问题的方法，计算机的出现大大提升了这种方法的意义 o 计算机只是人类的工具，穷举方案的确定得靠人脑来完成，但穷举过程的实施计算机却比人脑有效o 掌握穷举法穷举技巧(变量安排、穷举方案的确定) 问题1：o 公元前5世纪，我国数学家张丘建在算经一书中提出了一个“百钱买百鸡问题”。问题如下：鸡翁一

2、值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？o 设公鸡数为x，母鸡数为y，小鸡数为z，则有方程： x+y+z=100 5*x+3*y+z/3=100 三个未知数，两个方程，如何求解？ 用穷举法求解问题的基本过程o （1） 分析问题 利用所学的用解析法设计程序的方法列出了解析式设公鸡数为x，母鸡数为y，小鸡数为z，则有方程： x+y+z=100 5*x+3*y+z/3=100根据题目意思可知： 根据题目意思上式可优化为： 0 X 100 0 X 100 / 5 0 Y 100 0 y 100 / 3 0 Z 100o （2） 设计算法 X=0 Y=0 z = 100

3、 - x y 判断5 * x + 3 * y + 1 / 3 * z = 100成立，则打印x,y,z 如果y 33，则 y = y + 1返回 如果x 20，则x = x + 1返回 结束用穷举法求解问题的基本过程用穷举法求解问题的基本过程用穷举法求解问题的基本过程o （4） 调试程序o （5） 检测结果穷举法（枚举法）的基本思想是： 列举出所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的全部解答。 即将x、y、z的各种可能的值代入方程，看是否满足两个方程，如果满足，就是一组解。错误程序一：（可以得出正确的答案，但程序执行的效率较低，错误原因是没有排除不存在的情况,红色部

4、分为出错所在） 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 xEnd Sub错误程序二：（得出的答案不完整，错误原因是：没有考虑到公鸡、母鸡均有可能不买。红色部分为出错所在）Private Sub Command1_Click()Dim x, y, z As Integer For x = 1 To 20 F

5、or 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 xEnd Sub本节小结o （1）用穷举算法解决问题，通常可以从两个方面进行分析： 确定范围；问题所涉及的情况有哪些，情况的种数可不可以确定。 验证条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。o （2）要使用多重循环。o （3）如何评价一个算法的好坏，在考虑效率的同时，也要考虑程序的易读性。o 练习要求（提交作业） 1、百钱百鸡问题的求解百钱百鸡问题的求解 2、完成累加器界面和程序完成

6、累加器界面和程序累加器界面和程序累加器界面和程序Private Sub Command1_Click()Dim m, n, k, s As Singlem = Val(Text1.Text) 初值初值n = Val(Text2.Text) 终值终值k = Val(Text3.Text) 步长步长s = 0For i = m To n Step k 求和求和s If k = 0 Then Exit For s = s + iNext iIf k = 0 Then Label6.Caption = 步长为零，错！步长为零，错！ Else Label6.Caption = Str$(s)End IfEnd SubPrivate Sub Comman