穷举法 VB.ppt

《穷举法 VB.ppt》由会员分享，可在线阅读，更多相关《穷举法 VB.ppt（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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、完备化、系统化，从中找出规律，减少列举量。从中找出规律，减少列举量。穷举法的应用举例11、“水仙花数问题水仙花数问题”。水仙花数是指一个三位水仙花数是指一个三位数，它的各位数的立方和正好是等于该数本身。数，它的各位数的立方和正好是等于该数本身。153=13+53+33。请设计算法求解该问。请设计算法求解该问题。题。思路：三位数范围思路：三位数范围100-999约束条件：该三位数的各位数的立方和正好是等于该数本身约束条件：该三位数的各位数的立方和正好是等于该数本身程序结构选择：一重循环程序结构选择：一重循环水仙花数问题Private Sub command1_Click()Dim x As In

5、tegerDim 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元钱，问公鸡、母鸡和小鸡各有元钱，问公鸡、母鸡和小鸡各有几只？几只？设公鸡、母鸡、小鸡各为设公鸡、母鸡、小鸡各为x、y、z，列出方

6、程为：，列出方程为：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间间所有的数，如果满足条件所有的数，如果满足条件则输出。则输出。实现：在窗体上添加实现：在窗体上添加command1按钮，其

9、代码按钮，其代码窗口中输入代码，如右所窗口中输入代码，如右所示。示。说明说明（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