[计算机]跟我学vb--第15课时穷举法.doc

穷举法重点：1、穷举法的基本思想2、利用穷举法设计程序的基本步骤和方法3、穷举技巧（方案的确立和变量的安排等）难点：1、确定穷举方案和安排变量 2、穷举范围的确定 3、写出符合条件的判断语句导入：假设你有这样一个密码箱，已经很久没有打开了，现在你想打开它，但是忘了密码，你会怎么做？对，我们可以先转动一个密码位，然后固定其他密码位，一个一个号码进行尝试。这个过程就叫做穷举。案例：穷举法的思路：列举出所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解答。用于解决“是否存在”和“有多少可能性”等类型问题。穷举算法模式： （1）问题解的可能搜索的范围：用循环或循环嵌套结构实现； （2）写出符合问题解的条件：用选择语句实现。实例分析： 假设密码是一个5位数。只记得密码为678，其中百位和十位的数字记不清了，但知道该数能够被78整除，也能被67整除。同学们能不能设计一个算法帮找出这个密码。 思考：题目的未知数有哪些？所需哪些变量？题目给出的条件是什么？ （1）分析问题： 求出一个5位数678，能同时被78和67整除。 我们可以从变量的取值范围入手 ，列举出所有情况：这个密码是个五位数678，有2位数字是未知的，把这2位数字的所有可能性演变一次（09），就可以把可能的情况穷举完。再把各位数字合成一个5位数，判断是否同时被78和67整除就可以了。 （2）设计算法 如何确定求解的算法呢?这个问题适合用穷举法进行搜索。设计穷举法的关键是如何列举所有可能的情况。 因为2位数字未知，而且知道每位的变化范围，所以要用2个循环语句实现2位数字的取值，列举出所有的可能值。然后组成5位数d，判断d能否同时78和67整除即可得到结果。所以还需要一个判断语句对列举的五位数进行判断。 分别用a1、a2表示这2位求知数字，在它们各自的范围中变化，然后组成5位数d，判断d能否同时被78和67整除即可得到结果。 （3）编写程序如下：Private Sub Command8_Click()Dim d As LongDim a1,a2 As Integer For a1 = 0 To 9 For a2 = 0 To 9 d = 67000 + a1 * 100 + a2 * 10 + 8 If (d Mod 78 = 0) And (d Mod 67 = 0) Then Print d Next a2 Next a1End Sub （4）调试程序程序运行后单击窗体可得结果：67938复核知这个结果是符合题意了。练习： 有一张单据上有一个5位数的号码2，只有号码中间一位（百位数）能看清数字为2，还知道该数能够被61和83整除。设计一个程序求出该号码。拓展练习： 直角三角形一条直角边长是24，其余的边长都是正整数，而且斜边的长度不超过50。求出所有满足条件的三角形。（4组解）小结：一、穷举法的思路与解题步骤穷举法的基本思路： 把问题涉及的可能情况一一罗列出来，并且根据题目的条件和实际背景逐个作出判断，从中挑选出符合条件的解答。穷举法的解题步骤：1、分析问题，找出条件与未知数，确定变量；2、列举出变量所有可能的情况，用循环或循环的嵌套实现；3、写出符合条件的判断语句，用选择语句实现；4、输出符合条件的情况；5、优化程序。二、上节课练习存在问题存在问题：输出多个答案原因：缺少一个条件，即百位数是否为2，如何取出百位数？a3=a100 mod 10 三、优化程序对于许多问题，解决问题的算法往往不只一种，这时我们就得注意加以选择，找一种更好的算法。讲解上节课练习的第三种算法对比三种算法，如何评价其好坏，效率与可读性如何去兼顾？评价一个算法的好坏，许多时候效率是很重要的，但过分追求效率就会使得程序难以读懂，读不懂的程序就不能维护，使用这种程序就没有信心保证。所以编程要以程序的易读性作为重要的指标，一般不过分追求效率。练习2：1、直角三角形一条直角边长是24，其余的边长都是正整数，而且斜边的长度不超过50。求出所有满足条件的三角形。（4组解）2、如果一个4位数等于它的各位数字的4次方和，则这个4位数称为“玫瑰花”数，例如1634就是一个玫瑰花数： 。试编程