穷举法-VB课件.ppt

1、登录登录ftp:/192.168.1.211，将将“课堂资料课堂资料”中名字为中名字为“穷穷举法举法”的文件夹下载到自己的的文件夹下载到自己的电脑上。电脑上。穷举法穷举法陈忍陈忍复习解析法Private Sub Command1_Click()Dim t As SingleDim s As SingleDim d As SingleDim u As Singlet = Val(shuru.Text)s = td = tDou = 0.7 * dd = us = s + d + uLoop While (u = t / 1000)shuchu.Text = sEnd Sub导入 某个暑假你携带密

2、码行李箱外出旅游，旅行中某个暑假你携带密码行李箱外出旅游，旅行中发现自己忘记了开锁的密码，怎么办？发现自己忘记了开锁的密码，怎么办？用穷举法设计程序一、穷举法的基本思想一、穷举法的基本思想二、穷举法的程序实践二、穷举法的程序实践三、穷举算法小结三、穷举算法小结穷举法的基本含义“穷举法穷举法”也称为也称为“枚举法枚举法”或或“列举法列举法”。 穷举法，指在一个有穷的可能的解的集合中，一一列举出集合中的每穷举法，指在一个有穷的可能的解的集合中，一一列举出集合中的每一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满一个元素，用题目给定的检验条件来判断该元素是否符合条件，若满足条件，则该元素

3、即为问题的一个解；否则，该元素就不是该问题的足条件，则该元素即为问题的一个解；否则，该元素就不是该问题的解。穷举完所有对象，问题最终得以解决。解。穷举完所有对象，问题最终得以解决。穷举法在具体的程序实现过程中，可以通过穷举法在具体的程序实现过程中，可以通过循环循环和和条件判断语句条件判断语句来完来完成。成。穷举法常用于解决穷举法常用于解决“是否存在是否存在”或或“有多少种可能有多少种可能”等类型的问题。等类型的问题。穷举法的特点 穷举法的特点是穷举法的特点是算法简单算法简单，在用穷举法设计算法，在用穷举法设计算法时，重点注意时，重点注意优化优化，减少运算工作量。，减少运算工作量。 将与问题有关

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

5、 Sub command1_Click()Dim x As IntegerDim a As IntegerDim b As IntegerDim c As Integerx = 100Do While x = 999a = x Mod 10b = x 10 Mod 10c = x 100If x = a*a*a+b*b*b+c*c*c Then Print x;x = x + 1LoopEnd Sub穷举法的应用举例22、公鸡一只值、公鸡一只值5元，鸡母一只值元，鸡母一只值3元，小鸡三只值元，小鸡三只值1元。现元。现在有在有100只鸡，正好值只鸡，正好值100元钱，问公鸡、母鸡和小鸡各元钱，问

6、公鸡、母鸡和小鸡各有几只？有几只？设公鸡、母鸡、小鸡各为设公鸡、母鸡、小鸡各为x、y、z，列出方程为：，列出方程为： x+y+z=100 5x+3y+z/3=100三个未知数，两个方程，此题有若干个解，采用三个未知数，两个方程，此题有若干个解，采用“穷举法穷举法”，把每一种情况都考虑到。，把每一种情况都考虑到。解决此类问题采用解决此类问题采用“试凑法试凑法”，把每一种情况都考虑到。，把每一种情况都考虑到。方法一：最简单三个未知数利用三重循环来实现。方法一：最简单三个未知数利用三重循环来实现。方法二：从三个未知数的关系，利用两重循环来实现。方法二：从三个未知数的关系，利用两重循环来实现。注意：减

7、少穷举的范围和不必要的穷举是优化穷举算法的关键。注意：减少穷举的范围和不必要的穷举是优化穷举算法的关键。百钱买百鸡Private Sub Command1_Click()Dim x, y, z As IntegerDim a As IntegerFor x = 0 To 20For y = 0 To 33For z = 0 To 100If 5*x+3*y+z/3=100 And x+y+z=100 ThenPrint x=; x;Print y=; y;Print z=; zEnd IfNext zNext yNext xPrintEnd Sub小结 穷举法是最简单的一种解题策略，也是最容易

8、想穷举法是最简单的一种解题策略，也是最容易想到的一种方法，利用穷举法解题需要列举出问题到的一种方法，利用穷举法解题需要列举出问题的解的所有状态，其弱点便在于列举量太大，从的解的所有状态，其弱点便在于列举量太大，从而导致算法效率十分低下。而导致算法效率十分低下。 优化：优化：通过对问题的分析，挖掘出问题的隐含条通过对问题的分析，挖掘出问题的隐含条件，尽可能排除那些明显不可能属于问题的解的件，尽可能排除那些明显不可能属于问题的解的状态，就是一个行之有效的办法。状态，就是一个行之有效的办法。练习实例：输出实例：输出100200间不间不能被能被3整除的数。整除的数。分析：验证分析：验证100到到200

9、间间所有的数，如果满足条件所有的数，如果满足条件则输出。则输出。实现：在窗体上添加实现：在窗体上添加command1按钮，其代码按钮，其代码窗口中输入代码，如右所窗口中输入代码，如右所示。示。说明说明（1）10个数打印一个数打印一行，行，a为计数变量，为计数变量，i为要为要验证的数。验证的数。（2）“print”为打印一回为打印一回车，光标跳至下一行；车，光标跳至下一行；“print i；”为在当前位为在当前位置打印，光标向后移动。置打印，光标向后移动。Private Sub command1_Click() dim a as integer,i as integera=0for i=100 to 200 if i mod 30 then if a=10 then print a=0 else a=a+1 print i; end if end ifnext iprintend sub