算法分析与设计部分含计算的复习题及参考答案.doc

1、二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。2.简述回溯法解题的主要步骤。3.简述动态规划算法求解的基本要素。4.简述回溯法的基本思想。5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划算法的异同。三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(1

2、5,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。2.按要求完成以下关于排序和查找的问题。对数组A=15，29，135，18，32，1，27，25，5，用快速排序方法将其排成递减序。请描述递减数组进行二分搜索的基本思想，并给出非递归算法。给出上述算法的递归算法。使用上述算法对所得到的结果搜索如下元素，并给出搜索过程：18，31，135。3.已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1A2A3A4A5A6的最佳求积顺序（要求给出计算步骤）。4.根据分枝限界算法基本过程,求解0-1背包问题

3、。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：删除一个字符。插入一个字符。将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。8.试写出用分治法对数组An实现快速排序的算法。9.有n

4、个活动争用一个活动室。已知活动i占用的时间区域为si，f i，活动i,j相容的条件是：sjf i，问题的解表示为(xi| xi =1，2，n,)，xi表示顺序为i的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。10.设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。11.设数组A有n个元素，需要找出其中的最大最小值。请给出一个解决方法，并分析其复杂性。把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方

5、法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。12.有n个程序和长度为L的磁带，程序i的长度为ai，已知，求最优解(xi，x2 ，.，xi， xn)，xi =0，1, xi =1，表示程序i存入磁带，xi =0，表示程序i不存入磁带，满足，且存放的程序数目最多。13.试用分治法实现有重复元素的排列问题：设是要进行排列的个元素，其中元素可能相同，试设计计算的所有不同排列的算法。14.试用动态规划算法实现0-1闭包问题，请写出该算法。15.试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，请

6、写出该算法。16.试写出用分治法对一个有序表实现二分搜索的算法。17.试用动态规划算法实现最长公共子序列问题，请写出该算法。18.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包问题，请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值1040305035403019.求解子集和问题：对于集合S=1，2 ，6，8，求子集，要求该子集的元素之和d=9。画出子集和问题的解空间树；该树运用回溯算法，写出依回溯算法遍历节点的顺序；如果S中有n个元素，指定d，用伪代码描述求解子集和问题的回溯算法。20.求解填字游戏问题

7、：在33个方格的方阵中要填入数字1到N（N10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一种数字填法的算法和满足这个要求的全部数字填法的算法。21.试用动态规划算法实现最大子矩阵和问题：求矩阵A的一个子矩阵，使其各元素之和为最大。22.试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：。对于给定的两个整数和，要求用最少的变换和变换次数将变为。23.关于15谜问题。在一个44的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规

8、则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。124563791012813141115123456789101112131415 初始状态 目标状态二、简答题：1.备忘录方法和动态规划算法相比有何异同？简述之。备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。

9、备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。2.简述回溯法解题的主要步骤。回溯法解题的主要步骤包括：1）针对所给问题，定义问题的解空间；2）确定易于搜索的解空间结构；3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。3.简述动态规划算法求解的基本要素。动态规划算法求解的基本要素包括：1）最优子结构是问题能用动态规划算法求解的前提；2）动态规划算法

10、，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。4.简述回溯法的基本思想。回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。将递归算法转化为非递归算法的方法主要有：1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上

11、还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2）用递推来实现递归函数。3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。6.简要分析分支限界法与回溯法的异同。1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个

12、方面？算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。算法复杂性度量主要包括算法的时间复杂性和算法的空间复杂性。8.贪心算法求解的问题主要具有哪些性质？简述之。贪心算法求解的问题一般具有二个重要的性质：一是贪心选择性质，这是贪心算法可行的第一个基本要素；另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。9.分治法的基本

13、思想是什么？合并排序的基本思想是什么？请分别简述之。分治法的基本思想：将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1kn，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。合并排序基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。10.简述分析贪心算法与动态规划算法的异同。贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择

14、就将所求问题简化为规模更小的子问题。三、算法编写及算法应用分析题：1.已知有3个物品：(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10), 背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。解：根据递推式 fi（X）maxfi-1(X)，fi-l(Xwi)+pi |Xwi 从i=1开始，最后得到fn（M）f1(1) f1(11)= 0 f1(12) f1(20)= p1=15f2(1) f2(9)= 0f2(10) f2(11)= maxf1(10)，f1(10 w2)+p2 =13f2(12) f2(20)= maxf1(12)，f1(12 w

15、2)+p2=15f3(20)=maxf2(20)，f2(20 w3)+p3 = f2(20 6)+10=25可获得的最大利润为25，最优解为：（1，0，1）2.按要求完成以下关于排序和查找的问题。（1） 对数组A=15，29，135，18，32，1，27，25，5，用快速排序方法将其排成递减序。（2） 请描述递减数组进行二分搜索的基本思想，并给出非递归算法。（3） 给出上述算法的递归算法。（4） 使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。解：（1）第一步：15 29 135 18 32 1 27 25 5 第二步：29 135 18 32 27 25 1

16、5 1 5 第三步：135 32 29 18 27 25 15 5 1 第四步：135 32 29 27 25 18 15 5 1 （2）基本思想：首先将待搜索元素v与数组的中间元素进行比较，如果，则在前半部分元素中搜索v；若，则搜索成功；否则在后半部分数组中搜索v。非递归算法：输入：递减数组Aleft:right，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：【3分】int BinarySearch(int A,int left,int right,int v)int mid;while (leftAmid) right=mid-1;else left=mid+

17、1;return -1;（3）递归算法：输入：递减数组Aleft:right，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：int BinarySearch(int A,int left,int right,int v)int mid;if (leftAmid) return BinarySearch(A,left,mid-1,v);else return BinarySearch(A,mid+1,right,v);elsereturn -1;（4）搜索18：首先与27比较，1827，在前半部分搜索；再次32比较，3129，此时只有一个元素，未找到，返回-1。 搜

18、索135：首先与27比较，13527，在前半部分搜索；再次32比较，13532，在前半部分搜索；与135比较，相同，返回0。3.已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1A2A3A4A5A6的最佳求积顺序（要求给出计算步骤）。解：使用动态规划算法进行求解。求解矩阵为：12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘积序列为（A1A2）（A3A4

19、）（A5A6），共执行乘法2010次。4.根据分枝限界算法基本过程，求解0-1背包问题。已知，n=3，M=20，(w1,w2,w3)=(12,10,6), (p1,p2,p3)=(15,13,10)。解：用x(i)表示第i步选择的物品号， x(1)=1，()0，U(2)23 ;x(1)=2，(3)15，U(3)25, x(1)=3，(4)28，U (4)28 , U=min23,25,28=23, 由于(4)28U 所以节点删除。活节点表=2,3，取最小代价估值节点作为扩展节点：x(2)=2，w1+w2M，节点5是不合理节点；x(2)=3，这是答案节点c(6)=13，即找到了代价为13的解，修

20、改U13，由于活节点表中的节点3有(3)25，所以节点3可以删除。这时L ，算法结束。最优解X=1,3搜索产生的状态空间树如下图：12561230251528U=23734X1=1X1=2X2=3X1=3X2=223013131515节点6是答案节点5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。解：int greedy(vecterx,int n) int sum=0,k=x.size();for(int j=0;jn) cout”No solution”endl; re

21、turn -1; for(int i=0,s=0;in) sum+;s=xi; return sum; 6、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：(1)删除一个字符。(2)插入一个字符。(3)将一个字符改为另一个字符。请写出该算法。解：此题用动态规划算法求解：int dist( ) int m=a.size( ); int n=b.size( ); vectord(n+1,0); for(int i=1;i=n;i+) di=i; for(i=1;i=m;i+) int y=i-1; for(int j=1

22、;j1?dj-1:i; int del=ai-1= =bj-1?0:1; dj=min(x+del,y+1,z+1); return dn; 7、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。解：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。步骤 V1 V2 E1 E21. ab ab2. a,bd ab bd3. a,b,d c,f ab,bd dc,df4. a,b,d,c f ab,bd df5. a,b,c,d,f e ab,bd,dc,df fe6. a,b

23、,c,d,e,fg ab,bd,dc,df,fe eg7. a,b,c,d,e,f,gh ab,bd,dc,df,fe,eggh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 结果：从a到h的最短路径为，权值为18。求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。8、试写出用分治法对数组An实现快速排序的算法。解：用分治法求解的算法代码如下： int partition(float A,int p,int r) int i=p,j=r+1; float x

24、=ap; while (1) while(a+ix); if(i=j) break; ai ; ap=aj; aj=x; return j; void Quicksort( float a, int p, int r ) if( pxk，|xi-xj|xk，（i,j,k=1,2,3），根据x1+x2+x3=14可知1xi7（i=1,2,3）。利用回溯法求解得到：即有4个可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。11、设数组A有n个元素，需要找出其中的最大最小值。（1） 请给出一个解决方法，并分析其复杂性。（2） 把n个元素等分为两组A1和A2，分别求这两组的最大值

25、和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。解：（1）基本思想：从头到尾逐个扫描，纪录最大和最小元素。输入：具有n个元素的数组输出：最大值和最小值步骤：void FindMaxMin(int A, int n, int max, int min)max=min=A0;for (i=1;imax) max=Ai;if (Aimin) min=Ai;复杂性分析：由于是从头到尾扫描各个元素，而每个元素都要与max

26、和min比较一遍，从而时间复杂性为：O(n)。（2）void FindMaxMin(int left,int right, int max, int min)if (left=right) max=min=Aleft;else if (left=right-1)max=(AleftAright?Aright:Aleft);min=( AleftAright?Aleft:Aright);elsemid=(left+right)/2;FindMaxMin(left,mid,gmax,gmin);FindMaxMin(mid+1,right,hmax,hmin);max=(gmaxhmax?hmax

27、:gmax);min=(gminhmin?gmin:hmin);12、有n个程序和长度为L的磁带，程序i的长度为ai，已知，求最优解(xi，x2 ，.，xi， xn)，xi =0，1, xi =1，表示程序i存入磁带，xi =0，表示程序i不存入磁带，满足，且存放的程序数目最多。解：由于目标是存放的程序数目最多，所以最优量度应该是minai | ai为程序i的长度，即每次选入的程序都是当前最短的。我们可以将n个程序按a1a2an顺序排序，然后从i=1开始依次选择。算法如下：procedure programming(L,n, a, x)begin /n个程序按a1a2an顺序排序x0; i=1

28、; while (ai L and in) do xi 1; LL-ai；ii+ 1; end.13、试用分治法实现有重复元素的排列问题：设是要进行排列的个元素，其中元素可能相同，试设计计算的所有不同排列的算法。解：解答如下： Templatevoid Perm(Type list,int k,int m) if(k= =m) for(int i=0;i=m;i+) coutlisti; 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)

29、; ; 其中ok用于判别重复元素。 Template int ok(Type list,int k,int i) if(ik) for(int t=k;tI;t+) if(listt= =listi) return 0; return 1;14、试用动态规划算法实现0-1闭包问题，请写出该算法。解：解答如下：Templatevoid Knapsack(Type v,int w,int c,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);

30、 for(int j=0;j=jMax;j+) mij=mi+1j; for(int j=wi;j=w1) m1c=max(m1c,m2c-w1+v1); TemplateVoid Traceback(Type *m,int w,int c,int n,int x) for(int i=1;in;i+) if(mic= =mi+1c) xi=0; else xi=1,c-=wi;xn=(mnc)?1:0;15、试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，请写出该算法。解：解答如下：void dicomp(int n,int a) k=1;if(

31、n3) a1=0;return;if(nak) k+; ak=ak-1+1; n-=ak;if(n= =ak) ak+;n-;for(int i=0;in;i+) ak-i+;16、试写出用分治法对一个有序表实现二分搜索的算法。解：解答如下： Template int BinarySearch(Type a,const Type& x,int n)/假定数组a已按非递减有序排列，本算法找到x后返回其在数组a中的位置，/否则返回-1 int left=0,right=n-1; while(leftamiddle) left=middle+1; else right=middle-1;return

32、 -1;17、试用动态规划算法实现最长公共子序列问题，请写出该算法。解：用动态规划算法求解的算法代码如下： int lcs_len(char *a,char *b,int cN) int m=strlen(a),n=strlen(b),i,j; for(i=0;i=m;i+) ci0=0; for(j=1;j=n;j+) c0j=0; for(i=1;i=m;i+) for(j=1;j=cij-1) cij=ci-1j; else cij=cij-1; return cmn; ; char *build_lcs(char s,char *a,char *b) int k,i=strlen(a)

33、,j=strlen(b),cNN; k=lcs_len(a,b,c); sk=0; while(k0) if(cij= =ci-1j) i-; else if(cij= =cij-1) j-; else s-k=ai-1; i-,j-; return s; 18、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包问题，请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值10403050354030解：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为17。则可生产如下的状态空间搜索树

34、。其中各个节点处的限界函数值通过如下方式求得：a b. c d. e. f. g. h. i.j. 在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。19、求解子集和问题：对于集合S=1，2 ，6，8，求子集，要求该子集的元素之和d=9。画出子集和问题的解空间树；该树运用回溯算法，写出依回溯算法遍历节点的顺序； 如果S中有n个元素，指定d，用伪代码描述求解子集和问题的回溯算法。解答：满足要求的子集有1，2，6， 1，8解空间树如下：R1P1T1X1V11Z11U0S0W0Y0000Q0遍历结点的顺序为：A B D H P Q I R S E J T U K V W C F L X Y M Z G N O 用伪代码描述算法如下：#include#define N 100int as=0,t=0;int sum;void backtrackiter(int i,int s,int n,int d,