《用穷举法解决问题资料.pptx》由会员分享，可在线阅读，更多相关《用穷举法解决问题资料.pptx（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1用穷举法解决问题资料用穷举法解决问题资料教学重点教学重点(1)建立正确的数学模型，确定穷举方案。(2)根据命题确定可解空间（即变量的取值范围）(3)正确表达“符合条件”的判断。第1页/共15页 教学难点教学难点 n n(1)(1)如何确定穷举方案。如何确定穷举方案。n n(2)(2)如何评价各种穷举方案的优劣。如何评价各种穷举方案的优劣。第2页/共15页穷举法穷举法n n穷举法也是人们常用的解决问题的方法，计算机的出现大大提升了这种方法的意义 n n计算机只是人类的工具，穷举方案的确定得靠人脑来完成，但穷举过程的实施计算机却比人脑有效n n掌握穷举法穷举技巧(变量安排、穷举方案的确定)
2、第3页/共15页问题问题1：n n公元前公元前5 5世纪，我国数学家张丘建在世纪，我国数学家张丘建在算经算经一书中提出了一个一书中提出了一个“百钱百钱买百鸡问题买百鸡问题”。问题如下：鸡翁一值钱。问题如下：鸡翁一值钱5 5，鸡母一值钱，鸡母一值钱3 3，鸡雏三值钱，鸡雏三值钱1 1。百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？n n设公鸡数为设公鸡数为x x，母鸡数为，母鸡数为y y，小鸡数为，小鸡数为z z，则有方程：，则有方程：x+y+z=100 x+y+z=100 5*x+3*y+z/3=100 5*x+3*y+z/3=100 三个未知数，两个方程，如何求
3、解？三个未知数，两个方程，如何求解？第4页/共15页用穷举法求解问题的基本过程用穷举法求解问题的基本过程n n（1 1）分析问题分析问题 利用所学的用解析法设计程序的方法列出了解析式利用所学的用解析法设计程序的方法列出了解析式设公鸡数为设公鸡数为x x，母鸡数为，母鸡数为y y，小鸡数为，小鸡数为z z，则有方程：则有方程：x+y+z=100 x+y+z=100 5*x+3*y+z/3=100 5*x+3*y+z/3=100根据题目意思可知：根据题目意思可知：根据题目意思上式可优化为：根据题目意思上式可优化为：0 X 100 0 X 100/50 X 100 0 X 100/5 0 Y 100
4、 0 y 100/3 0 Y 100 0 y 100/3 0 Z 100 0 Z 100第5页/共15页n n（2 2）设计算法设计算法 X=0X=0 Y=0 Y=0 z=100-x z=100-x y y 判断判断5*x+3*y+1/3*z=1005*x+3*y+1/3*z=100成立，则打印成立，则打印x,y,zx,y,z 如果如果y 33y 33，则，则 y=y+1y=y+1返回返回 如果如果x 20 x 20，则，则x=x+1x=x+1返回返回 结束结束用穷举法求解问题的基本过程用穷举法求解问题的基本过程第6页/共15页用穷举法求解问题的基本过程用穷举法求解问题的基本过程第7页/共15
5、页用穷举法求解问题的基用穷举法求解问题的基本过程本过程n n（4）调试程序n n（5）检测结果第8页/共15页穷举法（枚举法）的基本思想是：穷举法（枚举法）的基本思想是：列举出所有可能的情况，逐个判断有列举出所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从哪些是符合问题所要求的条件，从而得到问题的全部解答。而得到问题的全部解答。即将即将x x、y y、z z的各种可能的值代入方的各种可能的值代入方程，看是否满足两个方程，如果满程，看是否满足两个方程，如果满足，就是一组解足，就是一组解。第9页/共15页错误程序一错误程序一错误程序一错误程序一：（可以得出正确的答案，但程序执行的效率较低，
6、错误原因是没有排除不：（可以得出正确的答案，但程序执行的效率较低，错误原因是没有排除不：（可以得出正确的答案，但程序执行的效率较低，错误原因是没有排除不：（可以得出正确的答案，但程序执行的效率较低，错误原因是没有排除不存在的情况存在的情况存在的情况存在的情况,红色部分为出错所在）红色部分为出错所在）红色部分为出错所在）红色部分为出错所在）Private Sub Command1_Click()Private Sub Command1_Click()Dim x,y,z As IntegerDim x,y,z As Integer For x=0 To For x=0 To 100100 For
7、y=0 To For y=0 To 100100 z=100-x-y z=100-x-y If 5*x+3*y+1/3*z=100 Then Print x,y,z If 5*x+3*y+1/3*z=100 Then Print x,y,z Next y Next y Next x Next xEnd SubEnd Sub第10页/共15页错误程序二错误程序二错误程序二错误程序二：（得出的答案不完整，错误原因是：没有考虑到公鸡、母鸡均有可能不买。：（得出的答案不完整，错误原因是：没有考虑到公鸡、母鸡均有可能不买。：（得出的答案不完整，错误原因是：没有考虑到公鸡、母鸡均有可能不买。：（得出的答案
8、不完整，错误原因是：没有考虑到公鸡、母鸡均有可能不买。红色部分为出错所在）红色部分为出错所在）红色部分为出错所在）红色部分为出错所在）Private Sub Command1_Click()Private Sub Command1_Click()Dim x,y,z As IntegerDim x,y,z As Integer For x=For x=1 1 To 20 To 20 For y=For y=1 1 To 33 To 33 z=100-x-y z=100-x-y If 5*x+3*y+1/3*z=100 Then Print x,y,z If 5*x+3*y+1/3*z=100 T
9、hen Print x,y,z Next y Next y Next x Next xEnd SubEnd Sub第11页/共15页本节小结本节小结n n（1）用穷举算法解决问题，通常可以从两个方面进行分析：确定范围；问题所涉及的情况有哪些，情况的种数可不可以确定。验证条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。n n（2）要使用多重循环。n n（3）如何评价一个算法的好坏，在考虑效率的同时，也要考虑程序的易读性。第12页/共15页n n练习要求（提交作业）1、百钱百鸡问题的求解百钱百鸡问题的求解 2、完成累加器界面和程序完成累加器界面和程序第13页/共15页 累加器界面和程
10、序累加器界面和程序累加器界面和程序累加器界面和程序Private Sub Command1_Click()Private Sub Command1_Click()Dim m,n,k,s As SingleDim m,n,k,s As Singlem=Val(Text1.Text)m=Val(Text1.Text)初值初值初值初值n=Val(Text2.Text)n=Val(Text2.Text)终值终值终值终值k=Val(Text3.Text)k=Val(Text3.Text)步长步长步长步长s=0s=0For i=m To n Step k For i=m To n Step k 求和求和求
11、和求和s s If k=0 Then Exit For If k=0 Then Exit For s=s+i s=s+iNext iNext iIf k=0 ThenIf k=0 Then Label6.Caption=Label6.Caption=步长为零，错！步长为零，错！步长为零，错！步长为零，错！Else Else Label6.Caption=Str$(s)Label6.Caption=Str$(s)End IfEnd IfEnd SubEnd SubPrivate Sub Command2_Click()Private Sub Command2_Click()清除按钮清除按钮清除按钮清除按钮Text1.Text=Text1.Text=Text2.Text=Text2.Text=Text3.Text=Text3.Text=Label6.Caption=Label6.Caption=Text1.SetFocusText1.SetFocusEnd SubEnd Sub第14页/共15页