《算法设计与分析》上机指导(2)

1. QuickSort(A,1,n)

过程QuickSort(A[1..n],low,high)

1. if low<high then 2. w=Split(A,low,high) 3. QuickSort(A,low,w-1) 4.

QuickSort(A,w+1,high)

5. ens if

过程procedure Split(A[1..n],low,high)

1. i←low //初始时i指向A[low]

2. x←A[low]

//处理过程中有：A[low..i]≤x=A[low]

《算法设计与分析》上机指导

3. for j←low+1 to high //j指向当前处理的元素 4. 5. 6. 7.

if A[j]≤x then

i←i+1

if i≠j then 互换A[i]和A[j]

//处理过程中有：A[i+1..j]>x=A[low]

end if

8. end for

9. if low≠i then 互换A[low]和A[i] 10. w←i 11. return w

用C语言实现上述算法并上机通过。

习题二（工程名为202、源程序名为202） 解最长公共子序列问题的伪代码描述如下： 算法 LCSRec（递归算法）

输入：字符串A和B，设A和B的长度分别为n和m。 输出：A和B的最长公共子序列的长度

1. LCSRec(n,m)

过程procedure LCSRec(i,j)

1. if i=0 or j=0 then return 0 2. else 3. 4.

if A[i]=B[j] then

return LCSRec(i-1,j-1)+1

5. else 6.

return max(LCSRec(i,j-1),LCSRec(i-1,j))

7. end if 8. end if

用C语言实现上述算法并上机通过。

选做题：给出最长公共子序列问题的非递归算法（动态规划法），并上机通过。

习题三（工程名为203、源程序名为203）

《算法设计与分析》上机指导

解背包问题的伪代码描述如下： 算法7.4 Knapsack（参见Page 139）

输入：背包容量C、物品体积集合 S = {s1,s2,...,sn}、物品价值集合V = {v1,v2,...,vn} 输出：可装入背包物品的最大总价值

1. for i←0 to n V[i,0]←0 2. for j←0 to C V[0,j]←0 3. for i←1 to n 4. 5. 6. 7. 8. 9.

for j←1 to C

if si > j then

//物品ui的体积si超过容量j,不装入。 //背包容量为0 //背包未装入任何物品

V[i,j]←V[i-1,j] //取上一次的计算结果

else

//物品ui的体积si不超过容量j,可装入。

V[i,j]←max(V[i-1,j],V[i-1,j-si]+vi)

end if

10. end for 11. end for 12. return V[n,C]

//返回最大总价值

用C语言实现上述算法并上机通过。

选做题1：如何修改算法Knapsack，，使它只需要Θ(C)空间，其中C是背包容量。

选做题2：给出背包问题的递归算法，并上机通过。

㈢提交方式

首先建立个人目录，目录名为“学号姓名”，例 “57053001温敬和”。在目录“57053001温敬和”中，建立子目录2（本次实习）。在目录“57053001温敬和\2”中，应具有如下文件：

201.cpp、201.exe、202.cpp、202.exe、203.cpp、203.exe

《算法设计与分析》上机指导

《算法设计与分析》上机指导3

㈠（每个）程序书写要求

// ******************************************************* // * 工 程 名：103.dsp * // * 程 序 名：103.cpp * // * 主要功能：自底向上合并排序法 * // * 学号姓名：57053001温敬和 * // * 编制时间：2007年7月13日 * // ******************************************************** #include <iostream.h> //#include <iostream> void main() //using namespace std; { //int main() …… //{

…… // …… …… // return 0; } //}

㈡实习内容

习题一（工程名为301、源程序名为301） 解最短路径问题的伪代码描述如下： 算法 8.1（Page 147）

输入：含权有向图G=(V,E)的邻接矩阵，约定结点1为源。 输出：G中结点1到其它各结点的最短路径长度

1. X={1}:Y=V-{1}:λ[1]=0 2. for y←2 to n

3. if y相邻于顶点1 then λ[y]=length[1,y] 4. else λ[y]=∞ 5. end if 6. end for 7. for j←1 to n-1

//Y中共有n-1个顶点

8.

设y∈Y且λ[y]为最小

9. X←X∪{y}:Y←Y-{y} //将结点y由集合X移入集合Y

10. for 每条边(y,w)

《算法设计与分析》上机指导

11. 12. 13.

if w∈Y and λ[y]+lengh[y,w]<λ[w] then

λ[w]←λ[y]+lengh[y,w]

end if

14. end for 15. end for

用C语言实现上述算法并上机通过。

习题二（工程名为302、源程序名为302） 解图三着色问题的伪代码描述如下： 输入：无向图G=(V,E)

输出：图的结点3着色向量c[1..n]，0≤c[j] ≤3（1≤j≤n）。

1．c[1..n]←0

//c[1..n]为全局量

2．GraphColorRec(1) 过程GraphColorRec(k)

1. for color←1 to 3 2.

c[k]←color

//部分解或解 //部分解

3. if c[1..k]为合法着色 then 4. if k<n then 5.

GraphColorRec(k+1) //进入下一个结点

//是解

6. else 7.

output c[1..n] and exit

8. end if 9. end if 10. end for 11. c[k]=0

//回溯前清0，即没有着任何颜色。

用C语言实现上述算法并上机通过。 选做题1：给出图三着色问题的全部解。

选做题2：给出图三着色问题的非递归算法，并上机通过。

《算法设计与分析》上机指导

习题三（工程名为303、源程序名为303） 解4皇后问题的伪代码描述如下： 算法 4-QueenRec（递归解） 输入：空

输出：对应于4皇后问题的向量c[1..4]（全局量） 1. c[1..4]←0 2. advanced(1) 过程advanced(k)

1. for col←1 to 4 2. 3. 4. 5. 6. 7. 8. 9.

c[k]←col

//部分解或解 //解

//最多只有4列

if c是解 then

if k=4 then

output c and exit

else //部分解

advanced(k+1) //移至下一行 end if end if

10. end for 11. c[k]←0

//返回前清0（回溯）

选做题1：给出4皇后问题的全部解。

选做题2：给出4皇后问题的非递归算法，并上机通过。

㈢提交方式

首先建立个人目录，目录名为“学号姓名”，例 “57053001温敬和”。在目录“57053001温敬和”中，建立子目录3（本次实习）。在目录“57053001温敬和\3”中，应具有如下文件：

301.cpp、301.exe、302.cpp、302.exe、303.cpp、303.exe