山东省枣庄市第八中学教科版高中信息技术选修一课件：3.2用穷举法解决问题(共12张PPT)

穷举法: 也叫枚举法、列举法，它将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将最终得以解决。 计算机的特点之一就是运算速度快、善于重复做一件事情，“穷举法”正是基于这一特点的最古老的算法。它一般是一时找不到解决问题的更好的途径，即从数学上找不到求解的公式或者规则时，根据问题中的“约束条件”，将解的所有可能情况一一列举出来，然后再逐一验证是否符合整个问题的求解要求，从而得到问题的所有解。 穷举法的应用举例 1、“水仙花数问题” 。 水仙花数是指一个三位数，它的各位数的立方和正好是等于该数本身。153=1^3+5^3+3^3。请设计算法求解该问题。 思路1：三位数范围100-999 约束条件：该三位数的各位数的立方和正好是等于该数本身 程序结构选择：一重循环 思路2：该数的百位范围1-9，十位范围0-9，个位范围0-9 约束条件：该数的个、十、百位数的立方和正好是等于该数本身 程序结构选择：三重循环 如果你理解了这2个思路，可以在VB 中编写出来么？GO! 方法一： For I=100 to 999 A=int(I/100) B=int(I/10) mod 10 C=I mod 10 If a^3+b^3+c^3=I then print I End if Next I 方法二： For a=1 to 9 for b=0 to 9 for c=0 to 9 if a^3+b^3+c^3=a*100+b*10+c then print a*100+b*10+c endif next c next b next a 二、用穷举法解决问题的步骤 1、确定问题解可能搜索的范围：用循环或嵌套来实现） 2、写出符合问题解的条件：用if语句实现 3、尽可能地缩小搜索的范围，减少程序运行时间，提高程序的执行效率。 2、例：公元前5世纪，我国数学家张丘建在《算经》一书中提出了一个“百钱买百鸡问题”。问题如下：鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？ 分析： 穷举的对象： 穷举的范围： 判断式： 鸡翁、鸡母、鸡雏 0 ≤ a≤ 100 0 ≤