穷举法 VB.ppt

1、,登录11，将“课堂资料”中名字为“穷举法”的文件夹下载到自己的电脑上。,穷举法,陈忍,复习解析法,Private Sub Command1_Click() Dim t As Single Dim s As Single Dim d As Single Dim u As Single t = Val(shuru.Text) s = t d = t Do u = 0.7 * d d = u s = s + d + u Loop While (u = t / 1000) shuchu.Text = s End Sub,导入,某个暑假你携带密码行李箱外出旅游，旅行中发

2、现自己忘记了开锁的密码，怎么办？,用穷举法设计程序,一、穷举法的基本思想 二、穷举法的程序实践 三、穷举算法小结,穷举法的基本含义,“穷举法”也称为“枚举法”或“列举法”。 穷举法，指在一个有穷的可能的解的集合中，一一列举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。穷举完所有对象，问题最终得以解决。 穷举法在具体的程序实现过程中，可以通过循环和条件判断语句来完成。 穷举法常用于解决“是否存在”或“有多少种可能”等类型的问题。,穷举法的特点,穷举法的特点是算法简单，在用穷举法设计算法时，重点注意优化，减少

3、运算工作量。 将与问题有关的知识条理化、完备化、系统化，从中找出规律，减少列举量。,穷举法的应用举例1,1、“水仙花数问题” 。 水仙花数是指一个三位数，它的各位数的立方和正好是等于该数本身。153=13+53+33。请设计算法求解该问题。,思路：三位数范围100-999 约束条件：该三位数的各位数的立方和正好是等于该数本身 程序结构选择：一重循环,水仙花数问题,Private Sub command1_Click() Dim x As Integer Dim a As Integer Dim b As Integer Dim c As Integer x = 100 Do While x =

4、 999 a = x Mod 10 b = x 10 Mod 10 c = x 100 If x = a*a*a+b*b*b+c*c*c Then Print x; x = x + 1 Loop End Sub,穷举法的应用举例2,2、公鸡一只值5元，鸡母一只值3元，小鸡三只值1元。现在有100只鸡，正好值100元钱，问公鸡、母鸡和小鸡各有几只？ 设公鸡、母鸡、小鸡各为x、y、z，列出方程为： x+y+z=100 5x+3y+z/3=100 三个未知数，两个方程，此题有若干个解，采用“穷举法”，把每一种情况都考虑到。 解决此类问题采用“试凑法”，把每一种情况都考虑到。 方法一：最简单三个未知数

5、利用三重循环来实现。 方法二：从三个未知数的关系，利用两重循环来实现。,注意：减少穷举的范围和不必要的穷举是优化穷举算法的关键。,百钱买百鸡,Private Sub Command1_Click() Dim x, y, z As Integer Dim a As Integer For x = 0 To 20 For y = 0 To 33 For z = 0 To 100 If 5*x+3*y+z/3=100 And x+y+z=100 Then Print x=; x; Print y=; y; Print z=; z End If Next z Next y Next x Print E

6、nd Sub,小结,穷举法是最简单的一种解题策略，也是最容易想到的一种方法，利用穷举法解题需要列举出问题的解的所有状态，其弱点便在于列举量太大，从而导致算法效率十分低下。 优化：通过对问题的分析，挖掘出问题的隐含条件，尽可能排除那些明显不可能属于问题的解的状态，就是一个行之有效的办法。,练习,实例：输出100200间不能被3整除的数。 分析：验证100到200间所有的数，如果满足条件则输出。 实现：在窗体上添加command1按钮，其代码窗口中输入代码，如右所示。 说明（1）10个数打印一行，a为计数变量，i为要验证的数。 （2）“print”为打印一回车，光标跳至下一行；“print i；”为在当前位置打印，光标向后移动。,Private Sub command1_Click() dim a as integer,i as integer a=0 for i=100 to 200 if i mo