算法设计与分析实验指导.doc

算法设计与分析实验指导

王歧 编实验一：递归与分治
1. 二分查找
2. 合并排序
3. 快速排序
实验二:回溯
1. 0—1背包问题
2. 装载问题
3. 堡垒问题（ZOJ1002）
4. *翻硬币问题
5. 8皇后问题
6. 素数环问题
7. 迷宫问题
8. ＊农场灌溉问题(ZOJ2412）
9. ＊求图像的周长（ZOJ1047）
10. *骨牌矩阵
11. ＊字母转换(ZOJ1003）
12. ＊踩气球（ZOJ1004）
实验三:搜索
1. Floodfill
2. 电子老鼠闯迷宫
3. 跳马
4. 独轮车
5. 皇宫小偷
6. 分酒问题
7. *找倍数
8. *8数码难题
实验四：动态规划
1. 最长公共子序列
2. 计算矩阵连乘积
3. 凸多边形的最优三角剖分
4. 防卫导弹
5. *石子合并
6. ＊最小代价子母树
7. *旅游预算
8. *皇宫看守
9. *游戏室问题
10. *基因问题
11. ＊田忌赛马
实验五：贪心与随机算法
1. 背包问题
2. 搬桌子问题
3. *照亮的山景
4. *用随即算法求解8皇后问题
5. 素数测试
实验一：递归与分治
实验目的
理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。
掌握分治算法的思想,对给定的问题能设计出分治算法予以解决.
实验预习内容
编程实现讲过的例题：二分搜索、合并排序、快速排序.
对本实验中的问题，设计出算法并编程实现.
试验内容和步骤
1． 二分查找
在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。
程序略
2． 合并排序
程序略
3． 快速排序
程序略
实验总结及思考
合并排序的递归程序执行的过程
实验二：回溯算法
实验目的：熟练掌握回溯算法
实验内容：回溯算法的几种形式
a) 用回溯算法搜索子集树的一般模式
void search（int m）
｛
if(m〉n) //递归结束条件
output()； //相应的处理(输出结果）
else
｛
a［m］=0； //设置状态：0表示不要该物品
search（m+1）; //递归搜索:继续确定下一个物品
a［m]=1； //设置状态：1表示要该物品
search（m+1)； //递归搜索：继续确定下一个物品
｝
}
b) 用回溯算法搜索子集树的一般模式
void search（int m)
{
if（m〉n） //递归结束条件
output(）； //相应的处理(输出结果)
else
for(i=m;i<=n；i++)
{
swap(m,i); //交换a[m]和a［i］
if(）
if(canplace(m）） //如果m处可放置
search(m+1); //搜索下一层
swpa（m，i); //交换a［m］和a[i］(换回来)
｝
｝
习题
1． 0—1背包问题
在0 / 1背包问题中，需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi .对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。
程序如下：
＃include <stdio。h〉
void readdata（);
void search（int）；
void checkmax（）；
void printresult()；
int c=35, n=10; //c： 背包容量；n:物品数
int w［10］, v［10］； //w[i］、v[i]：第i件物品的重量和价值
int a[10］, max; //a数组存放当前解各物品选取情况；max：记录最大价值
//a[i］=0表示不选第i件物品,a[i］=1表示选第i件物品
int main（)
{
readdata（); //读入数据
search(0); //递归搜索
printresult(）；
｝
void search(int m）
{
if(m〉=n)
checkmax()； //检查当前解是否是可行解，若是则把它的价值与max比较
else
{
a［m]=0; //不选第m件物品
search(m+1); //递归搜索下一件物品
a[m]=1； //不选第m件物品
search（m+1); //递归搜索下一件物品
}
}
void checkmax（)
{
int i， weight=0， value=0；
for(i=0;i〈n;i++)
｛
if(a[i]==1） //如果选取了该物品
｛
weight = weight + w[i］； //累加重量
value = value + v［i］; //累加价值
}
｝
if(weight<=c） //若为可行解
if（value>max) //且价值大于max
max=value; //替换max
｝
void readdata（)
{
int i;
for（i=0；i<n；i++)
scanf（"%d%d”，＆w［i]，&v［i］）； //读入第i件物品重量和价值
｝
void printresult（)
{
printf("%d”,max);
｝
2． 装载问题
有两艘船，载重量分别是c1、 c2，n个集装箱,重量是wi (i=1…n），且所有集装箱的总重量不超过c1+c2.确定是否有可能将所有集装箱全部装入两艘船.
提示：求出不超过c1的最大值max，若总重量－max < c2则能装入到两艘船。
3． 堡垒问题（ZOJ1002)
如图城堡是一个4×4的方格，为了保卫城堡，现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙,其余格子都是空格，堡垒只能建在空格里，每个堡垒都可以向上下左右四个方向射击，如果两个堡垒在同一行或同一列，且中间没有墙相隔,则两个堡垒都会把对方打掉。问对于给定的一种状态,最多能够修建几个堡垒.
程序主要部分如下：
int main(）
{
readdata(); //读入数据
search(0）； //递归搜索
printresult（);
｝
void search(int m）
｛
int row， col;
row=m/n; //求第m个格子的行号
col=m％n； //求第m个格子的列号
if(m>=n＊n）
checkmax(); //检查当前解是否是可行解，若是则把它的价值与max比较
else
{
search(m+1）； //该位置不放堡垒递归搜索下一个位置
if（canplace（m)) //判断第m个格子是否能放堡垒
｛
place（m); //在第m个格子上放置一个堡垒
search(m+1)； //递归搜索下一个位置
takeout（m)； //去掉第m个格子上放置的堡垒
}
}
}
4． 翻硬币问题
把硬币摆放成32×9的矩阵，你可以随意翻转矩阵中的某些行和某些列，问正面朝上的硬币最多有多少枚？
提示：（1）任意一行或一列，翻两次等于没有翻；
（2）对于9列的任何一种翻转的情况，每一行翻与不翻相互独立。
5． 8皇后问题
在一个８×８的棋盘里放置８个皇后，要求这8个皇后两两之间互相都不“冲突"。
#include 〈stdio.h〉
#include <math.h>
void search（int）;
void printresult（)； //打印结果
int canplace(int,int); //判断该位置能否放置皇后
void place（int，int）; //在该位置能否放置皇后
void takeout（int，int）； //把该位置放置皇后去掉
int a[8]； //a[i]存放第i个皇后的位置
int main()
{
search(0）； //递归搜索
｝
void search(int m)
｛
int i;
if(m>=8) //当已经找出一组解时
printresult(）； //输出当前结果
else
｛
for(i=0;i<8；i++） //对当前行0到7列的每一个位置
｛
if（canplace(m,i)） //判断第m个格子是否能放堡垒
{
place（m，i）； //在(m，i)格子上放置一个皇后
search（m+1); //递归搜索下一行
takeout（m，i)； //把(m,i)格子上的皇后去掉
}
}
｝
}
int canplace（int row， int col）
｛
int i；
for（i=0;i〈row;i++)
if(abs(i—row)==abs（a[i]—col）||a[i］==col）
return（0);
return（1）；
｝
void place（int row， int col）
{
a［row］=col；
}
void takeout（int row， int col）
{
a[row］=—1；
｝
void printresult()
｛
int i，j；
for(i=0;i〈8；i++）
｛
for（j=0；j<8；j++)
if（a[i］==j)
printf(" A "）;
else
printf(” 。 ”）;
printf（”\n”）；
}
printf("\n"）；
｝
6． 素数环问题
把从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数。
分析：用回溯算法，考察所有可能的排列。
程序如下：
＃include 〈stdio.h>
#include <math。h〉
void search(int）;
void init（); //初始化
void printresult(）; //打印结果
int isprime(int）； //判断该数是否是素数
void swap（int，int）; //交换a[m］和a［i］
int a[21］； //a数组存放素数环
int main()
{
init(）;
search(2）; //递归搜索
}
int isprime（int num)
{
int i，k；
k=sqrt(num）;
for(i=2；i〈=k;i++)
if(num%i==0）
return（0);
return（1)；
}
void printresult(）
｛
int i；
for(i=1；i〈=20;i++）
printf("%3d”，a［i]);
printf("\n”);
｝
void search（int m）
{
int i；
if（m>20) //当已经搜索到叶结点时
{
if（isprime(a[1］+a［20］）） //如果a［1］+a［20］也是素数
printresult（); //输出当前解
return；
｝
else
{
for（i=m;i〈=20；i++) //（排列树）
｛
swap（m,i); //交换a［m］和a[i］
if(isprime（a［m—1]+a［m])) //判断a［m—1］+a［m]是否是素数
search(m+1）; //递归搜索下一个位置
swap(m,i); //把a［m］和a[i］换回来
｝
｝
｝
void swap(int m, int i)
{
int t；
t=a［m]；
a[m]=a[i］；
a[i］=t;
}
void init(）
{
int i；
for(i=0；i<21;i++)
a［i］=i;
}
7． 迷宫问题
给一个20×20的迷宫、起点坐标和终点坐标，问从起点是否能到达终点。
输入数据：’.’表示空格;'X’表示墙。
程序如下：
#include <stdio。h〉
＃include <math.h>
void search(int,int）;
int canplace（int,int);
void readdata（)； //读入数据
void printresult（）; //打印结果
int a［20]［20]； //a数组存放迷宫
int s，t；
int main(）
｛
int row， col;
readdata（）;
row=s/20;
col=s％20;
search（row，col）; //递归搜索
printresult（)；
｝
void search(int row, int col）
{
int r，c;
a[row][col]=1；
r=row； //左
c=col—1;
if（canplace（r，c)） //判断（r,c)位置是否已经走过
search（r，c）； //递归搜索（r,c）
r=row+1; //下
c=col;
if（canplace(r，c)) //判断（r，c)位置是否已经走过
search（r,c)； //递归搜索(r,c）
r=row; //右
c=col+1;
if（canplace（r,c）） //判断(r，c)位置是否已经走过
search(r，c）; //递归搜索(r，c)
r=row-1; //上
c=col;
if(canplace（r,c）） //判断（r,c）位置是否已经走过
search(r，c); //递归搜索（r,c)
}
void printresult（)
｛
int i,j;
for（i=0；i〈20；i++)
{
for(j=0;j<20;j++）
printf(”％3d”,a[i］[j]）;
printf（”\n”)；
｝
｝
void readdata(）
{
int i，j;
for(i=0；i<20；i++）
{
for(j=0；j〈20;j++）
scanf("%d"，＆a[i］［j])；
}
}
int canplace（int row, int col)
{
if（row>=0&&row<20&&col〉=0&＆col〈20&&a［row]［col]==0)
return 1;
else
return 0；
｝

8． 农场灌溉问题（ZOJ2412）
一农场由图所示的十一种小方块组成,蓝色线条为灌溉渠.若相邻两块的灌溉渠相连则只需一口水井灌溉。给出若干由字母表示的最大不超过50×50具体由（m，n）表示的农场图,编程求出最小需要打的井数.每个测例的输出占一行。当M=N=-1时结束程序。

Sample Input
2 2
DK
HF
3 3
ADC
FJK
IHE
—1 —1
Sample Output
2
3
提示：参考迷宫问题，实现时关键要解决好各块的表示问题.
9． 求图像的周长（ZOJ1047）
给一个用 。 和X表示的图形，图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的,并且图像中间不会出现空洞，求这个图形的边长。
输入:首先给出m、n、x、y四个正整数,下面给出m×n的图形，x、y表示点击的位置，全0表示结束.
输出：点击的图形的周长。

Sample Input
2 2 2 2
XX
XX
6 4 2 3
。XXX
.XXX
。XXX
...X
。。X.
X...
0 0 0 0
Sample output
8
18
提示：参考迷宫问题，区别在于它是向8个方向填。

10． 骨牌矩阵
多米诺骨牌是一个小正方形方块，每个骨牌都标有一个数字（0～6）,现在有28组骨牌，每组两个，各组编号为1~28，每组编号对应的两个骨牌数值如下：
00 01 02 03 04 05 06
11 12 13 14 15 16 22
23 24 25 26 33 34 35
36 44 45 46 55 56 66
现将这28组骨牌排成一个7×8矩阵，此时只能看到每个骨牌上的数字（0～6)，而不能知道每组的组号（如左下图所示）。请编程序将每组骨牌分辨出来（如右下图所示）.
7X8骨牌矩阵 骨牌组编号矩阵
66265241 28 28 14 7 17 17 11 11
13201034 10 10 14 7 2 2 21 23
13246654 8 4 16 25 25 13 21 23
10432112 8 4 16 15 15 13 9 9
51360455 12 12 22 22 5 5 26 26
55402603 27 24 24 3 3 18 1 19
60534203 27 6 6 20 20 18 1 19
void search(int n)
{
查找下一个还没放置骨牌的位置(x,y)；
若没有，则表示已经找到一个解,输出并且返回；
尝试放置骨牌;
两次尝试都失败，进行回溯；
｝
尝试放置骨牌
l 把在(x,y)处的骨牌作为当前骨牌组的一个骨牌；
l 把(x+1,y）处的骨牌作为当前骨牌组的另一个骨牌；
l 判断当前骨牌组是够未被使用，如果未被使用则递归放置下一个骨牌组；
l 把（x,y +1)处的骨牌作为当前骨牌组的另一个骨牌；
l 判断当前骨牌组是否未被使用,如果未被使用则递归放置下一个骨牌组;

11． 字母转换(ZOJ1003）
通过栈交换字母顺序。给定两个字符串,要求所有的进栈和出栈序列（i表示进栈,o表示出栈），使得字符串2在求得的进出栈序列的操作下,变成字符串1。输出结果需满足字典序。例如TROT 到 TORT:
[
i i i i o o o o
i o i i o o i o
]
Sample Input
madam
adamm
bahama
bahama
long
short
eric
rice
Sample Output
［
i i i i o o o i o o
i i i i o o o o i o
i i o i o i o i o o
i i o i o i o o i o
]
［
i o i i i o o i i o o o
i o i i i o o o i o i o
i o i o i o i i i o o o
i o i o i o i o i o i o
]
[
］
[
i i o i o i o o
]

12． 踩气球（ZOJ1004）
六一儿童节，小朋友们做踩气球游戏,气球的编号是1～100，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的:如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。
输入为两个数字,0 0表示结束；
输出为获胜的数字。
Sample Input
36 62
49 343
0 0
Sample Output
62
49
实验三：搜索算法
实验目的：熟练掌握搜索算法
实验内容：广度优先搜索
搜索算法的一般模式：
void search(）
｛
closed表初始化为空;
open表初始化为空;
起点加入到open表；
while( open表非空 )
{
取open表中的一个结点u；
从open表中删除u；
u进入closed表；
for( 对扩展结点u得到的每个新结点vi ）
{
if（vi是目标结点)
输出结果并返回;
if vi 的状态与closed表和open表中的结点的状态都不相同
vi进入open表;
}
}
｝
搜索算法关键要解决好状态判重的问题,这样可省略closed表，一般模式可改为:
void search(）
{
open表初始化为空；
起点加入到open表;
while( open表非空 )
{
取open表中的一个结点u;
从open表中删除u;
for（ 对扩展结点u得到的每个新结点vi ）
{
if(vi是目标结点)
输出结果并返回；
If（notused（vi))
vi进入open表；
｝
｝
｝
1. Floodfill
给一个20×20的迷宫和一个起点坐标，用广度优先搜索填充所有的可到达的格子。
提示：参考第2题。
2. 电子老鼠闯迷宫
如下图12×12方格图，找出一条自入口（2，9）到出口（11，8）的最短路径.

本题给出完整的程序和一组测试数据。状态：老鼠所在的行、列。程序如下：
＃include<stdio。h>
void readdata(); //读入数据
void init（）； //初始化
int search（)； //广搜，并在每一个可到达的每一个空格出填上最小步数
int emptyopen（）; //判栈是否为空:空：1；非空：0。
int takeoutofopen(）； //从栈中取出一个元素，并把该元素从栈中删除
int canmoveto（int，int,int*,int*,int)； //判能否移动到该方向，并带回坐标(r，c)
int isaim（int row, int col）； //判断该点是否是目标
int used(int,int）； //判断该点是否已经走过
void addtoopen（int，int）; //把该点加入到open表
int a[12]［12］; //a存放迷宫,0表示空格,-2表示墙。
//广搜时，未找到目标以前到达的空格，填上到达该点的最小步数
int n； //n为迷宫边长，注：若大于12,必须修改一些参数,如a的大小
int open[20]，head，tail,openlen=20； //open表
int s,t; //起点和终点
int main()
｛
int number；
readdata(); //读取数据
init（）； //初始化
number=search（）； //广搜并返回最小步数
printf(”％d”,number)； //打印结果
｝
int search（）
｛
int u， row, col, r， c, i， num;
while（!emptyopen()） //当栈非空
{
u=takeoutofopen(）； //从栈中取出一个元素,并把该元素从栈中删除
row=u/n; //计算该点的坐标
col=u%n；
num=a［row]［col］； //取得该点的步数
for（i=0;i<4；i++）
{
if（canmoveto（row，col，＆r,&c，i）) //判能否移动到该方向，并带回坐标（r，c）
{
if（isaim（r,c）) //如果是目标结点
return(num+1); //返回最小步数
if(!used(r,c）） //如果（r,c）还未到达过
｛
a[r］［c］=num+1； //记录该点的最小步数
addtoopen（r，c）; //把该点加入到open表
}
｝
｝
}
｝
int emptyopen()
{
if(head==tail)
return(1）；
else
return（0）;
｝
int takeoutofopen（）
｛
int u；
if(head==tail)
｛
printf（"errer： stack is empty”）;
return（-1）；
}
u=open[head++]；
head=head%openlen;
return（u）;
}

int canmoveto（int row， int col, int *p, int *q, int direction)
｛
int r，c；
r=row;
c=col；
switch（direction)
{
case 0： c—-; //左
break;
case 1: r++; //下
break;
case 2： c++； //右
break;
case 3: r-—; //上
｝
*p=r；
*q=c；
if(r<0|｜r>=n|｜c<0|｜c>=n） //如果越界返回0
return（0）;
if（a［r]［c］==0） //如果是空格返回1
return（1）；
return(0）; //其余情况返回0
}
int isaim(int row， int col）
{
if(row＊n+col==t)
return（1）；
else
return（0);
}
int used(int row, int col）
｛
if(a［row］［col]==0） // 0表示空格
return（0)；
else
return（1）；
｝
void addtoopen(int row， int col)
{
int u；
u=row*n+col;
open[tail++]= u;
tail=tail％openlen；
}
void readdata（)
｛
int i,j，row，col；
char str［20];
scanf(”%d"，＆n）;
scanf(”%d%d",＆row，＆col); //起点坐标
s=row*n+col;
scanf("％d%d”,&row,＆col）; //终点坐标
t=row＊n+col;
gets（str）；
for（i=0;i<n;i++）
｛
gets（str）;
for(j=0；j<n;j++）
if（str［j］=='.’）
a[i][j]=0； //0表示空格
else
a[i]［j]=-2； //－2表示墙
}
｝
void init(）
{
head=0；
tail=1；
open[0］=s；
}
测试数据如下：
12 10 7 1 8
XXXXXXXXXXXX
X.。。..。X。XXX
X。X。XX...。.X
X。X。XX。XXX。X
X。X...。.X。.X
X.XXXXXXXXXX
X.。。X.X....X
X。XXX。..XXXX
X..。.。X.。..X
XXX.XXXX。X.X
XXXXXXX。。XXX
XXXXXXXXXXXX
注：测试数据可在运行时粘贴上去（点击窗口最左上角按钮，在菜单中选则“编辑”/“粘贴”即可）。
想一想：此程序都存在哪些问题，如果openlen太小程序会不会出错,加入代码使程序能自动报出此类错误.
3. 跳马
给一个200×200的棋盘,问国际象棋的马从给定的起点到给定的终点最少需要几步。
Sample Input 0 0 1 1 Sample output 4
状态:马所在的行、列.
程序如下：
#include<stdio。h〉
void readdata(）; //读入数据
void init(); //初始化
int search（）; //广度优先搜索
int emptyopen(）； //判栈是否为空：空：1；非空：0。
long takeoutofopen（); //从栈中取出一个元素，并把该元素从栈中删除
int canmoveto(int，int，int*,int＊，int); //判能否移动到该方向,并带回坐标(r,c）
int isaim（int row， int col）； //判断该点是否是目标
int used（int,int)； //判断该点是否已经走过
void addtoopen（int,int); //把该点加入到open表
int a［200］[200］，n=200； //a存放棋盘，n为迷宫边长
long open［2000]，head，tail,openlen=2000; //open表1367
long s,t; //起点和终点
int search（)
｛
long u;
int row, col, r, c， i, num;
while(!emptyopen(）) //当栈非空
{
u=takeoutofopen（)； //从栈中取出一个元素，并把该元素从栈中删除
row=u/n； //计算该点所在的行
col=u%n； //计算该点所在的列
num=a［row］［col］； //取得该点的步数
for(i=0;i〈8；i++）
｛
if(canmoveto（row,col，＆r，&c,i)） //判能否移动到该方向，并带回坐标(r,c)
｛
if（isaim（r,c)) //如果是目标结点
return(num+1)； //返回最小步数
if（!used(r，c）） //如果（r,c）还未到达过
｛
a［r]［c]=num+1; //记录该点的最小步数
addtoopen(r，c）； //把该点加入到open表
｝
｝
}
｝
return -1；
｝
int main(） //为了让search(）显示在一页内和main函数换了以下
{