高级编程实践---枚举与模拟

【例1】求最大公约数分析：a,b的最大公约数的穷举范围:k=b,b-1,……,1满足条件:a%k==0&&b%k=0;Voidmain(){……for(k=b;k=1;k--)if(a%k==0&&b%k==0){printf(“%ld\n”,k);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循环从0~n/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=N2)b,c,d满足abcd3)b,c,d都小于a4)预先计算每个整数的立方【例】数字三角形Description将A,B,C,D,E,F六个变量排成三角形,六个变量分别取[1,6]上不相同的证书，且使三角形三条边上的变量之和相等.Input一个1~6之间的整数AOutput所有以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的奇数p2)初始量:c=11,n=23)循环条件:c!=04)构造量:m=1【例】数字七段显示Description数字可以通过控制7个发光器件组成.Input输入包括多行,每行包括三个整数w,h,n,w,h表示显示数字的尺寸,n是要显示的数字.Output显示方式是:用w个”-”表示一个水平线段,用h个”|”表示一个垂直线段.每个数字需要占用w+2列和2*h+3行..分析:用三维数组表示用于显示0~9的各个笔画.将整数拆分放在数组中对数组中的每个数字按行进行显示在显示过程中控制列宽和行高