《算法设计与分析》实验指导书
计算机学院信息安全系毕方明
本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。
上机实验一般应包括以下几个步骤：
（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。
（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。
（3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。
本书共分阶段4个实验，每个实验有基本题和提高题。基本题必须完成，提高题根据自己实际情况进行取舍。题目不限定如下题目，可根据自己兴趣爱好做一些与实验内容相关的其他题目，如动态规划法中的图象压缩，回溯法中的人机对弈等。
其具体要求和步骤如下：
实验一 分治与递归（4学时）
基本题一：基本递归算法
一、实验目的与要求
1、 熟悉C/C++语言的集成开发环境；
2、通过本实验加深对递归过程的理解
二、实验内容：
掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。
三、实验题
任意输入一个整数，输出结果能够用递归方法实现整数的划分。
四、实验步骤
1． 理解算法思想和问题要求；
2． 编程实现题目要求；
3． 上机输入和调试自己所编的程序；
4． 验证分析实验结果；
5． 整理出实验报告。
基本题二：棋盘覆盖问题
一、实验目的与要求
1、掌握棋盘覆盖问题的算法；
2、初步掌握分治算法
二、实验题：
盘覆盖问题：在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
三、实验提示
void chessBoard(int tr, int tc, int dr, int dc, int size)
{
if (size == 1) return;
int t = tile++, // L型骨牌号
s = size/2; // 分割棋盘
// 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s)
// 特殊方格在此棋盘中
chessBoard(tr, tc, dr, dc, s);
else {// 此棋盘中无特殊方格
// 用 t 号L型骨牌覆盖右下角
board[tr + s - 1][tc + s - 1] = t;
// 覆盖其余方格
chessBoard(tr, tc, tr+s-1, tc+s-1, s);}
// 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
chessBoard(tr, tc+s, dr, dc, s);
else {// 此棋盘中无特殊方格
// 用 t 号L型骨牌覆盖左下角
board[tr + s - 1][tc + s] = t;
// 覆盖其余方格
chessBoard(tr, tc+s, tr+s-1, tc+s, s);}
// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s)
// 特殊方格在此棋盘中
chessBoard(tr+s, tc, dr, dc, s);
else {// 用 t 号L型骨牌覆盖右上角
board[tr + s][tc + s - 1] = t;
// 覆盖其余方格
chessBoard(tr+s, tc, tr+s, tc+s-1, s);}
// 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s)
// 特殊方格在此棋盘中
chessBoard(tr+s, tc+s, dr, dc, s);
else {// 用 t 号L型骨牌覆盖左上角
board[tr + s][tc + s] = t;
// 覆盖其余方格
chessBoard(tr+s, tc+s, tr+s, tc+s, s);}
}
提高题一：二分搜索
一、实验目的与要求
1、熟悉二分搜索算法；
2、初步掌握分治算法；
二、实验题
1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。
2、设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标I，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。
三、实验提示
1、用I，j做参数，且采用传递引用或指针的形式带回值。
bool BinarySearch(int a[],int n,int x,int& i,int& j)
{
int left=0;
int right=n-1;
while(left<right)
{
int mid=(left+right)/2;
if(x==a[mid])
{
i=j=mid;
return true;
}
if(x>a[mid])
left=mid+1;
else
right=mid-1;
}
i=right;
j=left;
return false;
}
int SearchTag(int a[],int n,int x)
{
int left=0;
int right=n-1;
while(left<right)
{
int mid=(left+right)/2;
if(x==a[mid]) return mid;
if(x>a[mid])
right=mid-1;
else
left=mid+1;
}
return -1;
}
提高题二： 用分治法实现元素选择
一、实验要求与目的
1、了解分治法的基本思想，掌握递归程序编写方法；
2、使用分治法编程，求解线形序列中第k小元素。
二、实验内容
1、 给定线形序列集中n个元素和一个整数k，1≤k≤n，输出这n个元素中第k小元素的值及其位置。
2、 简述该算法的原理、步骤。对该算法与直接排序查找进行比较。
3、 编写并调试程序。
测试要求：元素个数不少于100；分三种情况：k=1、k=n和k=中位数。
实验二动态规划算法（4学时）
基本题一：最长公共子序列问题
一、实验目的与要求
1、熟悉最长公共子序列问题的算法；
2、初步掌握动态规划算法；
二、实验题
若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。
三、实验提示
include "stdlib.h"
#include "string.h"
void LCSLength(char *x ,char *y,int m,int n, int **c, int **b)
{
int i ,j;
for (i = 1; i <= m; i++) c[i][0] = 0;
for (i = 1; i <= n; i++) c[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
{
if (x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if (c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{ c[i][j]=c[i][j-1];
b[i][j]=3;
}
}
}
void LCS(int i ,int j, char *x ,int **b)
{
if (i ==0 || j==0) return;
if (b[i][j]== 1)
{
LCS(i-1,j-1,x,b);
printf("%c",x[i]);
}
else if (b[i][j]== 2)
LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}
基本题二：最大字段和问题
一、实验目的与要求
1、熟悉最长最大字段和问题的算法；
2、进一步掌握动态规划算法；
二、实验题
若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。
三、实验提示
int MaxSum(int n,int *a,int &besti,int &bestj)
{
intsum=0;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
{
int thissum=0;
for(int K=i;k<=j;k++)thissum+=a[k];
if(thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
return sum;
}
int MaxSum(int n,int *a,int &besti,int &bestj)
{
intsum=0;
for(int i=1;i<=n;i++)
{
int thissum=0;
for(intj=i;j<=n;j++)
{
thissum+=a[j];
if(thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
}
return sum;
}
提高题一： 用动态规划法求解0/1背包问题
一、实验要求与目的
1、 掌握动态规划算法求解问题的一般特征和步骤。
2、 使用动态规划法编程，求解0/1背包问题。
二、实验内容
1、 问题描述：给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？
2、 算法描述。
3、 程序实现；给出实例测试结果。
实验三贪心算法（2学时）
基本题一：多机调度问题
一、实验目的与要求
1、熟悉多机调度问题的算法；
2、初步掌握贪心算法；
二、实验题
要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。
三、实验提示
1、把作业按加工所用的时间从大到小排序
2、如果作业数目比机器的数目少或相等，则直接把作业分配下去
3、 如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。
typedef struct Job
{
int ID;//作业号
int time;//作业所花费的时间
}Job;
typedef struct JobNode //作业链表的节点
{
int ID;
int time;
JobNode *next;
}JobNode,*pJobNode;
typedef struct Header //链表的表头
{
int s;
pJobNode next;
}Header,pHeader;
int SelectMin(Header* M,int m)
{
int k=0;
for(int i=1;i<m;i++)
{
if(M[i].s<m[k].s)k=i;
}
return k;
提高题一： 用贪心算法求解最小生成树
一、实验要求与目的
1、 熟悉贪心算法的基本原理与适用范围。
2、 使用贪心算法编程，求解最小生成树问题。
二、实验内容
1、 任选一种贪心算法（Prim或Kruskal），求解最小生成树。对算法进行描述和复杂性分析。
编程实现，并给出测试实例
提高题二：汽车加油问题
一、实验目的与要求
1、掌握汽车加油问题的算法；
2、进一步掌握贪心算法；
二、实验题
一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。并证明你的算法能产生一个最优解。
三、实验提示
把两加油站的距离放在数组中，a[1..n]表示从起始位置开始跑，经过n个加油站，a[k]表示第k－1个加油站到第k个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。（算法略）
实验四回溯算法和分支限界法（2学时）
基本题一：符号三角形问题
一、实验目的与要求
1、掌握符号三角形问题的算法；
2、初步掌握回溯算法；
二、实验题图
下面都是“-”。 下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是“+”，2个异号下面都是“-”。
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
三、实验提示
void Triangle::Backtrack(int t)
{
if ((count>half)||(t*(t-1)/2-count>half)) return;
if (t>n) sum++;
else
for (int i=0;i<2;i++) {
p[1][t]=i;
count+=i;
for (int j=2;j<=t;j++) {
p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
count+=p[j][t-j+1];
}
Backtrack(t+1);
for (int j=2;j<=t;j++)
count-=p[j][t-j+1];
count-=i;
}
}
基本题二：0—1背包问题
一、实验目的与要求
1、掌握0—1背包问题的回溯算法；
2、进一步掌握回溯算法；
二、实验题：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
三、实验提示
template<class Typew, class Typep>
Typep Knap<Typew, Typep>::Bound(int i)
{// 计算上界
Typew cleft = c - cw; // 剩余容量
Typep b = cp;
// 以物品单位重量价值递减序装入物品
while (i <= n && w[i] <= cleft) {
cleft -= w[i];
b += p[i];
i++;
}
// 装满背包
if (i <= n) b += p[i]/w[i] * cleft;
return b;
}
提高题一：旅行商售货员问题的分支限界算法
一、实验目的与要求
1、掌握旅行商售货员问题的分支限界算法；
2、区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。
二、实验题：
某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。
三、实验提示
旅行商问题的解空间是一个排列树。有两种实现的方法。第一种是只使用一个优先队列，队列中的每个元素 中都包含到达根的路径。另一种是保留一个部分解空间树和一个优先队列，优先队列中 的元素并不包含到达根的路径。以下为第一种方法。
由于我们要寻找的是最小耗费的旅行路径，因此可以使用最小耗费分枝定界法。在实现过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHeapNode。每个节点包括如下区域： x（从1到n的整数排列，其中x[0] = 1 ），s（一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s], 而剩余待访问的节点是x [s + 1 : n - 1 ]），cc（旅行路径前缀，即解空间树中从根节点到当前节点的耗费），lcost（该节点子树中任意叶节点中的最小耗费）， rcost（从顶点x[s : n - 1]出发的所有边的最小耗费之和）。当类型为MinHeapNode( T )的数据被转换成为类型T时，其结果即为lcost的值。分枝定界算法的代码见程序
程序首先生成一个容量为100的最小堆，用来表示活节点的最小优先队列。活节点按lcost值从最小堆中取出。接下来，计算有向图中从每个顶点出发的边中 耗费最小的边所具有的耗费MinOut。如果某些顶点没有出边，则有向图中没有旅行 路径，搜索终止。如果所有的顶点都有出边，则可以启动最小耗费分枝定界搜索。根的孩子B作为第一个E-节点，在此节点上，所生成的旅行路径前缀只有一个顶点1，因此s=0, x[0]=1, x[1:n-1]是剩余的顶点（即顶点2 ， 3 ，.， n ）。旅行路径前缀1的开销为0 ，即cc = 0 ，并且，rcost=n && i=1时MinOut 。
在程序中，bestc 给出了当前能找到的最少的耗费值。初始时，由于没有找到任何旅行
路径，因此bestc的值被设为NoEdge。
旅行商问题的最小耗费分枝定界算法
template
T AdjacencyWDigraph::BBTSP(int v[])
{// 旅行商问题的最小耗费分枝定界算法
// 定义一个最多可容纳1000个活节点的最小堆
MinHeap > H(1000);
T *MinOut = new T [n+1];
// 计算MinOut = 离开顶点i的最小耗费边的耗费
T MinSum = 0; // 离开顶点i的最小耗费边的数目
for (int i = 1; i <= n; i++) {
T Min = NoEdge;
for (int j = 1; j <= n; j++)
if (a[j] != NoEdge && (a[j] < Min || Min == NoEdge))
Min = a[j];
if (Min == NoEdge) return NoEdge; // 此路不通
MinOut = Min;
MinSum += Min;
}
// 把E-节点初始化为树根
MinHeapNode E;
E.x = new int [n];
for (i = 0; i < n; i++)
E.x = i + 1;
E.s = 0; // 局部旅行路径为x [ 1 : 0 ]
E.cc = 0; // 其耗费为0
E.rcost = MinSum;
T bestc = NoEdge; // 目前没有找到旅行路径
// 搜索排列树
while (E.s < n - 1) {// 不是叶子
if (E.s == n - 2) {// 叶子的父节点
// 通过添加两条边来完成旅行
// 检查新的旅行路径是不是更好
if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && (E.cc +
a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc == NoEdge))
{
// 找到更优的旅行路径
bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1];
E.cc = bestc;
E.lcost = bestc;
E . s + + ;
H . I n s e r t ( E ) ; }
else delete [] E.x;}
else {// 产生孩子
for (int i = E.s + 1; i < n; i++)
if (a[E.x[E.s]][E.x] != NoEdge)
{
// 可行的孩子, 限定了路径的耗费
T cc = E.cc + a[E.x[E.s]][E.x];
T rcost = E.rcost - MinOut[E.x[E.s]];
T b = cc + rcost; //下限
if (b < bestc || bestc == NoEdge) {
// 子树可能有更好的叶子
// 把根保存到最大堆中
MinHeapNode N;
N.x = new int [n];
for (int j = 0; j < n; j++)
N.x[j] = E.x[j];
N.x[E.s+1] = E.x;
N.x = E.x[E.s+1];
N.cc = cc;
N.s = E.s + 1;
N.lcost = b;
N.rcost = rcost;
H . I n s e r t ( N ) ; }
} // 结束可行的孩子
delete [] E.x;} // 对本节点的处理结束
try {H.DeleteMin(E);} // 取下一个E-节点
catch (OutOfBounds) {break;} // 没有未处理的节点
}
if (bestc == NoEdge) return NoEdge; // 没有旅行路径
// 将最优路径复制到v[1:n] 中
for (i = 0; i < n; i++)
v[i+1] = E.x;
while (true) {//释放最小堆中的所有节点
delete [] E.x;
try {H.DeleteMin(E);}
catch (OutOfBounds) {break;}
}
return bestc;
}
提高题二：用回溯法求解跳马问题
一、实验要求与目的
1、 掌握回溯法的基本原理。
2、 使用回溯法编程，求解跳马问题
二、实验内容
1、 问题描述：在N*N棋盘上有N2个格子，马在初始位置（X0，Y0），按照象棋中马走“日”的规则，使马走遍全部格子且每个格子仅经过一次。编程输出马的走法。
2、 给出算法描述。
编程实现，给出N=5，（X0，Y0）=（1，1）时的运行结果。