算法分析与设计习题集答案.doc

算法分析与设计习题集基础篇1、 算法有哪些特点？它有哪些特征？它和程序的主要区别是什么？特点：就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算（书上定义）特征：输入、输出、有穷性、明确性、有效性区别：算法是完成特定任务的有限指令集。程序是用计算机语言编写的写成特定任务的指令序列。2、 算法的时间复杂度指的是什么？如何表示？算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。（百度百科）3、 算法的空间复杂度指的是什么？如何表示？一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。（1）固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)其中n为问题的规模，S(n)表示空间复杂度。4、 什么是最坏时间复杂性？什么是最好时间复杂性？答：最坏情况时间复杂性：最好情况时间复杂性：I*是DN中使T(N, I*)达到Tmax(N)的合法输入；P(I)是在算法的应用中出现输入I的概率5、 什么是递归算法？什么是递归函数？递归算法（包括直接递归和间接递归子程序）都是通过自己调用自己，将求解问题转化成性质相同的子问题，最终达到求解的的。递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对相关且必要的信息的保存与恢复，从而省略了求解过程中的许多细节的描述。【课本】直接递归 子程序在运行完成前调用它们自己。间接递归 子程序在运行过程中调用其它子程序，其他子程序反过来调用这个调用子程序。递归函数，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。网上：答：（1）递归算法:直接或间接地调用自身的算法；（2）递归函数:用函数自身给出递归定义的函数。6、 分治法的设计思想是什么？将整个问题分成若干个小问题后分而治之给定一个有n个输入的函数，分治策略建议将输入分为k个不同的子集，1kn，从而产生k个子问题。当输入规模n取值较大时，可以将这n个输入分成k（1100递归体是：M（M（x+11）x 100实现本题功能的递归函数如下：intm ( intx ) int y;if ( x100 )return(x-10 );else y =m(x+11) ;return (m (y );procedure M(x) if x100 then return(x-10) else return M(M(x+11) endifend M12、 已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下：voiddel ( seqlist*a )inti=0, j;while ( ilength)if ( a-datai!= a-datai+1)i+;else for ( j=i; jlength; j+)a-dataj=a-dataj+1;a-length-;procedure del(A,LINK,n)/A(1:n)是元素按元素值非递减有序排列的顺序表，LINK(1:n)每个数的下一个数所在的下标，等于0时表示后面再没有数了，初始时为2，3，4n,0 global integer A(1:n),LINK(1:n) integer i,j; i1; while LINK(i)0 do jLINK(i) while jlchild=Null&rooot-rchild=Null) return(1); else num1=CountNode(root-lchild); num2=CountNode(root-rchild); return(num1+num2+1); procedure COUNTNODE(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD integer num1,num2; if T!=0 then if LCHILD(T)=0 and RCHILD(T)=0 then/既没有左孩子，也没有右孩子，则为叶子节点 return(1); else num1=COUNTNODE(LCHILD(T); num2=COUNTNODE(RCHILD(T); return(num1+num2+1);/将左右子树的结点数加起来，再加本身，相当时树的后序遍历 endfi endif return(0);end COUNTNODE 计算叶子总数int CountLeafs(BinTree *root) int num1,num2; if(root=Null) return(0); else if(root-lchild=Null&root-rchild=Null) return(1); else num1=CountLeafs(root-lchild);num2=CountLeafs(root-rchild);return(num1+num2); procedure COUNTLEAFS(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD integer num1,num2; if T!=0 then if LCHILD(T)=0 and RCHILD(T)=0 then/既没有左孩子，也没有右孩子，则为叶子节点 return(1); else num1=COUNTLEAFS(LCHILD(T); num2=COUNTLEAFS(RCHILD(T); return(num1+num2);/将左右子树的结点数加起来，再加本身，相当时树的后序遍历 endfi endif return(0);/T为空时，没有结点end COUNTLEAFS分治术14、 有金币15枚，已知其中有一枚是假的，而且它的重量比真币轻。要求用一个天平将假的金币找出来，试设计一种算法（方案），使在最坏情况下用天平的次数最少。procedure SELECKP(p,q)/A是一个全程数组，分别表示n个硬币的重量，在本题中表示15个硬币；p和q表示假币所在的一组硬币的起始和终止编号；最后返回硬币的编号；在主程序中调用SELECKP(1,15) if p=q then return(p); endif; global ingeger A(p:q);integer a,b,c,d,m; ap;/第一组数的起始编号 dq;/第二组硬币的终止编号 m0;/最多余的一个硬币所在的编号 if(ISODD(q-p+1)/如果该组硬币数量为d奇数 then mq;/最后一个数不作比较 dd-1; edif c(a+d+1)/2;/第二组硬币的起始编号编号 bb-1;/第一组硬币的终止编号 /将该组硬币分为平均分为两组，然后用天平比较两组重量，将轻的一组递归调用本方法 If WEIGHT(a,b)WEIGHT(c,d) then return(SELECKP(c,d); else if m!=0/若两组硬币重量相等，则剩下一个为假币 return(m); else /如果两组硬币重量相等，且没有不比较的硬币，即本次检查的硬币总数为偶数，表示没有硬币 print(没有假币); return(0); endifend SELECKP15、 利用分治策略，在n个不同元素中找出第k个最小元素。procedure SELECT(A,n,k) /在数组A(1),A(n)中找出第k小元素s并把它放在位置k，假设1=k=n。将剩下的元素按如下方式重新排列，使A(k)=t,有A(m)=t，有A(m)=t;对于km=t.A(n+1)=+/ integer n,k,m,r,j; m1rn+1;A(n+1)+; loop /每当进入这一循环时，1=m=r=n+1/ jr/将剩下的元素的最大下标加1后置给j/ call PARTITION(m,j) /返回j，它使得A(j)，它使得A(j)是第j小的值 case :k=j:return /找到该元素该元素为A(j) :k=v repeat /i由左向右移 loop pp-1 until A(p)=v repeat /p由左向右移 if ip-1 then call A(i)A(p) /A(i)和A(p)换位 else exit endif repeat A(m)A(p);A(p)v /划分元素在位置p/end PARTITION16、 设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表。（1）每个选手必须与其它n-1选手各赛一次；（2）每个选手一天只能赛一次。procedure TOURNAMENT(n)/A(1:n,1:n)为全程数组，A(i,j)表示第i天第j个队所比赛的对手,若轮空则为0 globel integer A(1:n,1:n) if n=1 then A(1,1)=1; return; endif if ISODD(n) then/当队数为奇数时，增加一个虚拟队员 TOURNAMENT(n+1); return; endif TOURNAMENT(n/2);/是偶数时，递归调用，返回时合并 call MAKECOPY(n);/主要是将左上角的递归计算出的小块中的所有数字按照其相对位置抄写到右下角，将左上角小块中的所有数字加n/2后按照其相对位置抄写到左下角，将左下角小块中的所有数字按照相对位置抄到右上角。end COUNTLEAFS 17、 已知序列503，87，512，61，908，170，897，275，652，462，写一个自底向上的归并分类算法对该序列作升序排序，写出算法中每一次归并执行的结果。void Merge(ElemType *r，ElemType *rf，int u，int v，int t)for(i=u，j=v，k=u；iv&j=t；k+)if(ri.keyrj.key)rfk=ri；i+；elserfk=rj；j+；if(iv) rfkt=riv-1；if(jelem；for(len=1；lenlength；len=2*len) /*从q2归并到q1*/for(i=1；i+2*len-1length；i=i+2*len)Merge(q2，q1，i，i+len，i+2*len-1)； /*对等长的两个子表合并*/if(i+len-1length)Merge(q2，q1，i，i+len，p-length)； /*对不等长的两个子表合并*/elseif(ilength)while(ilength) /*若还剩下一个子表，则直接传入*/q1i=q2i；q1q2； /*交换，以保证下一趟归并时，仍从q2归并到q1*/if(q1!=p-elem) /*若最终结果不在*p表中，则传入之*/for(i=1；ilength；i+)p-elemi=q1i；Procedure MERGESORT(low, high)/A(low : high)是一个全程数组，它含有high-low+10个待分类的元素/ Integer low, high; If low high then mid int(low+high)/2) /求这个集合的分割点/ call MERGESORT(low, mid) /将一个子集合分类/ call MERGESORT(mid+1, high)/将另一个子集合分类/ cal MERGE(low,mid,high) /归并两个已分类的子集合/ EndifendMERGESORTProcedure MERGE(low, mid, high)/A(low : high)是一个全程数组，它含有两个放在A（low : mid）和A（mid+1 : high）中的已分类的子集合。目标是将这两个已分类的集合归并成一个集合，并存放到A(low : high)中/使用一个辅助数组B(low : high)/ Integer h, I, j, k, low, mid, high; /lowmidmid then/处理剩余的元素/ for kj to high do /第二队列未处理完 B(i) A(k);ii+1 repeat Else for kh to mid do/第一队列未处理完 B(i) A(k); ii+1 repeat endif for k low to high do /将已归并的集合复制到A/ A(k) B(k) repeatendMERGE归并过程（黄色底纹的是每次归并的数）1234567891005038751261908170897275652462187503512619081708972756524622875035126190817089727565246238750351261908170897275652462461875035129081708972756524625618750351290817089727565246266187503512908170275897652462761875035129081702758974626528618750351290817027546265289796187170275462503512652897908贪心法18、 设有n个文件f1，f2，fn要求存放在一个磁盘上，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1，p2，pn，且=1。磁头从当前磁道移到被检索信息磁道所需的时间可用这两个磁道之间的径向距离来度量。如果文件fi存放在第i道上，1in则检索这n个文件的期望时间是。其中d(i，j)是第i道与第j道之间的径向距离。磁盘文件的最优存储问题要求确定这n个文件在磁盘上的存储位置，使期望检索时间达到最小。试设计一个解此问题的算法，并分析算法的正确性与计算复杂性。/*磁盘文件最优存储问题具有贪心选择性质：先将n个文件从大到小按概率进行排序。假设排序后有p1=p2=pn。贪心选择性质表示每次所选择加入的对象文件，都能得到当前的最优值，即使得期望检索时间达到最小。在磁盘最优存储问题中，要想使期望检索时间达到最小。那么就要使两个概率较大者的径向距离越小越好。因此第一次从p1=p2=pn中选取P1所对应的文件f1置于中心磁道上。随后从剩余概率队列中选取概率最大和次最大者所对应的文件放在靠着f1的左磁道，和f1的右磁道。这将得到初始的最优值。同样地，继续选择剩余概率队列中概率最大和次最大者所对应的文件分别置于靠着刚才所得最优位置的左磁道和右磁道上，将得到新的最优值。所以磁盘最优存储问题具有贪心选择性质。最优子结构性质：按照这n个文件的排序概率(p1=p2=pn)假设排序后的理想最优序列为：f（n-1）,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。（n为奇数）。若n为偶数个，则补上一个数0。那么不管n为奇数或者是偶数，其理想最优序列都可以表示为f（n-1）,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。（因为加上一个0，对其达到最小期望检索时间无影响，所以可以进行此处理。）利用反证法思想假设存在一个f（n-1）,f(n-3),f(n-5),f(j)f4,f2,f1,f3,f5,f(i)f(n-2),fn。该序列是原序列对调f(i)与f(j)的位置所得。该序列所得到的期望检索时间小于上面的贪心策略时间。经验证发现，该序列所获得的期望检索时间原所获得的期望检索时间。与最优值相矛盾。故贪心解为最优解。*/procedure GreedySearch(P,A,n) /P(1:n)是按照P(i)=P(i+1)排序的n个文件读取的概率；A(1:n)表示对应的文件序号；X(1:n)表示n个文件分别所放的在磁盘上的存储位置，即所要求的解 integer P(1:n),A(1:n); integer i,k, n; kn/2; /取中间位置,除法为向下取整/ X(k)A(1); /中间位置放概率最大的文件/ for i2 to n by +2 do X(k+i/2)A(i); repeat for i3 to n by +2 do X(k-i/2)A(i); repeatend GreedySearch19、 设有n个正整数，编写一个算法将他们连接成一排，组成一个最大的多位整数。用贪心法求解本题。procedure MAXINT(A,n)/A(1:n)是由n个整数组成的数组，S(1:n)是将A中每个数转化为字符串得到的数组 integer A(1:,i,j,a,b; string B(1:n),s for i1 to n-1 do for i1 to n do aSTRINT(B(i),B(j); bSTRINT(B(j),B(i); for a右边的数，因为删除之后高位减小，很容易想.那全局最优解也就是这个了，因为删除S个数字就相当于执行了S次删除一个数，因为留下的数总是当前最优解.*/procedure GreedyDelet(N,S,X)/N表示高精度的正整数（此整数中没有0），要去掉S个整数，X(1:s)表示删除数字的位置 real X(1:s) char* ntN;/把整数转化为字符串处理 integer sS; while s0 do i=0;/从串首开始 while ilength(nt) and nini+1 do i+; repeat delet(nt,i);/删除串n的第i个字符 s-; X(S-s)i; repeat print(X);/输出每次删除的位置 print(nt);/输出最后组成的新的整数end GreedyDelet21、 对于下图给出的有向网，写出用Dijkstra方法求从顶点A到图中其它顶点的最短路径的算法，并写出执行算法过程中顶点的求解次序及从顶点A到各顶点路径的长度。procedure SHORTEST-PATHS(v,COST,DIST,n) /G是一个n结点的有向图，它由其成本邻接矩阵COST(n,n)表示DIST(j)被置以结点v到结点j的最短路径长度，这里1=j=n; DIST(v)被为0 boolean S(1:n);real COST(1:n,1:n),DIST(1:n) integer u,v,n,num,i,w for i1 to n do /将集合S初始化为空 S(i)0; DIST(j)COST(v,j); repeat S(v)1; /将结点v计入集合S DIST(v)0; for num2 to n-1 do /确定由结点v出发的n-1条路 选取结点u，它使得在S(w)=0 的条件下，DIST(u)=minDIST(w) S(u) 1;/结点计入S for 所有S(w)=0 的结点w do DIST(w)min(DIST(w),DIST(u)+COST(u,w) repeat repeatend SHORTEST-PATHSABCDEFGA048+1528+40B+012+C+043+13+D+0183323E+33+0+F+9+0+G+200执行踪迹迭代选取的结点SSABCDEFG置初值-A048+1528+401DA,D048+152848382EA,D,E04861152848383GA,D,E,G04861152848384BA,D,E,G,B04860152848385FA,D,E,G,B,F048571528483822、 对于上图给出的有向图，写出最小成本生成树，给出求解算法。ACFBEDG91220181523Line procedure KRUSKAL(E,COST,n, T, mincost)/G有n个结点，E是G的边集，COST（u, v）是边（u, v）的成本。T是最小成本生成树的边集，mincost是它的成本。/ 1 real mincost, COST(1: n, 1: n) 2 integer PARENT(1:n), T(1:n-1, 2), n 3 以边成本为元素构造一个min-堆 4 PARENT -1 5 imincost0 6 while in-1 and 堆非空 do 7 从堆中删去最小成本边(u, v)并重新构造堆 8 jFIND(u); kFIND(v) 9 if jk then ii+1 10 T(i, 1)u; T(I,2)v 11 mincostmincost+COST(u, v) 12 call UNION(j, k) 13 endif 14 repeat 15 if in-1 then print(no spanning tree) endif 16 return 17 end KRUSKAL动态规划23、 求出上图中每对结点间的最短距离的算法，并给出计算结果。line procedure ALL-PATHS(COST, A, n) integer i, j, k, n; real COST(n, n), A(n, n)1 for i1 to n do 2 for j1 to n do3 A(i,j) COST(i,j)4 repeat5 repeat6 for k1 to n do7 for i1 to n do8 for j1 to n do 9 A (i,j) minA(i,j), A(i,k)+A(k,j)10 repeat11 repeat12 repeat13 end ALL-PATHSABCDEFGA0485715284838B01255732578C043611366D420183323E337604699F95270075G29729020024、 下图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?line procedure FGRAPH(E, k, n, P)/多段图的向前处理算法,输入是按照段的给结点编号的，有n个结点的k段图。E是边集，c(i,j)是边(i,j)的成本。P(1:k)是最小成本路径/1 real COST(n), integer D(n-1),P(k), r, j, k, n2 COST(n)03 for jn-1 to 1 by -1 do 4 设r是一个这样的结点，E且使c(j, r)+COST(r)取最小值。5 COST（j）c(j, r)+COST(r)6 D(j) r7 repeat/找一条最小成本路径8 P(1) 1;P(k) n9 for j2 to k-1 do/找路径上的第j个结点10 P(j) D(P(j-1)11 repeat12 end FGRAPH最短路程:1371011(13)25、 已知序列a1，a2，an，试设计一算法，从中找出一子序列 ai1 ai2 aik使k达到最大，并讨论其复杂性。算法一：procedure lis(A,f,n)/A(1:n)为长度为n数组序列，f(i)表示A中以A(i)为末元素的最长递增子序列的长度 f(0)1;/以第a1为末元素的最长递增子序列长度为1； for i 2 to n do/循环n-1次 f(i)1;/f(i)的最小值为1； for j0 to i do/循环i 次 if A(j)f(i)-1 then /选出最大的f(j) f(i)f(j)+1;/更新f(i)的值。 endif repeat repeat return f(n-1)end lis这个算法有两层循环，外层循环次数为n-1次，内层循环次数为i次，算法的时间复杂度所以T(n)=O(n2)。这个算法的最坏时间复杂度与第一种算法的阶是相同的。算法二：（改进后算法）procedure lis1(A,B,n)/A(1:n)为长度为n数组序列,数组B来存储“子序列的”最大递增子序列的最末元素 B0=-10000;/把B0设为最小，假设任何输入都大于-10000； B1=A0;/初始时，最大递增子序列长度为1的最末元素为a1 int len = 1;/Aen为当前最大递增子序列长度，初始化为1； int p,r,m;/p,r,m分别为二分查找的上界，下界和中点； for i = 1 to n do p=0;r=len; while p=r do/二分查找最末元素小于ai+1的长度最大的最大递增子序列； m = (p+r)/2; if Bmlen) then len+;/更新当前最大递增子序列长度； endif repeat return len;end lis1算法的循环次数为n，每次循环二分查找用时logn，所以算法的时间复杂度为O(nlogn)。这个算法在第二种算法的基础上得到了较好的改进26、 设计一个O（n2）时间的算法，找出由n个数组成的序列的最长的单调递增子序列。（上题算法一）27、 旅游预算问题。一个旅行社需要估算乘汽车从某城市到另一城市的最小费用，沿路有若干加油站，每个加油站收费不一定相同。旅游预算有如下规则：若油箱的油过半，不停车加油，除非油箱中的油不可支持到下一站；每次加油时都加满；在一个加油站加油时，司机要花费2元买东西吃；司机不必为其他意外情况而准备额外的油；汽车开出时在起点加满油箱；计算精确到分（1元=100分）。编写算法估计实际行驶在某路线所需的最小费用。Procedure LESTCOST(v,vm,f,n,S,FP,P)/共n个加油站，起点、加油站、和终点，分别编号为0,1,2.n,n+1，v为油箱容量，vm为每升油行驶的公里数，S为n个加油站和起点的距离，FP(1:n)为每个加油站的油价，P(1:n)为每次所停的加油站 integer n,P(1:n),N(1:n); float v,vm,f,S(1:n),FP(1:n),LEST(1:n); integer i,j,k; float vf; i=0;vf=0; LESTMAX LEST(0)f while in+1 do j=i+1 while jn+1 and S(j)-S(i)v*vm then jj-1; endif if j=i then print(不可能到达终点) return endif if j=n then /到达终点 continue; endif k=j; while jn+1 S(j)-S(i)=v*vm/油够到达该站并停车 vf=(S(j)-S(i)/vm/需要补充的汽油量 cost=LEST(i)+vf*FP(j)+2/在j站停车的最小血糖 if cost0 P(j-1)=F(P(j); j=P(j-1); enifenif本题的求解与求有向图的最短路径比较相似，也是选取两点间的直接连线费用和经过某个中间结点进行转折费用中的最小者。因此，