算法设计与分析实验指导
王歧 编
实验一:递归与分治
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×8的棋盘里放置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; /