算法分析与设计之作业习题答案

算法分析与设计作业答案第一章绪论一填空算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算2..算法具备五个重要特性：确定性、可实现性、数据输入、数据输出、有穷性3.要制定一个算法，一般要经过设计、确认、分析、编码、调试等阶段。4.算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。5．一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上。时间和空间资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。7.算法的时间复杂性函数用T(n)表示，它是问题的大小n的函数。8.n在不同的问题中有不同的表现形式。指出下列问题中n的计量。1)在数组中找值为c的分量，n表示数组中分量的个数2)两个矩阵相乘,n表示矩阵的阶3)一个数表的排序，n表示数组中元数的个数4)遍历一棵二叉树，n表示树中的结点数9.最坏情况下的时间复杂性定义：W(n)=max{T(n，I)},I∈Dn10.平均情况下的时间复杂性定义：A(n)＝∑P(I)T(n，I)I∈Dn11.最具有可操作性和实际价值的是最坏情况下的时间复杂性定义复杂性。教材中没有特殊说明时，T(n)一般指的就是最坏情况下的时间复杂性定义。12．f(n)=O(g(n))表示当且仅当存在正的常数C和N0，使得对于所有的n=N0，有f(n)=cg(n)。13.写出下列f(n)的渐进性态：1)f(n)=C0，为常数：f(n)=O(1)。2)f(n)=3n+2：f(n)=O(n)。3)f(n)=6×2n+n：f(n)=O(2n)。4)f(n)=nlogn：f(n)=O(nlogn)。二分析算法复杂性1.已知不重复且已经按从小到大排好的m个整数的数组A[L．m](为简单起见，设m＝2k，k是一个确定的非负整数)。对于给定的整数c，要求寻找一个下标i，使得A[i]=c,若找不到，则返回一个0。算法如下：proceduresearch(c)/*c是整型数*/{i←0;j←l;whileA[j]candjndo{ifA[j]=ctheni←j；j←j+1;}returni;}分析最坏的情况下即在A中找不到等于c的分量情况下的时间复杂性函数。答：如果C不在A中需要比较n次，时间复杂性函数为T(n)=n2.冒泡排序算法的基本运算如下：fori←1ton-1doforj←1ton-idoifa[j]a[j+1]then交换a[j]、a[j+1]；分析该算法的时间复杂性。解：排序算法的基本运算步为元素比较，冒泡排序算法的时间复杂性就是求比较次数与n的关系。1）设比较一次花时间12）内循环次数为：n-i次,（i=1,…n），花时间为：injin1)(13）外循环次数为：n-1，花时间为：)1(2)()(1nninnTni第二章分治法一.回答问题1．分治法的基本思想是什么？答：将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1k≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。2.写出分治法一般方法的递归过程。DanC(p,q)globaln，A[1:n];integerm,p,q;//1pqnifSmall(p,q)thenreturnG(p,q);elsem=Divide(p,q);//pmqreturnCombine(DanC(p,m),DanC(m+1,q));endifendDanC2．假定在A(1：9)中顺序存放着以下九个元素：-15，-6，0，7，9，23，54，82，101，用二分检索算法检索x=101是否在A中，需要比较几次？解：第一次执行循环体：mid=5，A[mid]x需要在A[5]~A[9]中检索；第二次执行循环体：mid=7，A[mid]x需要在A[8]~A[9]中检索；第三次执行循环体：mid=8，A[mid]x需要在A[9]~A[9]中检索；第四次执行循环体：mid=9，A[mid]=x返回9；需要比较4次。二．分析时间复杂性1.递归求取最大和最小元素算法MAXMIN的时间复杂性。解：设算法的元素比较次数为T(n)，mid将数组分成大小为2/2/nn和的两部分，递归调用原过程分别在两部分找max1、min1和max2、min2，分别花时间为)2/()2/(nTnT和，比较max1、max2和min1、min2找出max、min所花时间为2。因此递归方程为：2)2/()2/(10)(nTnTnT。当n是2的幂时，即对于某个正整数k，n：2k，有2/2/nn和T(n)：2T(n/2)+2＝2(2T(n/4)+2)+2=4T(n/4)+4+2……2T(2)2111kkii＝2k-1+2k-2＝3n/2-2所以：223)(nnT2.归并分类算法解：用T(n)表示归并排序所用的时间，两个子集递归调用归并排序过程所花时间：2T(n/2)，合并过程所用时间为cn，其中c是一个正数，则有递归方程：1)2/(21)(ncnnTnanT其中，a是一个常数。若n是2的方幂：kn2，直接推导可得ncnankcnTcnnTcncnnTnTklog)1(22)4/(4)2/)4/(2(2)(对于一般的整数n，我们可以假定122kkn，于是)2()(1kTnT，所以)log()(nnOnT3.汉诺塔问题解：汉诺塔问题的时间复杂性是完成ｎ个圆盘移动所移动的次数。设移动总次数为Ｔ(ｎ)，由于原问题分成了三个子问题：两个移动ｎ-1个圆盘的问题和一个移动一个圆盘的过程。两个移动ｎ-1个圆盘的问题采用递归调用，花时间Ｔ(ｎ-1)，移动一个圆盘花一个单位时间。所以的递归方程如下：11)1(211)(nnTnnT直接推导可得121.....2)1(212)2(41)1)2(2(2)(21nnnTnTnTnT第3章贪心方法一．填空1.贪心方法是一种分级处理方法。它首先根据题意，选取一种量度标准。然后按这种量度标准对这n个输入排序，并按序一次选入一个量。如果这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。选择能产生问题最优解的量度标准是使用贪心法设计求解的核心问题。2．贪心方法的抽象化控制procedureGREEDY(A，n)//A(1：n)包含n个输入//solutions←Φ；fori←1tondox←SELECT(A)ifFEASIBLE(solution，x)thensolutions←UNION(solution，x)；endifrepeat；return(solution)endGREEDY3．背包问题可以获得最优解的输入排序是P(i)/W(i)≥P(i+1)/W(i+1)。4．背包问题的贪心算法procedureGREEDY-KNAPSACK(P，W，M，X，n)X←0//将解向量初始化为零//cu←M//cu是背包剩余容量//fori←1tondoifW(i)≤cuthenexitendifX(i)←1；cu←cu-W(i)；repeat；ifi≤nthenX(i)←cu/W(i)；endifendGREEDY-KNAPSACK5.带有限期的作业排序lineprocedureJS(D，J，n，k)//D(1)，…，D(n)是期限值。n≥1。作业已按p1≥p2≥…pa被排序。J(i)是最优解中的第i个作业，1≤i≤k。终止时，D(J(i)≤D(J(I+1))，1≤ik//1integerD(0：n)，J(0：n)，i，k，n，r2D(0)←J(0)←0//初始化//3k←1；J(1)←1//计入作业1//4fori=2tondo5r←k;6whileD(J(r))D(i)andD(J(r))rdo7r←r-1;8repeat9ifD(J(r))≤D(i)andD(i)rthen10forl←ktor+1by-ldo11J(I+1)←J(l)；12repeat13J(r+1)←i；k←k+1；14endif15repeat16endJS二设计算法1．有n个程序和长度为L的磁带，程序i的长度为ai，已知Lanii1，求最优解(xi，x2，...，xi，…，xn)，xi=0，1,xi=1，表示程序i存入磁带，xi=0，表示程序i不存入磁带，满足Laxniii1，且存放的程序数目最多。解：由于目标是存放的程序数目最多，所以最优量度应该是min{ai|ai为程序i的长度}，即每次选入的程序都是当前最短的。我们可以将n个程序按a[1]≤a[2]≤…≤a[n]顺序排序，然后从i=1开始依次选择。算法如下：procedureprogramming(L,n,a,x)begin//n个程序按a[1]≤a[2]≤…≤a[n]顺序排序x←0;i=1;while(a[i]≤Landi≤n)do{x[i]←1;L←L-a[i]；i←i+1;}end.3.有n个活动争用一个活动室。已知活动i占用的时间区域为[si，fi]，活动i,j相容的条件是：sj≥fi，问题的解表示为(xi|xi=1，2…，n,)，xi表示顺序为i的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。解：解决这个问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中元素的顺序按结束时间非减排列：f1f2…fn。算法如下：GreedyAction(s,f，n)//s[1:n]、f[1:n]分别代表n项活动的起始//时间和结束时间,并且满足f[1]f[2]…f[n]j=1;solution={1};//解向量初始化为空集fori←2tondoifsifjthensolution=solution{j};//将j加入解中j=i;endifendforreturn(solution);endGreedy第四章动态规划一.填空1.最优化原理：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态所产生的状态构成一个最优决策序列。无论过程的是什么，其余的决策都必须相对于初始决策。2．最优子结构性质：原问题的最优解包含了其子问题的最优解。3.子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被被反复计算多次。二．回答问题1.写出0/1背包问题的递推式，并简述其表述的意义。答：0/1背包问题的递推式如下：fi（X）＝max{fi-1(X)，fi-l(X—wi)+pi|X≥wi}，fi（X）表示前i个物品，背包容积为X(0≤X≤M)下获得的最大利润，fi-1(X-wi)+pi表示第i个物品选入获得的利润pi，与前i-1个物品在背包容积为X-wi下获得的最大利润fi-l(X—wi)之和；fi-1(X)表示第i个物品不选入，前i-1个物品在背包容积为X下获得的最大利润fi-l(X)，fi（X）在两种情况下选择。2.写出多段图的向后递推式，并简述其表述的意义。答：多段图的向后递推式如下：)},(),1({cosmin),(cos1jlclitjitiiVjVlcost(i,j)表示从起点到第i级的顶点j的最短路径的代价，cost(i-1,l)表示从起点到第i-1级的顶点l的最短路径的代价，c(l,j)是顶点l到顶点j的代价。cost(i,j)等于两者之和。三.解题1.有一多段图如图所示，按算法4.1的步骤求出最短路经及其代价。解：COST(10)=0COST(9)＝2，D[9]=10,COST(8)＝2D[8]=10,COST(7)＝min{7+COST(9)}＝9,D[7]=9,COST(6)＝min{5+COST(9),3+COST(8)}=min{5+2,3+2}=5,D[6]=8,COST(