算法设计与分析答案参考

(1) (2) (3) (4) (5) (6) (7) (8) i p 7、对于下图，写出图着色算法得出一种着色方案的过程。 65 70 75 80 85 55 50 2 2 8 解： 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）

8、有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 ，因此贪心法不一定获得最优解。

9、排序和查找是经常遇到的问题。按照要求完成以下各题：

（1） 对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其

排成递减序。

（2） 给出上述算法的递归算法。

（3） 使用上述算法对（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）输入：递减数组A[left:right]，待搜索元素v。

输出：v在A中的位置pos，或者不在A中的消息（-1）。 步骤：

int BinarySearch(int A[],int left,int right,int v) { int mid;

if (left<=right) { } else }

（3）搜索18：首先与27比较，18<27，在后半部分搜索；再次与18比较，搜索到，返回5。

return -1;

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);