选修1《穷举法》ppt课件2 高中信息技术.pptVIP

穷举法（枚举法） 学习目标 理解穷举法的思想方法 学会分析建立正确的穷举步骤，归纳穷举法的穷举技巧 学会优化穷举算法 学会使用穷举法解决现实生活、学习中遇到的问题 用穷举法解决问题 计算机的特点之一就是运算速度快、善于重复做一件事情，“穷举法”正是基于这一特点的最古老的算法。它一般是一时找不到解决问题的更好的途径，即从数学上找不到求解的公式或者规则时，根据问题中的“约束条件”，将解的所有可能情况一一列举出来，然后再逐一验证是否符合整个问题的求解要求，从而得到问题的所有解。 示例1 求满足表达式A+B=C的所有整数解，其中A，B，C为1~3之间的整数。 解题思路 本题非常简单，即枚举变量A,B,C的所有可能取值情况，对每种取值情况判断是否符合表达式即可。 算法如下 for A:=1 to 3 do for B:=1 to 3 do for C:=1 to 3 do if(A+B=C) then writeln(A,’ ‘,B,’ ‘,C); 穷举法的定义 所谓穷举法，指的是从可能的解的集合中一一枚举各元素，用题目给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的，即为解。 金手指考试网 / 2016年金手指驾驶员考试科目一 科目四元贝驾考网 科目一科目四仿真考试题C1 解题思路 示例中的解变量有3个：A，B，C。其中 解变量A的可能取值范围A∈{1， 2 ，3} 解变量B的可能取值范围B∈{1， 2 ，3} 解变量C的可能取值范围C∈{1， 2 ，3} 从而问题的可能解有3*3*3=27个，可能解集： （A，B，C）∈{（1，1，1），（1，1，2），（1，1，3），…，（3，3，1），（3，3，2），（3，3，3）} 在上述可能解集中，满足题目给定的检验条件（A+B==C）的解元素，即为问题的解。 穷举法的使用范围 能确定解变量（枚举变量）的个数 n ； 每个解变量Ai（1 = i = n）的可能值能确定范围且能连续取得。 算法框架 设解变量的个数是n,Ai1—解变量Ai的最小值；Aik—解变量Ai的最大值(1≤i≤n)，即A11≤A1≤A1k，Ai1≤Ai≤Aik，……，An1≤An≤Ank 算法框架如下（伪代码）： for A1←A11 to A1k do for A2←A21 to A2k do …………………… for Ai←Ai1 to Aik do …………………… for An←An1 to Ank do if 状态(A1，…，Ai，…，An)满足检验条件 then 输出问题的解； 示例2 “水仙花数问题” 。 水仙花数是指一个三位数，它的各位数的立方和，正好是等于该数本身。例如153=1^3+5^3+3^3。请设计算法求解100-999其他的水仙花。 解题思路 该数的百位范围1-9，十位范围0-9，个位范围0-9 约束条件：该数的个、十、百位数的立方和正好是等于该数本身 程序结构选择：三重循环 解题思路 三位数范围100-999 约束条件：该三位数的各位数的立方和正好是等于该数本身 程序结构选择：一重循环 穷举法 枚举法的特点是算法简单，但有时运算量大。 优化枚举算法（考察重点） 枚举算法的时间复杂度=状态总数*考察单个状态的耗时 排除明显不属于解集的元素 减少状态总数（即减少枚举变量和枚举变量的值域） 降低单个状态的考察代价 示例1优化程序 示例算法显然可以修改如下: for A:=1 to 3 do for B:=1 to 3 do begin C:=A+B; if(C=1)and(C=3) then 输出A,B,C; end 通过变量的依赖关系减少了解变量的个数(局部枚举)，优化了枚举算法，n^3 - n^2。 示例3 公鸡一只值5元，鸡母一只值3元，小鸡三只值1元。现在有100只鸡，正好值100元钱，问公鸡、母鸡和小鸡各有几只？ 练习 完全数 古希腊人称因子的和等于本身的数是完全数，例如28的因子是1、2、4、7、14，而1+2+4+7+14=28，所以28是一个完全数。编程输出2~1000内所有的完全数。 破解密码 一张单据上有一个5位数的编号，其百位数和十位数已经变得模糊不清，但是知道这个5位数是37或67的倍数。现在要求设计一个算法，找出所有满足这些条件的5位数，并统计这些5位数的个数。 n:=25006; For i:=0 to 99 do Begin