2算法基本工具

1算法基本工具22.1循环与递归设计算法重复处理大量数据的思路：以不变应万变；两种思路：循环、递归。1循环设计要点例2.1求完数例2.2打印数字图形例2.3求级数2递归设计思路(运行机制、复杂度分析)例2.4累加求和3递归设计要点例2.5hanoi塔4非递归(循环)/递归比较31循环设计要点循环控制-熟悉；设计要点：“自顶向下”的设计方法由具体到抽象设计循环结构注意算法的效率41循环设计要点-例2.1例2.1编算法找出1000以内所有完数。如：28的因子为1、2、4、7，14，而28=1+2+4+7+14。因此28是“完数”。编算法找出1000之内的所有完数，并按下面格式输出其因子：28it’sfactorsare1，2，4，7，14。问题分析：1、这里不是要质因数，所以找到因数后也无需将其从数据中“除掉”。2、每个因数只记一次，如8的因数为1，2，4而不是1，2，2，2，4。(注：本题限定因数不包括这个数本身)51循环设计要点-例2.1核心算法设计for(i=0;in;i=i+1){判断i是否是完数;if是“完数”则按规则输出;}自顶向下，逐步求精判断i是否是完数for(j=2;ji;j=j+1)找i的因子，并累加；if累加值等于i，则i是完数；判断i是否是完数s=1；for(j=2;ji;j=j+1)if(i%j==0)s=s+j;if(s==i)i是“完数”;判断是否是完数的方法是“不变”，被判断的数是“万变”。6输出数据的方法是“不变”，被输出的数是“万变”。1循环设计要点-例2.1考虑到要按格式输出结果，应该开辟数组存储数据i的所有因子，并记录其因子的个数，因此算法细化如下：inta[100]，s=1,k=0;for(j=2;ji;j=j+1)if(i%j==0){s=s+j;a[k]=j;k=k+1;}if(s==i){print(s,“it’sfactorsare:”,1);for(j=0;jk;j++)print(“,”,a[k])}71循环设计要点-例2.2对于不太熟悉的问题，其“不变”不易抽象；162107313118415141295n=5例2.2编写算法：根据参数n打印具有下面规律的图形，如，当n=4时，图形如下：1528631097481循环设计要点-例2.215286310974问题分析：容易发现图形中数据排列的规律。另一种思路先用一个数组按此顺序存储数据，再正常输出；15286310974可不可以从1—最大数，通过循环，直接输出？printf是按照从左至右、从上至下的顺序；若想直接输出，只有找出公式，循环计算得到序列：1-\n-5-2-\n-8-6-3-\n-10-9-7-4.为数组赋值，也要用循环，如何循环？又要回到找规律公式的路上吗？斜着能循环吗？让循环泼辣一点。91循环设计要点-例2.2用斜行、列描述新的循环方向。15286310974斜[1，1]—a[1,1]斜[1，2]—a[2,2]斜[1，3]—a[3,3]斜[1，4]—a[4,4]斜[2，1]—a[2,1]斜[2，2]—a[3,2]斜[2，3]—a[4,3]列号相同；行号(显然行号与列号有关)第1斜行，对应行号1—n，行号与列号j同；第2斜行，对应行号2—n，行号比列号j大1；第3斜行，对应行号3—n，行号比列号j大2；斜[3，1]—a[3,1]斜[3，2]—a[4,2]斜行i取值(1~n)列j取值(1~n+1-i)a[i-1+j][j]这样可以描述循环。但数组元素的存取还是基于“行列”，能否简单转换？关键问题：第i斜行、j列的数据对应于第几行第几列的元素？斜[4，1]—a[4,1]101循环设计要点-例2.2main(){inti,j,a[100][100],n,k;input(n);k=1;for(i=1;i=n;i=i+1)for(j=1;j=n+1-i;j=j+1){a[i-1+j][j]=k;k=k+1;}for(i=1;i=n;i=i+1){print(“换行符”);for(j=1;j=i;j=j+1)print(a[i][j]);}}斜行i取值(1~n)列j取值(1~n+1-i)15286310974111循环设计要点-例2.3例2.3求级数求：1/1!-1/3!+1/5!-1/7!+…+(-1)n+1/(2n-1)!问题分析：此问题中既有累加又有累乘，累加的对象是累乘的结果。数学模型1：Sn=Sn-1+(-1)n+1/(2n-1)!算法设计1：直接利用题目中累加项通式，构造出循环体不变式为：S=S+(-1)n+1/(2n-1)!需要用二重循环来完成算法。算法设计1：外层循环求累加S=S+A;内层循环求累乘A=(-1)n+1/(2n-1)!。121循环设计要点-例2.3算法分析：以上算法是二重循环来完成，但算法的效率却太低O(n2)。数学模型2：Sn=Sn-1+(-1)n+1An；An=An-1*1/((2*n-2)*(2*n-1))其原因是，当前一次循环已求出7！，当这次要想求9！时，没必要再从1去累乘到9，只需要充分利用前一次的结果，用7！*8*9即可得到9！，模型为An=An-1*1/((2*n-2)*(2*n-1)。算法分析：按照数学模型2，只需一重循环就能解决问题算法的时间复杂性为O(n)。132递归设计思路-例2.4程序结构化设计的三种基本结构，顺序、选择、循环是不是必须的？例2.4根据参数n，计算1+2+……+n。voidsum_loop(intn){inti,sum=0;for(i=1;i=n;i++){sum=sum+i;}printf(\nsum=%d,sum);}nisum回答：在很多高级语言中，不是。可以抛弃谁呢？递归能取代循环的作用。142递归设计思路-例2.4例2.4根据参数n，计算1+2+……+n。intsum_recursive(intn){intsum=0;if(n==1)sum=1;elsesum=sum_recursive(n-1)+n;printf(\nsum=%d,sum);returnsum;}sum(n)sum(n-1)n+sum(n-2)n-1+…….sum(n-3)n-2+1递归算法是一个模块(函数、过程)除了可调用其它模块(函数、过程)外，还可以直接或间接地调用自身的算法。直接/间接递归调用。代入n=4，走一遍。递归树！sum(1)2+152递归设计思路-例2.4例2.4根据参数n，计算1+2+……+n。intsum_recursive(intn){intsum=0;if(n==1)sum=1;elsesum=sum_recursive(n-1)+n;printf(\nsum=%d,sum);returnsum;}…栈顶(top)栈底(bottom)出栈进栈栈底元素栈顶元素n…sumn-1…sum……..;2…sum1…sum表面上是一个变量，实际上是一个栈162递归设计思路-例2.4例2.4根据参数n，计算1+2+……+n。intsum_recursive(intn){intsum=0;if(n==1)sum=1;elsesum=sum_recursive(n-1)+n;printf(\nsum=%d,sum);returnsum;}T(n)=T(n-1)+O(1)sum(1)sum(n)sum(n-1)n+sum(n-2)n-1+…….sum(n-3)n-2+2+1=T(n-2)+O(1)+O(1)=……….=n*O(1)=O(n)17“收敛”3递归设计要点递归的关键在于找出递归方程式和递归终止条件。递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。递归边界条件：也就是所描述问题的最简单情况，它本身不再使用递归的定义。intsum_recursive(intn){intsum=0;if(n==1)sum=1;elsesum=sum_recursive(n-1)+n;printf(\nsum=%d,sum);returnsum;}sum(n)sum(n-1)n+sum(n-2)n-1+…….sum(n-3)n-2+sum(1)2+118例1.1欧几里德算法gcd(m,n)=gcd(n,mmodn)输入正整数m和n输出m和n的最大公因子1.如果n=0,计算停止返回m,m即为结果；否则继续2。2.记r为m除以n的余数，即r=mmodn。3.把n赋值给m，把r赋值给n，继续1。伪代码如下(循环)：Euclid(m,n){whilen0{r=m％n;m=n;n=r;}}递归代码：GCD(m,n)//约定mn//{ifn=0return(m)elsereturn(GCD(n,mmodn))}19GCD(22,8)GCD(8,6)GCD(6,2)GCD(2,0)2递推递推递推递推回归回归回归回归结果为GCD(22,8)=2例：GCD(22,8)=GCD(8,6)=GCD(6,2)=GCD(2,0)=2;203递归设计要点-hanoi塔Hanoi塔hanoi河内[越南首都]古代有一个梵塔，塔内有3个基座A、B、C，开始时A基座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A座移到B座，但每次只允许移动一个盘子，且在移动过程中在3个基座上的盘子都始终保持大盘在下，小盘在上。在移动过程中可以利用C基座做辅助。请编程打印出移动过程。约定盘子自上而下的编号为1，2，3，……，n。213递归设计要点-hanoi塔首先看一下2阶汉诺塔问题的解，不难理解以下移动过程：初始状态为A(1,2)B()C()第一步后A(2)B()C(1)第二步后A()B(2)C(1)第三步后A()B(1,2)C()用递归思路考虑223递归设计要点-hanoi塔把n个盘子抽象地看作“两个盘子”，上面“一个”由1——n-1号组成，下面“一个”就是n号盘子。移动过程如下：第一步：先把上面“一个”盘子以a基座为起点借助b基座移到c基座。第二步：把下面“一个”盘子从a基座移到b基座。第三步：再把c基座上的n-1盘子借助a基座移到b基座。递归：领导的艺术233递归设计要点-hanoi塔把n阶的汉诺塔问题的模块记作hanoi(n,a,b,c)a代表每一次移动的起始基座；b代表每一次移动的终点基座；c代表每一次移动的辅助基座；则hanoi(n,a,c,b)，表示把n个盘子从a搬到c，可以借助b；hanoi(5,c,a,b)，表示把5个盘子从c搬到a，可以借助b。则汉诺塔问题hanoi(n,a,b,c)等价于以下三步：第一步，hanoi(n-1,a,c,b)；第二步，把下面“一个”盘子从a基座移到b基座；第三步，hanoi(n-1,c,b,a)。至此找出了大规模问题与小规模问题的关系。243递归设计要点-hanoi塔hanoi(n,a,b,c)a：起始基座b：终点基座c：辅助基座hanoi(n,a,b,c)hanoi(n-1,a,c,b)hanoi(n-1,c,b,a)移hanoi(n-2,a,b,c)hanoi(n-2,b,c,a)移………………………………hanoi(2,..,..,..)hanoi(2,..,..,..)移hanoi(1,..,..,..)移hanoi(1,..,..,..)hanoi(0,..,..,..)/hanoi(0,..,..,..)O(2n)253递归设计要点-hanoi塔hanoi(intn,chara,charb,charc)/*a,b,c初值为”A”,”B”,”C”*/if(n0){/*0阶的汉诺塔问题当作停止条件*/hanoi(n-1,a,c,b);输出“Movedish”,n.”frompile”,a,”to”b);hanoi(n-1,c,b,a);}264非递归(循环)/递