高级编程实践枚举与模拟.ppt

枚举 枚举法,又称穷举法,指在一个有穷的可 能的解的集合中,对每一个元素,判断是否符 合条件. 【例1】求最大公约数 分析：a,b的最大公约数的穷举范围: k=b,b-1,1 满足条件:a%k=0 Void main( ) for(k=b;k=1;k-) if(a%k=0 break; 特点:算法简单,计算量大。 减少计算量的方法: 使用尽可能少的变量 减少代码嵌套层次 避免不必要的判断 选择合适的搜索顺序 【例2】6位分段和平方数 思路1:对所有6位整数,判断是否是一个平方 数,如是,再利用整数和求余运算把a分为两 个3位整数x,y,若满足a=(x+y)2,即找到一个 解. 思路2:对所有平方为6位整数的3位整数b, 求出a=b2,把a分为前后两个3位整数x,y,判 断b是否等于x+y. 【例3】整币兑零问题 思路:对6个变量进行穷举,穷举范围 :0=p1=n, 0=p2=n/2, 0=p5=n/5, 0=p10=n/10, 0=p20=n/20, 0=p50=n/50 满足: p1+2*p2+5*p5+10*p10+20*p20+50*p50=n, 找到一种兑换方法. 优化1: 5个变量确定以后,第6个可以计算出来: p1=n-(2*p2+5*p5+10*p10+20*p20+50*p50) 优化2: 循环条件可以加以限制,如: P5循环从0n/5改进为0(n-2*p2)/5 【例】完美立方 Description 寻找所有四元组(a,b,c,d),使得a3=b3+c3+d3,其 中1a,b,c,dN. Input 正整数N(N=100) Output 每行输出一个完美立方,按照a的值从小到大 依次输出.当两个完美立方等式中a的值相同时 ,依次按照b,c,d的升序排列输出. 分析: 对四个变量按照d-c-b-a的顺序进行枚举. 考虑如何减少循环次数: 1)对于a, 6=a=N 2)b,c,d满足abcd 3)b,c,d都小于a 4)预先计算每个整数的立方 【例】数字三角形 Description 将A,B,C,D,E,F六个变量排成三角形,六个变 量分别取1,6上不相同的证书，且使三角形三 条边上的变量之和相等. Input 一个16之间的整数A Output 所有以A为顶的三角形 分析: 当A确定后,对B,C,D,E,F各变量在取值范围内 ,逐个检验是否满足三边相等. 在各变量的循环中,对已经出现的值将不再考 虑. 对于F可以通过其他变量的值计算获得,可减 少一个变量的循环. 模拟 对于无法找到公式或规律进行求解的问 题,采用模拟的方法,用计算机模拟人解决问 题的方法来寻找答案. 运算模拟 操作过程模拟 【例】n个1 的数字游戏 Description 给定一个正整数p(个位数不为5的奇数),求另 一个正整数q,使得p和q 的积全是1组成的整数. Input 第1 行是测试数据的组数t,每组测试数据占1 行,每行包括一个个位数字不是5的奇数p. Output 对应每组测试数据输出共 t行,每行输出两个 整数,之间有一个空格分隔,一个是q,一个是p和 q的乘积. 分析: 采用模拟除运算. 模拟除的参量: 1)原始数据:个位数字不是5的奇数p 2)初始量:c=11,n=2 3)循环条件:c!=0 4)构造量:m=1 【例】数字七段显示 Description 数字可以通过控制7个发光器件组成. Input 输入包括多行,每行包括三个整数w,h,n, w,h 表示显示数字的尺寸,n是要显示的数字. Output 显示方式是:用w个”-”表示一个水平线段,用h 个”|”表示一个垂直线段.每个数字需