算法分析期末考试集答案

1、算法分析与设计?一、 解答题1. 机器调度问题。问题描述：现在有 n 件任务和无限多台的机器，任务可以在机器上得到 处理。每件任务的开始时间为Si，完成时间为f i, SiVfi。s i, fi为处理任 务 i 的时间范围。两个任务 i ， j 重叠指两个任务的时间范围区间有重叠， 而并非指 i, j 的起点或终点重合。例如：区间 1, 4与区间2, 4重叠, 而与4, 7不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务 分配给同一台机器。因此,在可行的分配中每台机器在任何时刻最多只处理 一个任务。最优分配是指使用的机器最少的可行分配方案。问题实例：假设任务占用的时间范围是 1 , 4

2、, 2, 5, 4, 5, 2, 6, 4, 7 ,那么按时完成所有任务最少需要几台机器？(提示：使用贪心 算法)画出工作在对应的机器上的分配情况。2. 非齐次递归方程：f(n) bf(n 1) g(n)，其中，b、c是常数，g(n)f (0) cn是 n 的某一个函数。那么 f(n) 的非递归表达式为： f(n) cbnbn ig(i) 。i1现有Hanoi塔问题的递归方程为：h(n) 2h(n 1) 1，求h(n)的非递归表 h(1) 1达式。解：禾U用给出的关系式，此时有：b=2, c=1, g(n)=1,从n递推到1，有：n1 h(n) cbn 1bn1 ig(i)i1n 1 n 22

3、2n 1 2n 2 . 22 2 1n2n 13. 单源最短路径的求解。问题的描述：给定带权有向图(如以下图所示)G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它 各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单 源最短路径问题解法：现采用Dijkstra 算法计算从源顶点1到其它顶点间最短路径。请将 此过程填入下表中。迭代Sudist2dist3dist4dist5初始1-10maxi nt3010012344. 请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为cl和c2的轮船，n

4、Wi C1 C2其中集装箱i的重量为wi，且i 1。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。解: void backtrack (int i)用分支限界法解装载问题时，对算法进行了一些改良，下面的程序段给出了 改良局部；试说明斜线局部完成什么功能，以及这样做的原因，即采用这样的方 式，算法在执行上有什么不同。/检查左儿子结点Type wt = Ew + wi; /左儿子结点的重量if (wt bestw) bestw = wt;/参加活结点队列if (i bestw & i 0故Ew+rbestw总是成立。也就 是说，此时右子树测试不起

5、作用。为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新 bestw的值。7.最长公共子序列问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn ， 找出X和丫的最长公共子序列。由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列Xi和Yj的最长公共子序列的长度。其中，Xi=x1,x2,xi ; Yj=y1,y2,yj。当 i=0 或 j=0 时，空序列是 Xi 和 Yj 的最长公共子序列。故此时Cij

6、=0 。其它情况下，由最优子结构性质可建立0i 0,j 0递归关系如下：ci jci 1j 1 1i, j 0;xi ymaxcij 1,ci1j i,j 0必 在程序中，bij 记录Cij的值是由哪一个子问题的解得到的。(1)请填写程序中的空格，以使函数LCSLe ngth完成计算最优值的功能。void LCSLength(int m , int n , char *x , char *y , int *c, int *b)int i , j；for (i = 1; i = m; i+) ci0 = 0;for (i = 1; i = n; i+) c0i = 0;for (i = 1; i

7、 = m; i+)for (j = 1; j =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3;(2)函数LCS实现根据b的内容打印出Xi和Yj的最长公共子序列。请填 写程序中的空格，以使函数LCS完成构造最长公共子序列的功能(请 将bij的取值与(1)中您填写的取值对应，否那么视为错误)。void LCSint i，int j ，char *x，int *b)if (i =0 | j=0) retur n;if (bij= 1) LCS( i-1，j-1，x, b); cout0 ) printf(%dn ,k);f(k-1);f(k-1);、复杂

8、性分析1、MERGESORT(lo，w high) if lowhigh ；then midJ (low , high)/2 ;MERGESORT(low ， mid) ；MERGESORT(mid+1 ， high) ；MERGE(low ， mid， high) ； endifend MERGESORT 答: 1 、 递归方程T(n)设 n=2k 解递归方程：2T(n/2) cn n 1T(n) 2(2T(n/4) cn/2)4T(n/4) 2cncn2k T(1) kcn an cnlogn2、procedure S1(P ， W， M， X， n)i J 1; a J 0while i

9、 M then return endifaJ a+iiJ i+1 ;repeatend解： i J 1 ;s J 0 时间为： O(1) while i v repeatloop p j p-1 until A(p)w v repeatif ipthen call INTERCHANGE(A(i),A(p)else exitendifrepeatA(m)jA(p);A(p)jvEnd PARTITION 解：最多的查找次数是 p-m+1 次F1(n)if n1 时 F1(n) 的时间复杂度与 F2(2,n,1,1) 的时间复杂度相同即为为MAX(A,n,j)xmax jA(1);j j1jA(

10、i); j ji;endif时间为： O(1)循环最多 n-1 次for ij 2 to n doif A(i)xmax then xmax repeat end MAX解：xmaxJ A(1);j j 1 for ij 2 to n do所以 总时间为 :T(n)=O(1)+ (n-1)O(1)= O(n)BINSRCH(A,n,x,j)integer low,high,mid,j,n;low j1;high jnwhile loww high domidj|_(low+high)/2 _|case:xA(mid):low J mid+1:else:j j mid; returnendcas

11、e repeat j J 0 end BINSRCH解: log n+1三、算法理解1、写出多段图最短路经动态规划算法求解以下实例的过程，并求出最优值。C(1,2)=3， C(1,3)=5C(2,6)=8，C(2,7)=4C(5,8)=4， C(6,8)=5 解：Cost(4,8)=0Cost(3,7)= C(7,8)+0=6Cost(3,6)= C(6，C(1,4)=2，C(3,5)=5，C(3,6)=4，C(7,8)=6,C(4,5)=2 ，C(4,6)=1，D5=88)+0=5, D6=8Cost(3,5)= C(5，8)+0=4 D7=8，5)+ Cost(3,5)，7)+ Cost(

12、3,7)Cost(2,4)= minC(4， 6)+ Cost(3,6), C(4=mi n1+ 5, 2+4=6 D4=6Cost(2,3)= minC(3，6)+ Cost(3,6) =mi n4+5=9 D3=5Cost(2,2)= minC(2，6)+ Cost(3,6), C(2=min 8+5, 4+6=10 D2=7Cost(1,1)= mi nC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)=min 3+10, 5+9,2+6= 8D1=41 t82、写出maxmin算法对以下实例中找最大数和最小数的过程。 数组 A

13、=(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, 123 1932, 574、61 32355、61 3次被分割的过程。3、快速排序算法对以下实例排序，算法执行过程中，写出数组A第A=(65,70,75,80,85,55,50,2)解：第一个分割元素为65(1) (2) (3) (4)(6)(8) i p65707580855550228652758085555070376525080855575704665250558580

14、7570465570758085655024、 归并排序算法对以下实例排序，写出算法执行过程。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、 写出图着色问题的回溯算法的判断Xk是否合理的过程。解：i 0while i P(i+1)/W(i+1) 的顺序。CU 25,X 0W1 CU: x1 1; CU CU-W1=13;W2CU: x3 CU/ W3=3/8;实例的解为：(1 , 1, 3/8

15、 , 0)11、有一个有序表为1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，当使用二分 查找值为82的结点时，经过多少次比拟后查找成功并给出过程。解：有一个有序表为1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，当使用二分 查找值为82的结点时，经过多少次比拟后查找成功并给出过程。一共要要执行四次才能找到值为82的数。12、使用prim算法构造出如以下图 G的一棵最小生成树。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=

16、5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6 解：使用普里姆算法构造出如以下图G的一棵最小生成树。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=613、有如下函数说明int f(int x,i nt y)f=x Mod y +1;后，k的值是多少并写出详细过程。后，k的值是多少并写出详细过程。 a=10,b=4,c=5 那么执行

17、 k=f(f(a+c,b),f(b,c)解：有如下函数说明int f(int x,i nt y)f=x Mod y +1; a=10,b=4,c=5 那么执行 k=f(f(a+c,b),f(b,c) K的值是5 14、McCathy函数定义如下： 当 x100 时 m(x)=x-10;当 x100 时 m(x)=x-10;当 x100) return(x-IOO);elsey=m(x+11);return (m(y); 15、设计一个算法在一个向量A中找出最大数和最小数的元素。解：设计一个算法在一个向量A中找出最大数和最小数的元素。Void maxmi n(A,n)Vector A;int n

18、;int max,mi n,i;max=A1;mi n=A1;for(i=2;imax)max=Ai; else if(Ai t2 tn排序2) S1:m清零j - 0设有n种面值为：d1 d2 dn的钱币，需要找零钱M,如何选择钱币dk，的数目兀，满足d1X X +dnX % M，使得X +最小请选择贪心策略，并设计贪心算法。 解：贪心原那么：每次选择最大面值硬币。CU- M;i - 1;X- 0有 n 个物品，n=7,利润为 P=(10,5,15,7,6,18,3) ，重量W=(2,3,5,7,1,4,1)，背包容积 M=15,物品只能选择全部装入背包或不装入背包，设计贪心 算法，并讨论是

19、否可获最优解。解：定义结构体数组 G,将物品编号、利润、重量作为一个结构体：例如 Gk=1,10,2 求最优解，按利润/重量的递减序，有5,6,1,6 1,10,2,56,18,4,9/2 3,15,5,3 7,3,1,32,5,3,5/3 4,7,7,1算法procedure KNAPSACK(P , W M X n)设计只求一个哈密顿环的回溯算法。解： Hamiltonian(n)k 1; xk 0;While k0 doxk xk+1;while B(k)=false and xk n doxk xk+1; repeatIf xk n thenif k=n then print x; r

20、eturnelse k k+1; xk 0; endifelse k k-1endifrepeatendprocedure B(k) Gxk-1,xk 丰 1 then return false;for i 1 to k-1 doif xi=xk then return false;endifrepeatreturn true;5利用对称性设计算法，求n 为偶数的皇后问题所有解。解：利用对称性设计算法，求 n 为偶数的皇后问题所有解。procedure NQUEENS1(n)0log n 5;(100n2)a2f(n) (g(n) f (n) (g(n) f(n) log n2;g(n) f(

21、n) 2n;g(n) 100n2; f(n) 2n;g(n) 3n; logn2(log n 5) 2n2n(3n) R r1,r2,.,rn) n r1,r2,.,rn R(4 分)coutendl;else for(int i=k;i=m;i+)if(ok(list,k,i)swap(listk,listi);Perm(list,k+1,m);swap(listk,listi); .( 8 分);其中 ok 用于判别重复元素。Templateint ok(Type list,int k,int i)if(ik)for(int t=k;tI;t+)if(listt= =listi) retu

22、rn 0;return 1; .( 13 分)3、试用分治法对一个有序表实现二分搜索算法。 (12 分)解：解答如下：Templateint BinarySearch(Type a,const Type& x,int n) (4 分)if(x= =amiddle) return middle+1;if(xamiddle) left=middle+1; . ( 8 分)else right=middle-1;return -1; .( 12 分)4、试用动态规划算法实现 0-1 闭包问题。(15 分)解：解答如下：Templatevoid Knapsack(Type v,int w,int c,

23、int n,Type *m)Int jMax=min(wn-1,c);for(int j=0;j=jMax;j+) mnj=0;for(int j=wn;j1;i-)jMax=min(wi-1,c);for(int j=0;j=jMax;j+) mij=mi+1j;for(intj=wi;j=w1) m1c=max(m1c,m2c-w1+v1); ( 10 分)TemplateVoid Traceback(Type *m,int w,int c,int n,int x)for(int i=1;in;i+)ifmic= =mi+1c xi=0; 12 分else xi=1,c-=wi;xn=mn

24、c?1:0; .15 分5、试用贪心算法求解以下问题：将正整数 n 分解为假设干个互不相同的自然数之 和，使这些自然数的乘积最大。 15 分解：解答如下：void dicomp(int n,int a)k=1;if(n3) a1=0;return;if(nak)k+;ak=ak-1+1;n-=ak; .( 10 分)if(n= =ak) ak+;n-;for(int i=0;in;i+) ak-i+; .( 15 分)6试用动态规划算法实现最大子矩阵和问题：求m n矩阵A的一个子矩阵，使其各元素之各为最大。 (15 分)解：解答如下：int MaxSum2(int m,int n,int *a

25、)int sum=0;int *b=new intn+1;for(int i=1;i=m;i+)for(int k=1;k=n;k+) bk=O; . ( 5分)for(int j=i;j=m;j+)for(int k=1;ksum) sum=max;return sum; .( 10 分)int MaxSum(int n,int *a)int sum=0,b=0;for(int i=1;i0) b+=ai;else b=ai;if(bsum) sum=b;Return sum; . ( 15 分)7、试用回溯法解决以下整数变换问题：关于整数i 的变换 f 和 g 定义如下：f(i) 3i;g

26、(i)i/2。对于给定的两个整数n和m,要求用最少的变换f和g变换次数将 n 变为 m 。(18 分)解：解答如下：void compute。k=1;while(!search(1,n)k+;if(kmaxdep) break;init();； .( 6 分)if(found) output();else coutNo Solution! k) return false；12分)for(int i=0；i2；i+)int n1=f(n,i)；tdep=i；if(n1= =m|search(dep+1,n1)Found=true；Out()；return true；return false; .

27、( 18 分)一、排序和查找是经常遇到的问题。按照要求完成以下各题：(20 分)(1) 对数组 A=15, 29, 135, 18, 32, 1 , 27, 25, 5，用快速排序方法将其排成递减序。2) 请描述递减数组进行二分搜索的根本思想，并给出非递归算法。3) 给出上述算法的递归算法。4) 使用上述算法对( 1)所得到的结果搜索如下元素，并给出搜索过程：18，31，答案：( 1 )第一步： 15 29 135 18 32 1 27 25 5第二步： 29 135 18 32 272515 1 5【 1分】第三步： 135 32 29 18 272515 5 1【 1分】第四步： 135

28、32 29 27 251815 5 1【 1分】(2) 根本思想：首先将待搜索元素v与数组的中间元素A n进行比拟，如果v A -,2 2那么在前半局部元素中搜索v ;假设v A n，那么搜索成功；否那么在后半局部数组中搜索v。【22分】非递归算法：输入：递减数组 Aleft:right，待搜索元素V。【1分】输出：v在A中的位置pos，或者不在A中的消息(-1 )。【1分】步骤：【3分】int Bin arySearch(i nt A,i nt left,i nt right, int v)int mid;while (leftAmid) right=mid-1;else left=mid+

29、1;return -1;(3) 递归算法：输入：递减数组 Aleft:right，待搜索元素V。【1分】输出：v在A中的位置pos，或者不在A中的消息(-1 )。【1分】步骤：【3分】int Bin arySearch(i nt A,i nt left,i nt right, int v)int mid;if (leftAmid) retur n Bin arySearch(A,left,mid-1,v);else return Bin arySearch(A,mid+1,right,v);elsereturn -1;(4) 搜索18：首先与27比拟，1827,在前半局部搜索；再次 32比拟，

30、3129，此时只有一个元素，未找到，返回-1。【2分】搜索135:首先与27比拟，13527,在前半局部搜索；再次 32比拟，13532，在前 半局部搜索；与135比拟，相同，返回 0。【2分】二、对于以下图使用 Dijkstra 算法求由顶点a到顶点h的最短路径。20分。答案：用Vi表示已经找到最短路径的顶点，V2表示与Vi中某个顶点相邻接且不在 V中的顶点；E表示参加到最短路径中的边，E2为与Vi中的顶点相邻接且距离最短的路径。【1分】步骤V 1V2 E1E21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,fea

31、b,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 【以上每步2分】结果:从a到h的最短路径为a b d f e gh ,权值为18。【1分】三假设有7个物品，它们的重量和价值如下表所示。假设这些物品均不能被分割，且背包容量 W 150，使用回溯方法求解此背包问题。请写出状态空间搜索树20分。物品ABC重量353060价值104030DEFG5040102550354030答案：求所有顶点对之间的最短路径可以使用Di

32、jkstra 算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】三、按照单位效益从大到小依次排列这 7个物品为：FBGDECA将它们的序号分别记为 17。 那么可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】X7X21X2X41aX4xiQidgX3X,0【状态空间搜索树及其计算过程17分，每个节点1分】a.404030503540190.625(1,1,1,1-,0,0)8150 11574040305030177.5 (1,1,1,1,0,0)60124040305010170(1,1,1,

33、1,0,0,1)150 10534040303530167.5(1,1,1,0,1,_,0)604150 13014040503530175(1,1,0,1,10)60315013040405035 1035170.71(1,1,0,1,1,0石)150115b.c.d.e.f.(1,1,0,1,0,1,0)g.4040 50 30160h.4040 35 30 10 150 140146.8535(1,1,0,0,1,1,|)i.150 125u40 30 50 35 30 167.5(何乙诗,。)60j.15014540 30 50 35 30157.5(0,1,111丄,0)1260在Q

34、处获得该问题的最优解为1,1,1,1,0,0,1,背包效益为170。即在背包中装入物品G D、A时到达最大效益，为170,重量为150。【结论2分】 Ak(aij(k)n*r11，k=1， 2， 3， 4， 5， 6，1=5，2=10，3=3，r4=12， r5=5, r6=50，7=6，求矩阵链积 AX A.X AX AX A5X A的最正确求积顺序。要求：给出计算步骤20分 答案：使用动态规划算法进行求解。求解矩阵为：【每个矩阵18分】123456101503304051655202120360330243019503018093017704030001860501500601234561

35、012420222230p4440445060因此，最正确乘积序歹y 为(AA2)(氏A (AA6),共执行乘法2021次。【结论2分】七、算法设计题(此题10分)通过键盘输入一个高精度的正整数n(n的有效位数w 240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。【样例输入】178543S=4【样例输出】13六、算法设计题(此题15分)(1) 贪心算法 O (nlog (n)首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。假设将这种物品全部装入

36、背包后，背包内的物品 总重量未超过 C,那么选择单位重量价值次高的物品并尽可能多地装入背包。依此策 略一直地进行下去，直到背包装满为止。具体算法可描述如下：void Knapsack(int n,float M,float v,float w,float x)Sort( n,v,w);int i;for (i=1;i=n ;i+) xi=0;float c=M;for (i=1;ic) break;xi=1; c-=wi;if (i=n) xi=c/wi;(2) 动态规划法 0( nc)m(i , j)是背包容量为j，可选择物品为i , i+1 ,，n时0-1背包问题的最优值。由 0-1背包问

37、题的最优子结构性质，可以建立计算m(i , j)的递归式如下。m()maxm(i 1，j)，m(i 1，j w Vij Wim(i 1,j)0 j Wim(n, j)VnWnWnvoid KnapSack(int v,int w,int c,int n,int m11) int jMax=mi n(w n-1,c);for (j=O;j=jMax;j+) /*m(n,j)=0 0=jwn*/ m nj=O;for (j=w n ;j=w n*/ m nj=v n ;for (i=n-1;i1;i-) int jMax=mi n(wi-1,c);for (j=0;j=jMax;j+) /*m(i,j)=m(i+1,j) 0=jwi*/ mij=mi+1j;for (j=wi;j=w n*/ mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c=w1) m1c=max(m1c,m2c-w1+v1