湖南大学复习算法分析期末答案大题.doc

湖南大学复习算法分析期末答案大题
一、 解答题
1. 机器调度问题。
问题描述：现在有n件任务和无限多台的机器，任务可以在机器上得到处理。每件任务的开始时间为si，完成时间为fi，si<fi 。[si，fi]为处理任务i的时间范围。两个任务i，j重叠指两个任务的时间范围区间有重叠，而并非指i，j的起点或终点重合。例如：区间[1，4]及区间[2，4]重叠，而及[4，7]不重叠。一个可行的任务分配是指在分配中没有两件重叠的任务分配给同一台机器。因此，在可行的分配中每台机器在任何时刻最多只处理一个任务。最优分配是指使用的机器最少的可行分配方案。
问题实例：若任务占用的时间范围是{[1，4]，[2，5]，[4，5]，[2，6]，[4，7]}，则按时完成所有任务最少需要几台机器？（提示：使用贪心算法）
画出工作在对应的机器上的分配情况。

3. 单源最短路径的求解。
问题的描述：给定带权有向图（如下图所示）G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
解法：现采用Dijkstra算法计算从源顶点1到其它顶点间最短路径。请将此过程填入下表中。

4

3

2

1
100
30
maxint
10
-
{1}
初始
dist[5]
dist[4]
dist[3]
dist[2]
u
S
迭代

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。其它情况下，由最优子结构性质可建立递归关系如下：
在程序中，b[i][j]记录C[i][j]的值是由哪一个子问题的解得到的。

三、算法理解
1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。

5
2

8
6
3
1

7
4

各边的代价如下：
C(1,2)=3， C(1,3)=5 ，C(1,4)=2
C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1
C(5,8)=4， C(6,8)=5 ，C(7,8)=6
解：Cost(4,8)=0
Cost(3,7)= C(7,8)+0=6 ，D[5]=8
Cost(3,6)= C(6，8)+0=5, D[6]=8
Cost(3,5)= C(5，8)+0=4 D[7]=8

Cost(2,4)= min{C(4，6)+ Cost(3,6), C(4，5)+ Cost(3,5)}
= min{1+ 5, 2+4}=6 D[4]=6
Cost(2,3)= min{C(3，6)+ Cost(3,6) }
= min{4+5}=9 D[3]=5
Cost(2,2)= min{C(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7)}
= min{8+5, 4+6}=10 D[2]=7

Cost(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}= 8
D[1]=4
1→4→6→8

2、 写出maxmin算法对下列实例中找最大数和最小数的过程。
数组 A=(48,12,61,3,5,19,32,7)
解：写出maxmin算法对下列实例中找最大数和最小数的过程。
数组 A=()
1、 48,12,61,3, 5,19,32,7
2、48,12 61,3 5,19 32,7
3、 48～61, 12～3 19～32，5～7
4、 61～32 3～5
5、 61 3

1、 快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。
A=(65,70,75,80,85,55,50,2)
解：第一个分割元素为65
(1) (2) (3) (4) (5) (6) (7) (8) i p
65 70 75 80 85 55 50 2 2 8
65 2 75 80 85 55 50 70 3 7
65 2 50 80 85 55 75 70 4 6
65 2 50 55 85 80 75 70 4 6
55 70 75 80 85 65 50 2

2、 归并排序算法对下列实例排序，写出算法执行过程。
A=(48,12,61,3,5,19,32,7)
解： 48,12,61,3 5,19,32,7
48,12 61,3 5,19 32,7
12,48 3,61 5,19 7,32
3, 12, 48, 61 5, 7, 19，32
3,5, 7,12，19，32，48,61

3、 写出图着色问题的回溯算法的判断X[k]是否合理的过程。
解：i←0
while i<k do
if G[k,i]=1 and X[k]= X[i] then
return false
i←i+1
repeat
if i= k then return true

4、 对于下图，写出图着色算法得出一种着色方案的过程。
2

3

1

4

解：K←1
X[1] ←1 , 返回 true
X[2]←1,返回false; X[2]←X[2]+1=2, 返回 true
X[3]←1 ,返回false; X[3]←X[3]+1=2, 返回false;X[3]←X[3]+1=3, 返回 true
X[4]←1, 返回false; X[4]←X[4]+1=2, 返回false;X[4]←X[4]+1=3, 返回 true
找到一个解 （1，2，3，3）

5、 写出第7题的状态空间树。
解：
X[1]=1

X[2]=2

X[3]=33

X[4]=33

8、写出归并排序算法对下列实例排序的过程。
(6,2,9,3,5,1,8,7)
解：调用第一层次 6,2,9,3 5,1,8,7 分成两个子问题
调用第二层次 6,2 9,3 5,1 8,7 分成四个子问题
调用第三层次 6 2 9 3 5 1 8 7 分成八个子问题
调用第四层次 只有一个元素返回上一层
第三层归并 2 ,6 3, 9 1,5 7,8 返回上一层
第二层归并 2 ,3,6, 9 1,5,7,8 返回上一层
第一层归并 1, 2 ,3, 5 ,6, 7, 8,9 排序结束，返回主函数

9、写出用背包问题贪心算法解决下列实例的过程。
P=(18,12,4,1)
W=(12,10,8,3)
M=25
解: 实例符合P(i)/W(i)≥P(i+1)/W(i+1)的顺序。
CU←25,X←0
W[1]< CU: x[1]←1; CU←CU-W[1]=13;
W[2]< CU: x[2]←1; CU←CU-W[2]=3;
W[3]>CU: x[3]←CU/ W[3]=3/8;
实例的解为：（1，1，3/8，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的一棵最小生成树。

1
2
4
3
5
6

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)=6
解：使用普里姆算法构造出如下图G的一棵最小生成树。

1
2
4
3
5
6

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)=6

1
3
1
6
1
3
6
4
1
2
6
4
5
1
2
6
3
4
3
3

13、有如下函数说明
int f(int x,int y)
{
f=x Mod y +1;
}
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细过程。
解：有如下函数说明
int f(int x,int y)
{
f=x Mod y +1;
}
已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细过程。

}
K的值是5

四、设计算法
1. 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。
多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。
解：对于处理机j，用S[j] 表示处理机j已有的作业数，用P[j,k]表示处理机j的第k个作业的序号 。
1）将作业按照t[1]≥t[2]≥……≥t[n]排序
2）S[1:m]清零 j←0 //从第一个处理机开始安排
3) for i←1 to n do //安排n个作业
j←j mod m +1 //选下一个处理机
S[j]←S[j]+1;
P[j,S[j]]←i ；
Repeat

2. 设有n种面值为:
d1≥d2≥……≥dn的钱币，需要找零钱M，如何选择钱币dk，的数目Xk，满足
d1×Xi＋……dn×Xn=M ，使得
Xi＋……Xn 最小
请选择贪心策略，并设计贪心算法。
解：贪心原则：每次选择最大面值硬币。
CU←M;i←1;X←0 // X为解向量
While CU≠0 do
X[i]←CU div d[i] // X[i]为第i中硬币数
CU←CU-d[i]*X[i]
i←i+1;
repeat

3. 有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。
解：定义结构体数组G，将物品编号、利润、重量作为一个结构体：例如G[k]={1,10,2}
求最优解，按利润/重量的递减序，有
{5,6,1,6} {1,10,2,5}{6,18,4,9/2} {3,15,5,3} {7,3,1,3}{2,5,3,5/3} {4,7,7,1}
算法
procedure KNAPSACK(P，W，M，X，n)
//P(1：n)和W(1；n)分别含有按
P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值
和重量。M是背包的容量大小，而x(1：n)是解向量//
real P(1：n)，W(1：n)，X(1：n)，M，cu；
integer i，n；
X←0 //将解向量初始化为零//
cu←M //cu是背包剩余容量//
for i←1 to n do
if W(i)>cu then exit endif
X(i) ←1
cu←cu-W(i)
repeat
end GREEDY-KNAPSACK
根据算法得出的解：
X=（1,1,1,1,1,0,0）获利润52， 而解
（1,1,1,1, 0, 1,0）可获利润54
因此贪心法不一定获得最优解。

1、对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或或，并简述理由。（12分）
(1)
(2)
(3)
解：简答如下：
（1），（2），（3）

《算法设计及分析》考试试卷
一、 排序和查找是经常遇到的问题。按照要求完成以下各题：（20分）
（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 15 1 5 【1分】
第三步：135 32 29 18 27 25 15 5 1 【1分】
第四步：135 32 29 27 25 18 15 5 1 【1分】
（2）基本思想：首先将待搜索元素v及数组的中间元素进行比较，如果，则在前半部分元素中搜索v；若，则搜索成功；否则在后半部分数组中搜索v。【2分】
非递归算法：
输入：递减数组A[left:right]，待搜索元素v。【1分】
输出：v在A中的位置pos，或者不在A中的消息（-1）。【1分】
步骤：【3分】
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
while (left<=right)
{
mid=int((left+right)/2);
if (v==A[mid]) return mid;
else if (v>A[mid]) right=mid-1;
else left=mid+1;
}
return -1;
}
（3）递归算法：
输入：递减数组A[left:right]，待搜索元素v。【1分】
输出：v在A中的位置pos，或者不在A中的消息（-1）。【1分】
步骤：【3分】
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
if (left<=right)
{
mid=int((left+right)/2);
if (v==A[mid]) return mid;
else if (v>A[mid]) return BinarySearch(A,left,mid-1,v);
else return BinarySearch(A,mid+1,right,v);
}
else
return -1;
}
（4）搜索18：首先及27比较，18<27，在后半部分搜索；再次及18比较，搜索到，返回5。【1分】
搜索31：首先及27比较，31>27，在前半部分搜索；再次32比较，31<32，在后半部分搜索，及29比较，31>29，此时只有一个元素，未找到，返回-1。【2分】
搜索135：首先及27比较，135>27，在前半部分搜索；再次32比较，135>32，在前半部分搜索；及135比较，相同，返回0。【2分】

二、 对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。（20分）。

答案：用V1表示已经找到最短路径的顶点，V2表示及V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为及V1中的顶点相邻接且距离最短的路径。【1分】
步骤 V1 V2 E1 E2
1. {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} {} 【以上每步2分】
结果：从a到h的最短路径为，权值为18。【1分】

三、 假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
答案：求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】
三、按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】
【状态空间搜索树及其计算过程17分，每个节点1分】
a．
b.
c．
d.
e.
f.
g.
h.
i.
j.
在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】
四、 已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。（要求：给出计算步骤）（20分）
答案：使用动态规划算法进行求解。
求解矩阵为：【每个矩阵18分】

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

因此，最佳乘积序列为（A1A2）（（A3A4）（A5A6）），共执行乘法2010次。【结论2分】

五、算法理解题（本题5分）
设有n=2k个运动员要进行循环赛，现设计一个满足以下要求的比赛日程表：
①每个选手必须及其他n-1名选手比赛各一次；
②每个选手一天至多只能赛一次；
③循环赛要在最短时间内完成。
（1）如果n=2k，循环赛最少需要进行几天；
（2）当n=23=8时，请画出循环赛日程表。
六、算法设计题（本题15分）
分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。
七、算法设计题（本题10分）
通过键盘输入一个高精度的正整数n(n的有效位数≤240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。
【样例输入】
178543
S=4
【样例输出】
13

1 2 3 4 5 6 7 8
2 1 4 3 6 5 8 7
3 4 1 2 7 8 5 6
4 3 2 1 8 7 6 5
5 6 7 8 1 2 3 4
6 5 8 7 2 1 4 3
7 8 5 6 3 4 1 2
8 7 6 5 4 3 2 1

五、（1）8天（2分）；
（2）当n=23=8时，循环赛日程表（3分）。
六、算法设计题（本题15分）
（1）贪心算法 O（nlog（n））
Ø 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
（2）动态规划法 O(nc)
m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。

（3）回溯法 O(2n)
cw:当前重量 cp:当前价值 bestp：当前最优值
void backtrack(int i)
//回溯法  i初值1
{    if(i > n) //到达叶结点
{ bestp = cp;              return;            }   
     if(cw + w[i] <= c) //搜索左子树   
         { cw += w[i];
  cp += p[i];              
backtrack(i+1);   
           cw -= w[i];
            cp -= p[i];   
        }   
       if(Bound(i+1)>bestp)
//搜索右子树   
        backtrack(i+1);   
 }   

七、算法设计题（本题10分）
为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。
具体算法如下：
输入s, n;
while（ s > 0 ）
{ i=1; //从串首开始找
while (i < length(n)) && (n[i]<n[i+1])
{i++;}
delete(n,i,1); //删除字符串n的第i个字符
s--;
}
while (length(n)>1)&& (n[1]=‘0’)
delete(n,1,1); //删去串首可能产生的无用零
输出n;

二．计算题和简答题（每小题7分，共21分）
1．用O、、表示函数f及g之间阶的关系，并分别指出下列函数中阶最低和最高的函数：
(1)　f (n)=100 g(n)=
(2) f(n)=6n+n g(n)=3n
(3) f(n)= n/logn-1 g(n)=
(4) f(n)= g(n)=
(5) f(n)= g(n)=
1. 阶的关系：
(1) f(n)= O(g(n))
(2) f(n)=(g(n))
(3) f(n)=(g(n))
(4) f(n)= O(g(n))
(5) f(n)=(g(n))
阶最低的函数是：100
阶最高的函数是：

四．算法设计题（15分）
1. 一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为公里，0=，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。
算法设计题：
1. 贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。
算法 MINSTOPS
输入：A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行驶的公里数m，存储各加油站离起点A的距离的数组d[1..n]。
输出：从A地到B地的最少加油次数k以及最优解x[1..k]（x[i]表示第i次加油的加油站序号），若问题无解，则输出no solution。
d[n+1]=s; //设置虚拟加油站第n+1站。
for i=1 to n
if d[i+1]-d[i]>m then
output “no solution”; return //无解，返回
end if
end for
k=1; x[k]=1 //在第1站加满油。
s1=m //s1为用汽车的当前油量可行驶至的地点及A点的距离
i=2
while s1<s
if d[i+1]>s1 then //以汽车的当前油量无法到达第i+1站。
k=k+1; x[k]=i //在第i站加满油。
s1=d[i]+m //刷新s1的值
end if
i=i+1
end while
output k, x[1..k]
MINSTOPS

最坏情况下的时间复杂性：Θ(n)

二、简答题：
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<k≤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)= 0
f1(12) ~ f1(20)= p1=15
f2(1) ~ f2(9)= 0
f2(10) ~ f2(11)= max{f1(10)，f1(10 – w2)+p2} =13
f2(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）第一步：15 29 135 18 32 1 27 25 5
第二步：29 135 18 32 27 25 15 1 5
第三步：135 32 29 18 27 25 15 5 1
第四步：135 32 29 27 25 18 15 5 1
（2）基本思想：首先将待搜索元素v及数组的中间元素进行比较，如果，则在前半部分元素中搜索v；若，则搜索成功；否则在后半部分数组中搜索v。
非递归算法：
输入：递减数组A[left:right]，待搜索元素v。
输出：v在A中的位置pos，或者不在A中的消息（-1）。
步骤：【3分】
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
while (left<=right)
{
mid=int((left+right)/2);
if (v==A[mid]) return mid;
else if (v>A[mid]) right=mid-1;
else left=mid+1;
}
return -1;
}
（3）递归算法：
输入：递减数组A[left:right]，待搜索元素v。
输出：v在A中的位置pos，或者不在A中的消息（-1）。
步骤：
int BinarySearch(int A[],int left,int right,int v)
{
int mid;
if (left<=right)
{
mid=int((left+right)/2);
if (v==A[mid]) return mid;
else if (v>A[mid]) return BinarySearch(A,left,mid-1,v);
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，此时只有