文档介绍：算法设计与分析实验指导
王歧 编
实验一:递归与分治
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 <>
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