算法分析期末试题集答案(6套)1

《算法分析与设计》一、解答题1.机器调度问题。问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi，sifi。[si，fi]为处理任务i的时间范围。两个任务i，j重叠指两个任务的时间范围区间有重叠，而并非指i，j的起点或终点重合。例如：区间[1，4]与区间[2，4]重叠，而与[4，7]不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。问题实例：若任务占用的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）画出工作在对应的机器上的分配情况。2.已知非齐次递归方程：f(n)bf(n1)g(n)f(0)c，其中，b、c是常数，g(n)是n的某一个函数。则f(n)的非递归表达式为：nnnii1f(n)cbbg(i)。现有Hanoi塔问题的递归方程为：h(n)2h(n1)1h(1)1，求h(n)的非递归表达式。解：利用给出的关系式，此时有：b=2,c=1,g(n)=1,从n递推到1，有：n1n1n1ii1n1n22nh(n)cbbg(i)22...221213.单源最短路径的求解。问题的描述：给定带权有向图（如下图所示）G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。4.请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且121niiwcc。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。解：voidbacktrack(inti){//搜索第i层结点if(in)//到达叶结点更新最优解bestx,bestw;return;r-=w[i];if(cw+w[i]=c){//搜索左子树432110030maxint10-{1}初始dist[5]dist[4]dist[3]dist[2]uS迭代x[i]=1;cw+=w[i];backtrack(i+1);cw-=w[i];}if(cw+rbestw){x[i]=0;//搜索右子树backtrack(i+1);}r+=w[i];}5.用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。解答：斜线标识的部分完成的功能为：提前更新bestw值；这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r0故Ew+rbestw总是成立。也就是说，此时右子树测试不起作用。为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。//检查左儿子结点Typewt=Ew+w[i];//左儿子结点的重量if(wt=c){//可行结点if(wtbestw)bestw=wt;//加入活结点队列if(in)Q.Add(wt);}//检查右儿子结点if(Ew+rbestw&&in)Q.Add(Ew);//可能含最优解Q.Delete(Ew);//取下一扩展结点7.最长公共子序列问题：给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：00,0[][][1][1]1,0;max{[][1],[1][]},0;ijijijcijcijijxycijcijijxy在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。（1）请填写程序中的空格，以使函数LCSLength完成计算最优值的功能。（2）函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填写程序中的空格，以使函数LCS完成构造最长公共子序列的功能（请将b[i][j]的取值与（1）中您填写的取值对应，否则视为错误）。voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i=m;i++)c[i][0]=0;for(i=1;i=n;i++)c[0][i]=0;for(i=1;i=m;i++)for(j=1;j=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}8.对下面的递归算法，写出调用f(4)的执行结果。二、复杂性分析1、MERGESORT(low，high)iflowhigh；thenmid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifendMERGESORT答:1、递归方程设n=2k解递归方程：2、procedureS1(P，W，M，X，n)i←1;a←0voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1，j-1，x，b);coutx[i];}elseif(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);}voidf(intk){if(k0){printf(%d\n,k);f(k-1);f(k-1);}}1)2/(21)(ncnnTnanTncnankcnTcnnTcncnnTnTklog)1(22)4/(4)2/)4/(2(2)(whilei≤ndoifW(i)Mthenreturnendifa←a+ii←i+1;repeatend解：i←1;s←0时间为：O(1)whilei≤ndo循环n次循环体内所用时间为O(1)所以总时间为:T(n)=O(1)+nO(1)=O(n)3.procedurePARTITION(m,p)Integerm,p,i;globalA(m:p-1)v←A(m);i←mlooploopi←i+1untilA(i)≥vrepeatloopp←p-1untilA(p)≤vrepeatifipthencallINTERCHANGE(A(i),A(p))elseexitendifrepeatA(m)←A(p);A(p)←vEndPARTITION解：最多的查找次数是p-m+1次4.procedureF1(n)ifn2thenreturn(1)elsereturn(F2(2,n,1,1))endifendF1procedureF2(i,n,x,y)ifi≤nthencallF2(i+1,n,y,x+y)endifreturn(y)endF2解：F2（2，n,1,1）的时间复杂度为：T(n)=O(n-2);因为i≤n时要递归调用F2，一共是n-2次当n＝1时F1(n)的时间为O(1)当n1时F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为O(n)5.procedureMAX(A,n,j)xmax←A(1);j←1fori←2tondoifA(i)xmaxthenxmax←A(i);j←i;endifrepeatendMAX解：xmax←A(1);j←1时间为：O(1)fori←2tondo循环最多n-1次所以总时间为:T(n)=O(1)+(n-1)O(1)=O(n)6.procedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low←1;high←nwhilelow≤highdomid←|_(low+high)/2_|case:xA(mid):high←mid-1:xA(mid):low←mid+1:else:j←mid;returnendcaserepeatj←0endBINSRCH解：log2n+1三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。各边的代价如下：C(1,2)=3，C(1,3)=5，C(1,4)=2C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1C(5,8)=4，C(6,8)=5，C(7,8)=6解：Cost(4,8)=0Cost(3,7)=C(7,8)+0=6，D[5]=8Cost(3,6)=C(6，8)+0=5,D[6]=8Cost(3,5)=C(5，8)+0=4D[7]=851342678Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}=min{1+5,2+4}=6D[4]=6Cost(2,3)=min{C(3，6)+Cost(3,6)}=min{4+5}=9D[3]=5Cost(2,2)=min{C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}=min{8+5,4+6}=10D[2]=7Cost(1,1)=min{C(1,2)+Cost(2,2),C(1,3)+Cost(2,3),C(1,4)+Cost(2,4)}=min{3+10,5+9,2+6}=8D[1]=41→4→6→82、写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=(48,12,61,3,5,19,32,7)解：写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48～61,12～319～32，5～74、61～323～55、6133、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。A=(65,70,75,80,85,55,50,2)解：第一个分割元素为654、归并排序算法对下列实例排序，写出算法执行过程。A=(48,12,61,3,5,19,32,7)解：48,12,61,35,19,32,748,1261,35,1932,712,483,615,197,323,12,48,615,7,19，323,5,7,12，19，32，48,615、写出图着色问题的回溯算法的判断X[k]是否合理的过程。解：i←0whileikdoifG[k,i]=1andX[k]=X[i]thenreturnfalse(1)(2)(3)(4)(5)(6)(7)(8)ip6570758085555022865275808555507037652508085557570466525055858075704655707580856550