数据结构电子科技-第五章算法设计

数据结构与算法设计技术是密切相关的好的算法需要选择适当的数据结构概括介绍算法设计策略分治法贪心法动态规划回溯法分支限界法5.1算法分析技术对算法分析主要包含时间复杂度和空间复杂度的分析;算法的程序实现后，其执行时间主要花费在循环和递归上。

GeneralRules

循环:一个循环的运行时间是循环内的语句最大运行时间乘以迭代次数.

嵌套循环:一组嵌套循环的总的运行时间是一个循环的执行时间乘以嵌套的循环个数..

连续语句:所有连续语句运行时间求和(即这些语句运行时间的最大值).

IF/ELSE:Forthefragment

if(Condition)S1;

elseS2;

运行时间永远也不会超过Conditon测试语句+max(S1,S2)[例5.1].有人想知道一年内一对兔子可繁殖成多少对，便筑了一道围墙把一对兔子关在里面。已知一对兔子每一个月可以生一对小兔子，而一对兔子出生后第二个月就开始生小兔子。假如一年内没有发生死亡，则一对兔子一年内能繁殖成多少对？

分析:现在我们寻求兔子繁殖的规律。成熟的一对兔子用记号●表示，未成熟的用○表示。每一对成熟的兔子经过一个月变成本身的●及新生的未成熟○。未成熟的一对○经过一个月变成成熟的●，不过没有出生新兔，这样便可画出右上图设Fn为第n个月农场所有的兔子数量,则Fn=Fn-1+Fn-2且F0=0,F1=1;由此公式,可以写出求解第n个月农场所有的兔子数量的算法算法1--递归:longFibnacci_rec(intn){ if(n==0) return0; if(n==1) return1; else returnFibnacci_rec(n-1)+Fibnacci_rec(n-2);}T(N)=?longFibnacci_ite(intn){ inta=0; intb=1; intc=0; inti,n; for(i=0;i<n;i++) { a=b; b=c; c=a+b; } returnc;}算法2—迭代:T(N)=?小结1．循环的时间代价分析方法：对单个循环，循环次数乘以循环体中基本操作（最耗时）即为其时间代价对多个并列循环，可先计算每个循环的时间代价，然后按加法规则计算总代价对多层嵌套循环，可按乘法规则计算时间复杂度2．递归的时间代价分析方法：

对于递归算法，一般可以把时间代价表示为一个递推方程。

递归算法时间代价分析方法：

决定问题规模的度量

找出算法的基本操作

对于算法基本操作的执行次数，建立一个递推方程，以及相应的初始条件

解这个递推方程【例5.2】给定的n阶方阵A和B，求计算乘积C=AB的算法时间复杂度。C也是一个n阶方阵，它的每个元素都是矩阵A的行和矩阵B的列的乘积：算法5.2求矩阵乘积算法：

Matrixmultiplication(A[0..n-1,0..n-1],B[0..n-1,0..n-1]){for(i=0;i<n;i++)for(j=0;j<n;j++)C[i,j]0;for(k=0;k<n;k++)

C[i,j]=C[i,j]+A[i,k]*B[k,j];}基本操作：乘法三层嵌套循环，每层均为n时间复杂度为O（n3）【例5.3】对于任意非负整数n，计算阶乘函数的值。因为当n≥1时，并且根据定义，0！=1，可以使用下面的递归算法计算：算法5.3阶乘算法F(n){

/*递归计算n!*/

if(n==0)return1;

elsereturnF(n-1)*n；

}可以建立该算法基本运算乘法执行次数M(n)的递推关系和初始条件：用反向替换法来解这个递推方程：问题规模为：n基本操作为：乘法TowerofHanoi问题问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻，每个塔座上不能将大盘压到小盘上解决方法：n=1时，直接把圆盘从A移到Cn>1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题算法：执行情况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示nxyz返回地址

main(){intm;printf("Inputnumberofdisks”);scanf("%d",&m);printf(”Steps:%3ddisks”,m);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6n

xyz返址

main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB6

main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC0

main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(1){(2)if(n==1)(3)move(1,x,z);(4)else{(5)hanoi(n-1,x,z,y);(6)move(n,x,z);(7)hanoi(n-1,y,x,z);(8)}(9)}ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0栈空3ABC02BAC8

在算法设计中，我们会遇到一些问题可以用直观的思维解决。下面介绍两种基本策略：穷举法递推法5.2直接法例：求二维空间两点间距离设点是以标准的笛卡尔坐标形式(x,y)给出，两点间的距离是标准的欧几里德距离：算法5.4使用穷举法求平面中距离最近的两点qiongjuclosepoints(p)/*输入：n(n≥2)个点的坐标列表p：（x0，y0）、（x1，y1）…*//*输出：两个最近点的下标，index1和index2*/{dmin=∞;for(i=0;i<n-1;i++)for(j=i+1;j<n-1;j++){d=sqrt((xi-xj)2+(yi-yj)2);/*求平方根*/if(d<dmin){dmin=d;index1=i;index2=j}}}1.递归实现：a*b=b+(a-1)*b

intmul1(inta，intb){ifa==0return0

elsereturn(b+mul1(a-1，b))}2.迭代实现：a*b=a个b之和intmul2(inta，intb){z=0；

for（

i=1；i<=a；i++）z+=b；

return(z)}例：计算两个非负整数a*b的算法小结:穷举法穷举法是一种最简单、也可能是最容易应用的算法设计策略，常常直接基于问题的描述和所涉及的概念定义，例如：计算的值。可以简单地把１和a相乘n次，来得到的值。穷举法的特点：1.和其他策略不同，穷举法可以解决各种问题2.穷举法效率通常很低3.可以用穷举法解决问题规模较小的问题小结:递推法递推法是利用问题本身所具有的递推关系，来求解问题。即由问题的递推性质，能从已求得的规模为1，2,…，i-1的一系列解，构造出问题规模为i的解，直到问题规模n。例如，n的阶乘就可以形成如下一系列解：1！=1,２!=2*1！,…,n！=n*(n-1)!令fact(n)为n的阶乘，依据后项与前项的关系，可写出递推公式递推策略与递归实现和迭代实现递推是数学上的概念，主要是指递推公式或者说递推数列，递推函数，也就是说一个数列的下面一项由它的前面几项的值的一种运算构成，比如a[n]=a[n-1]+a[n-2]；递归和迭代是计算机中的概念，递归就是指有直接或间接调用自己的函数（计算机中函数是指一段代码）。递推函数在计算机上实现，可以通过递归来实现，也可以通过迭代来实现。Fib序列的递归实现：intFib(intn){if(n=0)return0;if(n=1)return1;return(Fib(n-1)+Fib(n-2));}Fib序列的迭代实现：

intFib(intn){intf1=0,f2=1;inti,f;if(n=0)f=0;if(n=1)f=1;for(i=2;i<=n;i++){f=f1+f2;f1=f2;f2=f;}returnf;}适合于递归实现的问题类型有：

函数定义是递归的

┏1当n=0阶乘n!=┃

┗n*(n-1)!当n>0┏0n=0Fibonacci数列Fib(n)=┃1n=1┗Fib(n-1)+Fib(n-2)n>1

数据结构是递归结构

二叉树，广义表结构本身固有递归特性，操作也可递归描述解法是递归的汉诺塔问题1.应用递归算法主要原因：适用于要解决的问题,要计算的函数,要处理的数据结构已是递归定义的场合.2.递归过程的特点：是程序设计的一个强有力的工具，它具有结构清晰，程序易编、易读、易调试，程序正确性易证明等优点；但运行效率低。3.基本原理：重复地把问题转化为与原问题相似的新问题，直到问题可解决为止。4.关键点：

①用较简单的新问题来表示较复杂的原问题(递归方程) 例如：n！=n(n-1)！，或n!=(n+1)！/(n+1)。 ②不能产生自己调用自己的无穷序列，即必须有一个递归调用序列的“出口”，来终止递归调用(边界条件)5.实现：递归过程都是通过栈来实现的，并且任何递归算法均可通过栈改写为非递归算法。【例5.6】饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。问到第12个月时，该饲养场共有兔子多少只？假设第1个月时兔子数为s1，第2个月时兔子数为s2，第3个月时兔子数为s3，则有s1＝1，s2＝s1+s1×1＝2，s3＝s2+s2×1＝4，……根据规律，可归纳出递推公式：sn

＝sn－1×2(n≥2)对应sn和sn－1，定义两个迭代变量y和x，可将上面的递推公式转换成如下迭代关系：y=x*2，x=y对这个迭代关系重复执行11次，就可以算出第12个月时的兔子数。算法5.6迭代法解兔子繁殖问题

voidmain()

{x=1;

for(i=2;i<=12;i++)

{y=x*2;

x=y;/*新值代替旧值*/}

printf(“%d”,y);}迭代变量：y和x迭代关系：y=x*2，x=y迭代控制：11次再看看递归与迭代实现的差异认识和计算n！有多种方式：1.递归方式：n！=n*（n-1）！Factorial_recursive（n）{ifn==1thenRETURN1elseRETURN（n*Factorial（n-1））}Factorial_recursive(6)(6*Factorial_recursive(5))(6*(5*Factorial_recursive(4)))(6*(5*(4*Factorial_recursive（3))))(6*(5*(4*(3*Factorial_recursive（2)))))(6*(5*(4*(3*(2*Factorial_recursive(1))))))(6*(5*(4*(3*(2*1)))))(6*(5*(4*(3*2))))(6*(5*(4*6)))(6*(5*24))(6*120)720递归计算过程:构造了一个推迟进行操作的链（乘法链），需要保存操作轨迹，长度正比于n。分展开和收缩两个阶段：在展开阶段，把较复杂的问题的求解推到比原问题简单的问题的求解。在收缩阶段，当获得最简单的情况后，逐级返回，依次获得稍复杂问题的解。2.迭代的递归实现方式：n！=1*2*……*（n-1）*n先计算1*2，然后再将结果乘以3，再将所得结果乘以4，……，直到结果乘以n。用一个计数器counter从1到n，再用一个乘积product，每一步都按如下规则改变：product=counter*product；counter=counter+1；n！就是counter超过n时product的值。Factorial_iterative（n）{Fact_iter（1，1，n）}Fact_iter（product，counter，max_count）{ifcounter>max_countthenRETURNproductelseFact_iter（counter*product，counter+1，max_count）}Factorial_iterative（6）Fact_iter（1，1，6）Fact_iter（1，2，6）Fact_iter（2，3，6）Fact_iter（6，4，6）Fact_iter（24，5，6）Fact_iter（120，6，6）Fact_iter（720，7，6）720迭代计算过程:在计算的过程中没有展开和收缩，只需要保存counter、product和max_count的当前值。3.迭代的非递归实现方式：n！=1*2*……*（