文档文库
手机版
投诉建议
热门搜索： 心得体会 演讲稿 思想汇报
首页 > 算法分析与设计复习题及参考答案

算法分析与设计复习题及参考答案

发布时间：   来源：文档文库   
小 中 大
字号：
手机查看
网络教育课程考试复习题及参考答案
算法分析与设计
一、名词解释：
1.算法2.程序
3.递归函数4.子问题的重叠性质5.队列式分支限界法6.多机调度问题7.最小生成树二、简答题：
1.备忘录方法和动态规划算法相比有何异同？简述之。2.简述回溯法解题的主要步骤。
3.简述动态规划算法求解的基本要素。4.简述回溯法的基本思想。
5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。6.简要分析分支限界法与回溯法的异同。
7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。
9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划算法的异同。三、算法编写及算法应用分析题：
1.已知有3个物品：(w1,w2,w3=(12,10,6,(p1,p2,p3=(15,13,10,背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。
2.按要求完成以下关于排序和查找的问题。
①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。
④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。
(k
3.已知kijri*ri1，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，
A(a
求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序（要求给出计算步骤）。4.根据分枝限界算法基本过程,求解0-1背包问题。
已知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的最短路径。
b
e
2
g
2
1
2
ad
3
2
3
1
8
2
c
f2h


8.试写出用分治法对数组A[n]实现快速排序的算法。
9.有n个活动争用一个活动室。已知活动i占用的时间区域为[si，fi]，活动i,j相容的条件是：sj≥fi，问题的解表示为(xi|xi=1，2…，n,，xi表示顺序为i的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。
10.设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。11.设数组A有n个元素，需要找出其中的最大最小值。①请给出一个解决方法，并分析其复杂性。
②把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。12.有n个程序和长度为L的磁带，程序i的长度为ai，已知
a
i1
n
i
L，求最优解(xi，x2，...，xi，…，
xn，xi=0，1,xi=1，表示程序i存入磁带，xi=0，表示程序i不存入磁带，满足存放的程序数目最多。
xa
ii1
n
i
L，且
13.试用分治法实现有重复元素的排列问题：设R{r1,r2,...,rn是要进行排列的n个元素，其中元素
r1,r2,...,rn可能相同，试设计计算R的所有不同排列的算法。
14.试用动态规划算法实现0-1闭包问题，请写出该算法。
15.试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，请写出该算法。
16.试写出用分治法对一个有序表实现二分搜索的算法。
17.试用动态规划算法实现最长公共子序列问题，请写出该算法。
18.假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题，请写出状态空间搜索树。
物品A
B
C
D
E
F
G
重量35306050401025价值10403050354030

19.求解子集和问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之和d=9。①画出子集和问题的解空间树；
②该树运用回溯算法，写出依回溯算法遍历节点的顺序；
③如果S中有n个元素，指定d，用伪代码描述求解子集和问题的回溯算法。
20.求解填字游戏问题：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一种数字填法的算法和满足这个要求的全部数字填法的算法。
21.试用动态规划算法实现最大子矩阵和问题：求mn矩阵A的一个子矩阵，使其各元素之和为最大。22.试用回溯法解决下列整数变换问题：关于整数i的变换f和g定义如下：f(i3i;g(ii/2。对于给定的两个整数n和m，要求用最少的变换f和g变换次数将n变为m。
23.关于15谜问题。在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效

的移动，设计了估值函数C1(x，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。
请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。1
24

5637

910128

13141115
初始状态
12345
6
7
8
9101112131415

目标状态

参考答案
一、名词解释：
1.算法：算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入；（2）输出：算法产生至少一个量作为输出；（3）确定性：组成算法的每条指令清晰、无歧义；（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。
2.程序：程序是算法用某种程序设计语言的具体实现。3.递归函数：用函数自身给出定义的函数称为递归函数。
4.子问题的重叠性质：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次，这种性质称为子问题的重叠性质。
5.队列式分支限界法：队列式(FIFO分支限界法是将活结点表组织成一个队列，并按照队列的先进先出（FIFO）原则选取下一个结点为扩展结点。
6.多机调度问题：多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。同时约定每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
7.最小生成树：G=(V,E是无向连通带权图，G的子图称为G的生成树，生成树上各边权的总和称为该生成树的耗费，在G的所有生成树中，耗费最小的生成树称为G的最小生成树。二、简答题：
1.备忘录方法和动态规划算法相比有何异同？简述之。
备忘录方法是动态规划算法的变形。与动态规划算法一样，备忘录方法用表格保存已解决的子问题的答案，在下次需要解此问题时，只要简单地查看该子问题的解答，而不必重新计算。
备忘录方法与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同的子问题的重复求解，而直接递归方法没有此功能。
2.简述回溯法解题的主要步骤。回溯法解题的主要步骤包括：
1）针对所给问题，定义问题的解空间；2）确定易于搜索的解空间结构；
3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。3.简述动态规划算法求解的基本要素。动态规划算法求解的基本要素包括：
1）最优子结构是问题能用动态规划算法求解的前提；
2）动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果，即重叠子问题。4.简述回溯法的基本思想。
回溯法的基本做法是搜索，在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。将递归算法转化为非递归算法的方法主要有：
1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2）用递推来实现递归函数。
3）通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。6.简要分析分支限界法与回溯法的异同。
1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标

则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？
算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A。
算法复杂性度量主要包括算法的时间复杂性和算法的空间复杂性。8.贪心算法求解的问题主要具有哪些性质？简述之。贪心算法求解的问题一般具有二个重要的性质：
一是贪心选择性质，这是贪心算法可行的第一个基本要素；
另一个是最优子结构性质，问题的最优子结构性质是该问题可用贪心算法求解的关键特征。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。
分治法的基本思想：将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1≤n，而且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。
合并排序基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。10.简述分析贪心算法与动态规划算法的异同。
贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。三、算法编写及算法应用分析题：
1.已知有3个物品：(w1,w2,w3=(12,10,6,(p1,p2,p3=(15,13,10,背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。解：
根据递推式fi（X）＝max{fi-1(X，fi-l(X—wi+pi|X≥wi}从i=1开始，最后得到fn（M）
f1(1~f1(11=0f1(12~f1(20=p1=15f2(1~f2(9=0
f2(10~f2(11=max{f1(10，f1(10–w2+p2}=13f2(12~f2(20=max{f1(12，f1(12–w2+p2}=15
f3(20=max{f2(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）第一步：15291351832127255
第二步：29135183227251515第三步：13532291827251551第四步：13532292725181551

（2）基本思想：首先将待搜索元素v与数组的中间元素A进行比较，如果vA，则在前半部分
22元素中搜索v；若vA，则搜索成功；否则在后半部分数组中搜索v。
2
非递归算法：
输入：递减数组A[left:right]，待搜索元素v。
输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：【3分】
intBinarySearch(intA[],intleft,intright,intv{
intmid;
while(left<=right{
mid=int((left+right/2;if(v==A[mid]returnmid;
elseif(v>A[mid]right=mid-1;elseleft=mid+1;}
return-1;}
（3）递归算法：
输入：递减数组A[left:right]，待搜索元素v。
输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：
intBinarySearch(intA[],intleft,intright,intv{
intmid;
if(left<=right{
mid=int((left+right/2;if(v==A[mid]returnmid;
elseif(v>A[mid]returnBinarySearch(A,left,mid-1,v;elsereturnBinarySearch(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(ari*ri1，k=1，2，3，4，5，6，r=5，r=10，r=3，r=12，r=5，r=50，r=6，求3.已知kij
1
2
3
4
5
6
7
nn
n

矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序（要求给出计算步骤）。
解：使用动态规划算法进行求解。求解矩阵为：
12345610150330405165520102036033024301950301809301770403000186050150060

123456
1012242
202222
30344
4044
50560
因此，最佳乘积序列为（A1A2）（（A3A4）（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，c(２＝0，U(2＝23;x(1=2，c(3＝15，U(3＝25,x(1=3，c(4＝28，U(4＝28,
U=min{23,25,28}=23,由于c(4＝28>U所以节点４删除。活节点表Ｌ={2,3}，取最小代价估值节点２作为扩展节点：
x(2=2，w1+w2>M，节点5是不合理节点；
x(2=3，这是答案节点c(6=13，即找到了代价为13的解，修改U＝13，由于活节点表中的节点3有c(3＝25，所以节点3可以删除。这时L＝｛｝，算法结束。最优解X={1,3}搜索产生的状态空间树如下图：
1
X1=3
28


X1=1
230
1
X1=2
2515
2X2=3
3
4
U=23
X2=2
2313013

1515
7

56

节点6是答案节点



5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。
解：intgreedy(vecterx,intn
{
intsum=0,k=x.size(;for(intj=0;jif(x[j]>n{
cout<<”Nosolution”<return-1;}
for(inti=0,s=0;is+=x[i];
if(s>n{sum++;s=x[i];}}
returnsum;
}
6、试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：
(1删除一个字符。(2插入一个字符。
(3将一个字符改为另一个字符。请写出该算法。
解：此题用动态规划算法求解：
intdist({
intm=a.size(;intn=b.size(;
vectord(n+1,0;
for(inti=1;i<=n;i++d[i]=i;for(i=1;i<=m;i++{inty=i-1;
for(intj=1;j<=n;j++{intx=y;y=d[j];
intz=j>1?d[j-1]:i;
intdel=a[i-1]==b[j-1]?0:1;d[j]=min(x+del,y+1,z+1;}}
returnd[n];}7、对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。

be2g
2
1
2
ad
3
2
3
1
8

解：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。步骤V1V2E1E21.{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的最短路径为abdfegh，权值为18。
求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。8、试写出用分治法对数组A[n]实现快速排序的算法。解：用分治法求解的算法代码如下：
intpartition(floatA[],intp,intr{
inti=p,j=r+1;floatx=a[p];while(1{
while(a[++i]while(a[--j]>x;if(i>=jbreak;a[i]a[j];
};
a[p]=a[j];a[j]=x;returnj;
}
voidQuicksort(floata[],intp,intr{
if(p
intq=partition(a,p,r;Quicksort(a,p,q-1;Quicksort(a,q+1,r;}
2
c
f2h


};
Quicksort(a,0,n-1;
9、有n个活动争用一个活动室。已知活动i占用的时间区域为[si，fi]，活动i,j相容的条件是：sj≥fi，问题的解表示为(xi|xi=1，2…，n,，xi表示顺序为i的活动编号活动，求一个相容的活动子集，且安排的活动数目最多。
解：解决这个问题的基本思路是在安排时应该将结束时间早的活动尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结束时间分别用两个数组s和f存储，并使得数组中元素的顺序按结束时间非减排列：f1f2…fn。算法如下：
GreedyAction(s,f，n//s[1:n]、f[1:n]分别代表n项活动的起始//时间和结束时间,并且满足f[1]f[2]…f[n]j=1;solution={1};//解向量初始化为空集fori←2tondoifsifjthen
solution=solution{j};//将j加入解中j=i;endifendfor
return(solution;endGreedy10、设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。解：由于x1、x2、x3是三角形的三条边，从而xi+xj>xk，|xi-xj|，（i,j,k=1,2,3），根据x1+x2+x3=14可知1（i=1,2,3）。利用回溯法求解得到：
x1=6
x2=6
5
×
5
543
×4
4
×Ö
x3=2
Ö
3
ÖÖ

即有4个可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。11、设数组A有n个元素，需要找出其中的最大最小值。
（1）请给出一个解决方法，并分析其复杂性。
（2）把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大
值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。
解：（1）基本思想：从头到尾逐个扫描，纪录最大和最小元素。输入：具有n个元素的数组输出：最大值和最小值步骤：

voidFindMaxMin(intA[],intn,intmax,intmin{
max=min=A[0];for(i=1;i{
if(A[i]>maxmax=A[i];if(A[i]}}
复杂性分析：由于是从头到尾扫描各个元素，而每个元素都要与max和min比较一遍，从而时间复杂性为：O(n。
（2）voidFindMaxMin(intleft,intright,intmax,intmin{if(left==rightmax=min=A[left];elseif(left=right-1{
max=(A[left]min=(A[left]}else{
mid=(left+right/2;
FindMaxMin(left,mid,gmax,gmin;FindMaxMin(mid+1,right,hmax,hmin;max=(gmaxmin=(gmin}
}12、有n个程序和长度为L的磁带，程序i的长度为ai，已知
a
i1
n
i
L，求最优解(xi，x2，...，xi，…，
n
xn，xi=0，1,xi=1，表示程序i存入磁带，xi=0，表示程序i不存入磁带，满足
xa
ii1
i
L，且存放
的程序数目最多。
解：由于目标是存放的程序数目最多，所以最优量度应该是min{ai|ai为程序i的长度}，
即每次选入的程序都是当前最短的。我们可以将n个程序按a[1]≤a[2]≤…≤a[n]顺序排序，然后从i=1开始依次选择。算法如下：
procedureprogramming(L,n,a,xbegin
//n个程序按a[1]≤a[2]≤…≤a[n]顺序排序x←0;i=1;
while(a[i]≤Landi≤ndo{x[i]←1;L←L-a[i]；i←i+1;}end.
13、试用分治法实现有重复元素的排列问题：设R{r1,r2,...,rn是要进行排列的n个元素，其中元素
r1,r2,...,rn可能相同，试设计计算R的所有不同排列的算法。

解：解答如下：
Template
voidPerm(Typelist[],intk,intm{
if(k==m{
for(inti=0;i<=m;i++cout<cout<}
elsefor(inti=k;i<=m;i++if(ok(list,k,i{
swap(list[k],list[i];Perm(list,k+1,m;
swap(list[k],list[i];};}
其中ok用于判别重复元素。Template
intok(Typelist[],intk,inti
{
if(i>k
for(intt=k;t
if(list[t]==list[i]return0;
return1;
}
14、试用动态规划算法实现0-1闭包问题，请写出该算法。解：解答如下：
Template
voidKnapsack(Typev,intw,intc,intn,Type**m{
IntjMax=min(w[n]-1,c;
for(intj=0;j<=jMax;j++m[n][j]=0;for(intj=w[n];j<=c;j++m[n][j]=v[n];for(inti=n-1;i>1;i--{jMax=min(w[i]-1,c;
for(intj=0;j<=jMax;j++m[i][j]=m[i+1][j];
for(intj=w[i];j<=c;j++m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i];};
m[1][c]=m[2][c];
if(c>=w[1]m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1];}
Template
VoidTraceback(Type**m,intw,intc,intn,intx{
for(inti=1;i
if(m[i][c]==m[i+1][c]x[i]=0;
else{x[i]=1,c-=w[i];};x[n]=(m[n][c]?1:0;}

15、试用贪心算法求解下列问题：将正整数n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大，请写出该算法。
解：解答如下：
voiddicomp(intn,inta[]{
k=1;
if(n<3{a[1]=0;return;};
if(n<5{a[k]=1;a[++k]=n-1;return;};a[1]=2;n-=2;
while(n>a[k]{k++;
a[k]=a[k-1]+1;n-=a[k];
};
if(n==a[k]{a[k]++;n--;};for(inti=0;i}
16、试写出用分治法对一个有序表实现二分搜索的算法。解：解答如下：
Template
intBinarySearch(Typea[],constType&x,intn
{//假定数组a[]已按非递减有序排列，本算法找到x后返回其在数组a[]中的位置，//否则返回-1intleft=0,right=n-1;while(left<=right{
intmiddle=(left+right/2;
if(x==a[middle]returnmiddle+1;if(x>a[middle]left=middle+1;elseright=middle-1;}
return-1;}
17、试用动态规划算法实现最长公共子序列问题，请写出该算法。解：用动态规划算法求解的算法代码如下：
intlcs_len(char*a,char*b,intc[][N]{
intm=strlen(a,n=strlen(b,i,j;for(i=0;i<=m;i++c[i][0]=0;for(j=1;j<=n;j++c[0][j]=0;for(i=1;i<=m;i++for(j=1;j<=n;j++
if(a[i-1]==b[j-1]c[i][j]=c[i-1][j-1]+1;elseif(c[i-1][j]>=c[i][j-1]c[i][j]=c[i-1][j];
elsec[i][j]=c[i][j-1];returnc[m][n];};
char*build_lcs(chars[],char*a,char*b

{
intk,i=strlen(a,j=strlen(b,c[N][N];k=lcs_len(a,b,c;s[k]=’\0’;while(k>0{
if(c[i][j]==c[i-1][j]i--;
elseif(c[i][j]==c[i][j-1]j--;else{
s[--k]=a[i-1];i--,j--;}}
returns;
}
18、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题，请写出状态空间搜索树。
物品A
B
C
D
E
F
G
重量35306050401025价值10403050354030
解：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：
x11
x21
x31
a
x10
a
x20
j
ai
x41
a
x40
x30
a
x50
d
x41
e
x40
b
x60
x51
e
x50
hg
c
x70
e
x60
Q1
f

40
8
a．4040305035150115190.625(1,1,1,1,7,0,0b.4040305030150115177.5(1,1,1,1,0,7,0
60
12
c．4040305010170
(1,1,1,1,0,0,1
d.4040303530150105167.5(1,1,1,0,1,3,0
60
4

e.4040503530150130175
60
1
(1,1,0,1,1,,0
3
4(1,1,0,1,1,0,7
f.4040503510150130170.71
35
g.40405030160

(1,1,0,1,0,1,0
h.4040353010150140146.85(1,1,0,0,1,1,2
357
i.4030503530150125167.5(1,0,1,1,1,5,0
6012150145
j.4030503530157.5(0,1,1,1,1,1,0
6012
在Q1处获得该问题的最优解为(1,1,1,1,0,0,1，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。
19、求解子集和问题：对于集合S={1，2，6，8}，求子集，要求该子集的元素之和d=9。
①画出子集和问题的解空间树；
②该树运用回溯算法，写出依回溯算法遍历节点的顺序；
③如果S中有n个元素，指定d，用伪代码描述求解子集和问题的回溯算法。解答：满足要求的子集有[1，2，6]，[1，8]
①解空间树如下：
00011010101011
10ÎÂYZÔÛPÊQRSTUVWX
②遍历结点的顺序为：ABDHPQIRSEJTUKVWCFLXYMZÊGNÔÛOÂÎ③用伪代码描述算法如下：#include#defineN100intas=0,t=0;intsum;
voidbacktrackiter(inti,ints[],intn,intd,intsum{
if(i>n


return;else{
if(as==d{
t++;return;}
sum-=s[i];if(as+s[i]<=d{
as+=s[i];
backtrackiter(i+1,s,n,d,sum;as-=s[i];}
if(as+sum>=d
backtrackiter(i+1,s,n,d,sum;sum+=s[i];}}
20、求解填字游戏问题：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求的一种数字填法的算法和满足这个要求的全部数字填法的算法。
解：为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。
回溯法找一个解的算法：{}
intm=0,ok=1;intn=8;do{
if(ok扩展;else调整;
ok=检查前m个整数填放的合理性;}while((!ok||m!=n&&(m!=0if(m!=0输出解;
else输出无解报告；
如果要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下：
回溯法找全部解的算法：{intm=0,ok=1;



}
intn=8;do{
if(ok
{if(m==n
{输出解；
调整；}
else扩展;
}
else调整;
ok=检查前m个整数填放的合理性;}while(m!=0;
21、试用动态规划算法实现最大子矩阵和问题：求mn矩阵A的一个子矩阵，使其各元素之和为最大。解：解答如下：
intMaxSum2(intm,intn,int**a{
intsum=0;
int*b=newint[n+1];for(inti=1;i<=m;i++{
for(intk=1;k<=n;k++b[k]=0;for(intj=i;j<=m;j++{
for(intk=1;k<=n;k++b[k]+=a[j][k];intmax=MaxSum(n,b;
if(max>sumsum=max;
}}
returnsum;}
intMaxSum(intn,int*a
{
intsum=0,b=0;
for(inti=1;i<=n;i++{if(b>0b+=a[i];elseb=a[i];if(b>sumsum=b;}
Returnsum;}22、试用回溯法解决下列整数变换问题：关于整数i的变换f和g定义如下：f(i3i;g(ii/2。对于给定的两个整数n和m，要求用最少的变换f和g变换次数将n变为m。解：解答如下：
voidcompute({k=1;

while(!search(1,n{k++;
if(k>maxdepbreak;init(;
};if(foundoutput(;
elsecout<<”NoSolution!”<}
boolsearch(intdep,intn{
If(dep>kreturnfalse;for(inti=0;i<2;i++{
intn1=f(n,i;t[dep]=i;if(n1==m||search(dep+1,n1{Found=true;Out(;
returntrue;}
returnfalse;}
23、关于15谜问题。在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。
请使用该估计函数，对图示的初始状态，给出使用分支限界方法转换到目标状态的搜索树。
12412

563756

910128910

131411151314

初始状态目标状态

37
48
111215


1245637910128131411151234567910128613141115
12456379101286
13141115
12341245679101285
56379101287
13141115131411151234123456127910855679101284
13141115
13141115
1231234567456789101285
910123
13141115
13141115
12341234
5678789101223
56910121513141115
131411
1234123412345683567891071291011121
5678910123
13141115
131415
13141115
12341234
5678567891011122
91011120
131415
131415
解：
7

本文来源：https://www.2haoxitong.net/k/doc/4b45cb05ef06eff9aef8941ea76e58fafab045e4.html

《算法分析与设计复习题及参考答案.doc》
将本文的Word文档下载到电脑，方便收藏和打印
推荐度：
点击下载文档

文档为doc格式
相
关
案
例

相关推荐

推荐内容

人物传记阅读分类专练与答案 作文-你是我最欣赏的人 2019年中考化学86个考点大汇总,考生必看!转给孩子! 法国人的礼仪 学生会纪检部检讨书(精选多篇).doc 高考生物光合作用知识点总结 韦伯定律的应用 恋爱中双方应保持的几个距离 2020商场经理竞聘演讲稿范文(精选3篇) [贱卖恋爱遗产]附加遗产
网站内容来自网络，如有侵权请联系我们，立即删除！ Copyright © 范文写作网京ICP备16605803号