第3章 算法基本工具和优化技巧

第3章算法基本工具和优化技巧3．1循环与递归3．2算法与数据结构3．3算法优化基本技巧3．4优化算法的数学模型1.循环设计要点2.递归设计要点3.递归与循环的比较3.1循环与递归1．设计中要注意算法的效率√2．“自顶向下”的设计方法3．由具体到抽象设计循环结构√一、循环设计要点循环体的特点是：“以不变应万变”。所谓“不变”是指循环体内运算的表现形式是不变的，而每次具体的执行内容却是不尽相同的。在循环体内用不变的运算表现形式去描述各种相似的重复运算。1．循环设计中要注意算法的效率)!12/()1(11nSSnnn)!12()1(!71!51!31!111nn【例】求数学模型1：main(){inti,n,j,sign=1;floats,t=1;input(n);s=1；for(i=2;i=n;i=i+1){t=1;//求阶乘for(j=1;j=2*i-1;j=j+1)t=t*j;sign=1;//求（-1）n+1for(j=1;j=i+1;j=j+1)sign=sign*(-1);s=s+sign/t;}print(“Sum=”,s);}算法的时间复杂度：O（n2）效率较低！(2n-1)!=(2(n-1)-1)!*(2n-2)*(2n-1))!12/()1(11nSSnnn数学模型2：main(){inti,n,sign;floats,t=1;input(n);s=1；sign=1;for(i=2;i=n;i=i+1){sign=-sign;t=t*(2*i-2)*(2*i-1);s=s+sign/t;}print(“Sum=”,s);})12(*)22(*;)1(111nnAAASSnnnnnn算法的时间复杂度：O(n)2．“自顶向下”的设计方法自顶向下的方法是从全局走向局部、从概略走向详尽的设计方法。自上而下是系统分解和细化的过程。【例】一个数如果恰好等于它的因子之和（包括1，但不包括这个数本身），这个数称为“完数”。编算法找出1000以内所有完数。例如，28的因子为1、2、4、7，14（每个因数只记一次），而28=1+2+4+7+14。因此28是“完数”。输出格式如下：28it’sfactorsare1，2，4，7，14。1）顶层算法for(i=2;i=1000;i=i+1){判断i是否为“完数”；是“完数”则按格式输出；}2）判断i是否为“完数”for(j=2;ji;j=j+1)找i的因子，并累加如果累加值为i，则是“完数”3）进一步细化——判断i是否“完数”算法s=1;for(j=2;ji;j=j+1)if(imodj=0)s=s+j;if(s=i)i是“完数”;4）考虑输出格式——判断i是否“完数”算法考虑到要按格式输出结果，应该开辟数组存储数据i的所有因子，并记录其因子的个数，因此算法细化如下：定义数组a，s=1;k=0;for(j=2;ji;j=j+1)if(imodj=0)(j是i的因素){s=s+j;a[k]=j;k=k+1;}if(s=i){按格式输出结果}算法如下：main(){inti,k,j,s,a[20];for(i=1;i=1000;i++){s=1;k=0;for(j=2;ji;j++)if(imodj=0){s=s+j;a[k]=j;k++;}if(i=s){print(s,“it’sfactorsare:”,1);for(j=0;ik;j++)print(“,”,a[k]);}}}对于不太熟悉的问题，其数学模型或“机械化操作步骤”的不易抽象，下面看一个由具体到抽象设计循环细节的例题。【例】编写算法：打印具有下面规律的图形。152863109743．由具体到抽象设计循环结构main(){inti,j,a[100][100],n,k;input(n);k=1;for(i=0;i=n-1;i=i+1)for(j=0;j=n-i;j=j+1){a[i-1+j][j]=k;k=k+1;}for(i=0;i=n-1;i=i+1){print(“换行符”);for(j=0;j=i;j=j+1)print(a[i][j]);}}二、递归设计要点思想：把一个复杂问题转换为一个与原问题相似的规模较小问题。设计方法：问题描述：定义递归模块形式；递归关系：大规模问题与小规模问题的关系；停止条件：所描述问题的最简单情况，它本身不再使用递归的定义。【例】汉诺塔问题古代有一个梵塔，塔内有3个基座A、B、C，开始时A基座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A座移到B座，但每次只允许移动一个盘子，且在移动过程中在3个基座上的盘子都始终保持大盘在下，小盘在上。在移动过程中可以利用C基座做辅助。请编程打印出移动过程。递归关系：把n阶的汉诺塔问题的模块记作hanoi(n,a,b,c)a：起始基座，b:终点基座，c:辅助基座问题描述：则汉诺塔问题hanoi(n,a,b,c)等价于以下三步：第一步，hanoi(n-1,a,c,b)；第二步，把下面“一个”盘子从a基座移到b基座；第三步，hanoi(n-1,c,b,a)。停止条件：当n=1时：ab算法如下：hanoi(intn,chara,charb,charc){if(n=1)print(a,””,b);else{hanoi(n-1,a,c,b);print(a,””,b);haboi(n-1,c,b,a);}}三、递归与循环的比较◆递归与循环都是解决“重复操作”的机制。◆递归使一些复杂的问题处理起来简单明了。◆就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。◆每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然。◆递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。【例】任给十进制的正整数，请从高位到低位逐位输出各位数字。f3(n){intj,i=0,a[16];while(n=10){a[i]=nmod10;i=i+1;n=n\10;}a[i]=n;for(j=i;j=0;j=j-1)print(n);}循环算法如下：f4(n){if(n10)print(n);else{f4(n\10);print(nmod10);}}递归算法设计：算法分析递归算法程序更简单，可读性好函数递归调用时需要保存现场，并开辟新的运行资源；返回时，又要回收资源。因此递归算法的时间复杂度和空间复杂度相对较高【例】找出n个自然数(1,2,3,…,n)中r个数的组合。例如，当n=５,r=3时，所有组合为：123124125134135145234235245345total=10{组合的总数}循环算法1：Constitute1(){intn=5,i,j,k,t;t=0;for(i=1;i=n;i--)for(j=1;j=n;j--)for(k=1;k=n;k--)if(ij)and(jk)t=t+1;print('total=',t);}时间复杂度O(n3)循环算法2：constitute2（）{intn=5,r=3,i,j,k,t;t=0;for(i=1;i=n-r+1;i=i+1)for(j=i+1;j=n-r+2;j=j+1)for(k=j+1;k=n-r+3;k=k+1)t=t+1;print('total=',t);}效率稍好，时间复杂度还是O(n3)用递归法设计此题：问题描述：comb(n,r)：从n个自然数中取r个的组合数递归关系：comb(n,r)=comb(n-1,r-1)+comb(n-2,r-1)+…+comb(r-1,r-1)停止条件：comb(n,1)=ncomb(n,n)=1递归算法如下：intcomb(intn,intr){inti,s;if(r=1)returnn;elseif(n=r)return1;else{s=0for(i=n-1;i=r-1;i--)s=s+comb(i,r-1);returns;}}r层递归，每个算法递归n-r+1次。因此时间复杂度为O(n*r)算法分析递归的层次是可以控制的，而循环嵌套的层次只能是固定的递归非递归程序可读性易难代码量大小小大时间长短占用空间大小适用范围广窄设计难度易难递归与非递归的比较：3.2算法与数据结构数据的逻辑结构常分为四大类：（1）集合结构（2）线性结构（3）树形结构（4）图结构（网结构）存储结构可以分为：连续存储和链式存储。连续存储又可以分为：静态存储和动态存储1、常用的几种数据结构顺序存储的优点：(1)方法简单，各种高级语言中都提供数组结构，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。2、连续存储和链式存储比较顺序存储的缺点：(1)在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。温馨提示：链表的优缺点恰好与顺序表相反。3、在选取存储结构时权衡因素有：１）基于存储的考虑顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。２）基于运算的考虑在顺序表中按序号访问ai的时间性能时O(1)，而链表中按序号访问的时间性能O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；但对于插入、删除操作，则后者优于前者。３）基于环境的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，操作简单。一、原始信息与处理结果对应存储每一个问题中的信息往往是多方面的，在算法中一般有输入信息、输出信息和信息加工处理过程中的中间信息。那么哪些信息需要用数组进行存储，数组元素下标与信息怎么样对应等问题的确定，在很大程度上影响着算法的编写效率和运行效率。【例】某校决定由全校学生选举学生会主席。有5个候选人，编号分别为1，2，3，4，5，选举其中一人为学生会主席，每个学生一张选票，只能填写一人。请编程完成统计选票的工作。算法如下：vote(){inti,xp,a[5]={0，0，0，0，0};input(xp);while(xp!=-1){if(xp=1andxp=5)a[xp]=a[xp]+1;elseprint(xp,inputerror!);input(xp);}for(i=1;i=5;i++)print(i,numberget,a[i],votes);}【例】编程统计身高（单位为厘米）。统计分150——154；155——159；160——164；165——169；170——174；175——179及低于是150、高于是179共八档次进行。算法设计：算法如下：main(){inti,xp,a[8];input(sg);while(sg-1){if(sg179)a[7]=a[7]+1；elseif(sg150)a[0]=a[0]+1；elsea[sg/5-29]=a[sg/5-29]+1；input(sg);}for(i=0;i=7;i=i+1)print(i+1,“fieldthenumberofpeople：”,a[i]);}二、数组使信息有序化当题目中的数据缺乏规律时，很难把重复的工作抽象成循环不变式来完成，但先用数组结构存储这些地信息后，问题就迎刃而解了，【例】编程将编号“翻译”成英文。例35706“翻译”成three-five-seven-zero-six。main(){inti,a[10],ind;longnum1,num2;chareng[10