《算法设计与分析》实验指导书bfm全.docx
《《算法设计与分析》实验指导书bfm全.docx》由会员分享，可在线阅读，更多相关《《算法设计与分析》实验指导书bfm全.docx（20页珍藏版）》请在冰点文库上搜索。
《算法设计与分析》实验指导书bfm全
《算法设计与分析》实验指导书
计算机学院信息安全系毕方明
本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。
上机实验一般应包括以下几个步骤：
（1）、准备好上机所需的程序。
手编程序应书写整齐，并经人工检查无误后才能上机。
（2）、上机输入和调试自己所编的程序。
一人一组，独立上机调试，上机时出现的问题，最好独立解决。
（3）、上机结束后，整理出实验报告。
实验报告应包括：
题目、程序清单、运行结果、对运行情况所作的分析。
本书共分阶段4个实验，每个实验有基本题和提高题。
基本题必须完成，提高题根据自己实际情况进行取舍。
题目不限定如下题目，可根据自己兴趣爱好做一些与实验内容相关的其他题目，如动态规划法中的图象压缩，回溯法中的人机对弈等。
其具体要求和步骤如下：
实验一分治与递归（4学时）
基本题一：
基本递归算法
一、实验目的与要求
1、熟悉C/C++语言的集成开发环境；
2、通过本实验加深对递归过程的理解
二、实验内容：
掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。
三、实验题
任意输入一个整数，输出结果能够用递归方法实现整数的划分。
四、实验步骤
1．理解算法思想和问题要求；
2．编程实现题目要求；
3．上机输入和调试自己所编的程序；
4．验证分析实验结果；
5．整理出实验报告。
基本题二：
棋盘覆盖问题
一、实验目的与要求
1、掌握棋盘覆盖问题的算法；
2、初步掌握分治算法
二、实验题：
盘覆盖问题：
在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
三、实验提示
voidchessBoard（inttr,inttc,intdr,intdc,intsize）
{
if（size==1）return;
intt=tile++, //L型骨牌号
s=size/2; //分割棋盘
//覆盖左上角子棋盘
if（dr //特殊方格在此棋盘中
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=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 //特殊方格在此棋盘中
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做参数，且采用传递引用或指针的形式带回值。
boolBinarySearch（inta[],intn,intx,int&i,int&j）
{
intleft=0;
intright=n-1;
while（left {
intmid=（left+right）/2;
if（x==a[mid]）
{
i=j=mid;
returntrue;
}
if（x>a[mid]）
left=mid+1;
else
right=mid-1;
}
i=right;
j=left;
returnfalse;
}
intSearchTag（inta[],intn,intx）
{
intleft=0;
intright=n-1;
while（left {
intmid=（left+right）/2;
if（x==a[mid]）returnmid;
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"
voidLCSLength（char*x,char*y,intm,intn,int**c,int**b）
{
inti,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;
}
elseif（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;
}
}
}
voidLCS（inti,intj,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]）;
}
elseif（b[i][j]==2）
LCS（i-1,j,x,b）;
elseLCS（i,j-1,x,b）;
}
基本题二：
最大字段和问题
一、实验目的与要求
1、熟悉最长最大字段和问题的算法；
2、进一步掌握动态规划算法；
二、实验题
若给定n个整数组成的序列a1，a2，a3，……an，求该序列形如ai＋ai＋1＋……＋an的最大值。
三、实验提示
intMaxSum（intn,int*a,int&besti,int&bestj）
{
intsum=0;
for（inti=1;i<=n;i++）
for（intj=i;j<=n;j++）
{
intthissum=0;
for（intK=i;k<=j;k++）thissum+=a[k];
if（thissum>sum）
{
sum=thissum;
besti=i;
bestj=j;
}
}
returnsum;
}
intMaxSum（intn,int*a,int&besti,int&bestj）
{
intsum=0;
for（inti=1;i<=n;i++）
{
intthissum=0;
for（intj=i;j<=n;j++）
{
thissum+=a[j];
if（thissum>sum）
{
sum=thissum;
besti=i;
bestj=j;
}
}
}
returnsum;
}
提高题一：
用动态规划法求解0/1背包问题
一、实验要求与目的
1、掌握动态规划算法求解问题的一般特征和步骤。
2、使用动态规划法编程，求解0/1背包问题。
二、实验内容
1、问题描述：
给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，问如何选择装入背包的物品，使得装入背包的物品的总价值最大？
2、算法描述。
3、程序实现；给出实例测试结果。
实验三贪心算法（2学时）
基本题一：
多机调度问题
一、实验目的与要求
1、熟悉多机调度问题的算法；
2、初步掌握贪心算法；
二、实验题
要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。
作业不能拆分成更小的子作业。
三、实验提示
1、把作业按加工所用的时间从大到小排序
2、如果作业数目比机器的数目少或相等，则直接把作业分配下去
3、 如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。
typedefstructJob
{
intID;//作业号
inttime;//作业所花费的时间
}Job;
typedefstructJobNode//作业链表的节点
{
intID;
inttime;
JobNode*next;
}JobNode,*pJobNode;
typedefstructHeader //链表的表头
{
ints;
pJobNodenext;
}Header,pHeader;
intSelectMin（Header*M,intm）
{
intk=0;
for（inti=1;i {
if（M[i].s }
returnk;
提高题一：
用贪心算法求解最小生成树
一、实验要求与目的
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，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。
三、实验提示
voidTriangle:
:
Backtrack（intt）
{
if（（count>half）||（t*（t-1）/2-count>half））return;
if（t>n）sum++;
else
for（inti=0;i<2;i++）{
p[1][t]=i;
count+=i;
for（intj=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（intj=2;j<=t;j++）
count-=p[j][t-j+1];
count-=i;
}
}
基本题二：
0—1背包问题
一、实验目的与要求
1、掌握0—1背包问题的回溯算法；
2、进一步掌握回溯算法；
二、实验题：
给定n种物品和一背包。
物品i的重量是wi，其价值为vi，背包的容量为C。
问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
三、实验提示
template
TypepKnap:
:
Bound（inti）
{//计算上界
Typewcleft=c-cw; //剩余容量
Typepb=cp;
//以物品单位重量价值递减序装入物品
while（i<=n&&w[i]<=cleft）{
cleft-=w[i];
b+=p[i];
i++;
}
//装满背包
if（i<=n）b+=p[i]/w[i]*cleft;
returnb;
}
提高题一：
旅行商售货员问题的分支限界算法
一、实验目的与要求
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
TAdjacencyWDigraph:
:
BBTSP（intv[]）
{//旅行商问题的最小耗费分枝定界算法
//定义一个最多可容纳1000个活节点的最小堆
MinHeap>H（1000）;
T*MinOut=newT[n+1];
//计算MinOut=离开顶点i的最小耗费边的耗费
TMinSum=0;//离开顶点i的最小耗费边的数目
for（inti=1;i<=n;i++）{
TMin=NoEdge;
for（intj=1;j<=n;j++）
if（a[j]!
=NoEdge&&（a[j]Min=a[j];
if（Min==NoEdge）returnNoEdge;//此路不通
MinOut=Min;
MinSum+=Min;
}
//把E-节点初始化为树根
MinHeapNodeE;
E.x=newint[n];
for（i=0;iE.x=i+1;
E.s=0;//局部旅行路径为x[1:
0]
E.cc=0;//其耗费为0
E.rcost=MinSum;
Tbestc=NoEdge;//目前没有找到旅行路径
//搜索排列树
while（E.sif（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=E.cc+a[E.x[n-2]][E.x[n-
升级会员 