发布时间 : 2024/5/18 18:37:30 星期六 文章算法分析与设计复习题及参考答案更新完毕开始阅读13b82668abea998fcc22bcd126fff705cc175cff

else return BinarySearch(A,mid+1,right,v); } else return -1; } （4）搜索18：首先与27比较，18<27，在后半部分搜索；再次与18比较，搜索到，返回5。 搜索31：首先与27比较，31>27，在前半部分搜索；再次32比较，31<32，在后半部分搜索，与29比较，31>29，此时只有一个元素，未找到，返回-1。 搜索135：首先与27比较，135>27，在前半部分搜索；再次32比较，135>32，在前半部分搜索；与135比较，相同，返回0。

(k)A(a)krrrrrrr

，=1，2，3，4，5，6，=5，=10，=3，=12，=5，

=50，=6，求3.已知

矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步

骤）。123456解：使用动态规划算法进行求解。 求解矩阵为： 1 2 3 4 5 6 1 0 150 330 405 1655 2010 2 0 360 330 2430 1950 3 0 180 930 1770 4 0 3000 1860 5 0 1500 6 0 1 2 3 4 5 6 1 0 1 2 2 4 2 2 0 2 2 2 2 3 0 3 4 4 4 0 4 4 5 0 5 6 0 因此，最佳乘积序列为（AA）（（AA）（AA）），共执行乘法2010次。 1234564.根据分枝限界算法基本过程，求解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)=3，(4)＝28，U (4)＝28 ,

x(1)=2，(3)＝15，U(3)＝25, U=min{23,25,28}=23, 由于(4)

＝28>U 所以节点４删除。活节点表Ｌ={2,3}，取最小代价估值节点２作为扩展节点： x(2)=2，w1+w2>M，节点5是不合理节

点； x(2)=3，这是答案节点c(6)=13，即找到了代价为13的解，修改U＝13， c由于活节点表中的节点3有(3)＝25，所以节点3可以删除。 这时L＝｛ ｝，算法结束。最优解X={1,3} 搜索产生的状态空间树如下图： 1 X1=1 1 X1=3 X1=2

23 4 28 25 U=23 2 0 3 15 X2=2 X2=3 23 13 15 6 5 0 13 15 7 节点

6是答案节点

5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。 解：int greedy(vecterx,int n) { int sum=0,k=x.size(); for(int j=0;jn){ cout<<”No solution”<n){ sum++;s=x[i];} } 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++) d[i]=i; for(i=1;i<=m;i++){ int y=i-1; for(int j=1;j<=n;j++){ int x=y; y=d[j]; int z=j>1?d[j-1]:i; int del=a[i-1]= =b[j-1]?0:1; d[j]=min(x+del,y+1,z+1); } }

return d[n]; } 7、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

be2g

212ad323182cf2h 解：用V表示已经找到最短路径

的顶点，V表示与V中某个顶点相邻接且不在V中的顶点；E表示加入到12111最短路径中的边，E为与V中的顶点相邻接且距离最短的路径。 21步骤 V V E E 12121. {a} {b} {} {ab} 2. {a,b} {d} {ab} {bd} 3. {a,b,d} {c,f} {ab,bd} {dc,df} 4. {a,b,d,c} {f} {ab,bd} {df} 5. {a,b,c,d,f} {e} {ab,bd,dc,df} {fe} 6. {a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg} 7. {a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh} 8. {a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {} 结果：从a到h的最短路径为，权值为18。

求所有顶点对之间的

最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。 8、试写出用分治法对数组A[n]实现快速排序的算法。 解：用分治法求解的算法代码如下： int partition(float A[],int p,int r) { int i=p,j=r+1; float x=a[p]; while (1) { while(a[++i]x);

a[j]=x; return j; } void Quicksort( float a[],

int p, int r ) { if( p

}; Quicksort(a,0,n-1); 9、有n 个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，且

iiii

安排的活动数目最

多。 解：解决这个问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中元素的顺序按结束时间非减排列：

fn。算法如下： GreedyAction(s, f，n) // s[1:n]、f[1:n]分别代表n项活动的起始 //时间和结束时间, 并且满足j=1; solution={1}; //解向量初始化为空集

将j加入解中 j=i; endif

endfor return(solution); end Greedy xxx10、设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。 123123解：由于x1、x2、x3是三角形的三条边，从而xi+xj>xk，|xi-xj|