yls 算法设计与分析实验指导

1、算法设计和分析实验指导馀资生篇实验1 :递归和分治1 .二分检索2 .合并排序3 .快速排序实验2 :倒退1. 0-1背包问题2 .安装问题3 .堡垒问题(ZOJ1002 )4. *翻硬币的问题5. 8皇后问题6 .素数循环问题七.迷宫问题8. *农场灌溉问题(ZOJ2412 )9. *求出图像的周长(ZOJ1047 )10. *多米诺骨牌矩阵11. *字母转换(ZOJ1003 )踩气球(ZOJ1004 )实验3 :检索1. Floodfill2 .电子老鼠侵入迷宫3 .跳马4 .独轮车5 .皇居贼6 .分酒问题7. *找倍数8. *8数字课题实验4 :动态计划1 .最长公共子序列2 .计算矩

2、阵连接积3 .凸多边形的最佳三角形化4 .防卫导弹5. *石的合并6. *最小成本子母树7. *旅行预算8. *宫的看守人9. *游戏室问题10. *基因问题11. *田忌赛马实验5 :贪婪和随机算法1 .背包问题2 .搬运桌子的问题3. *照耀的山景4. *用立即算法解决皇后问题5 .素数测试实验1 :递归和分离实验的目的理解递归算法的思想和递归程序的执行过程，能很好地写递归程序。掌握分治算法的思想，可以对给定的问题设计和解决分治算法。实验预习内容编程实现中叙述的例题：二分搜索、综合排序、高速排序。针对本实验中的问题，设计并编程实现了算法。考试内容和步骤1 .二分检索使用线性表时，经常需要检

3、查元素在线性表中的位置。 这个问题的输入是检查等待要素x和线性表l，作为x在l中还是x不在l中的信息而输出。程序略2 .合并排序程序略3 .快速排序程序略实验的总结和思考结合和执行排序的递归程序的过程实验2 :回溯算法实验目的：熟练使用回溯算法。实验内容：回溯算法的几种形式a )用回溯算法搜索子集树的一般模式void搜索(PS m )举止if(mn) /递归结束条件output ()； /相应的处理(输出结果)else举止am=0； /安装状态： 0表示不需要此项目search(m 1) /递归搜索：继续确定以下项目am=1； /设置状态： 1表示想要那个商品search(m 1) /递归搜索

4、：继续确定以下项目以下以下b )用回溯算法搜索子集树的一般模式void搜索(PS m )举止if(mn) /递归结束条件output ()； /相应的处理(输出结果)elsefor(i=m； i=n； PS )举止交换交换(m，i) am和ai。PS ()如果可以放在if(canplace(m) /的地方的话搜索(m1 )/下一层交换swpa(m，i) am和ai。以下以下练习题1. 0-1背包问题在0/1背包问题中，需要加载容量为c的背包。 从n个物品中选择装有背包的物品，1个物品I的重量为wi，价值为pi。 对于可能的背包装载，背包中物品的总重量不得超过背包的容量。 最佳装载是指装载的物品

5、价值最高。程序如下所示：#includevoid读数据()；void搜索(int )void检查max ()；void打印结果()；int c=35，n=10； /c :背包容量n :物件数int w10，v10； /wi、vi :第I项的重量和价值PS 10 、max； /a排列现在解收纳各物品的选择状况的max :记录的最大价值/ai=0表示没有选择第I个项目，ai=1表示选择第I个项目int main ()举止readdata ()； /读入数据search(0) /递归检索打印结果()；以下void搜索(PS m )举止if(m=n )checkmax ()； /检查现在的解是否是可能

6、的解，将其价值与max进行比较else举止am=0；/不选择第m个项目递归搜索search(m 1) /下一个项目am=1；/不选择第m个项目递归搜索search(m 1) /下一个项目以下以下void检查max ()举止int i，weight=0，值=0；for(i=0； imax) /且价值大于max最大值； 替换/max以下void读数据()举止PS；for(i=0； i=n*n )检查最大()； /检查现在的解是否是可能的解，将其价值与max进行比较else举止search(m 1) /这个位置放置堡垒不递归地搜索下一个位置判断第if(canplace(m) /个格子是否能放置堡垒举

7、止在第place(m) /m格子上设置堡垒递归查找search(m 1) /下一个位置清除放置在第takeout(m) /m个格子上的堡垒以下以下以下4 .翻硬币的问题把硬币排列成329个行列的话，可以自由翻转行列的一部分行和一部分列，问正面朝上的硬币最多有几枚提示： (1)反转任何行或列两次等于不反转(2)9列中任意一列反转时，是否逐行反转是相互独立的。5. 8皇后问题在88个棋盘上放了8个女王，要求这8个女王不要互相“冲突”。#include#includevoid搜索(int )void打印结果()； /打印结果判断能否放置int canplace(int，int) /女王void pl

8、ace(int，int) /能否把女王放在这个位置上void takeout(int，int) /把这个位置放在女王身上PS 8； /a容纳第 I 个女王的地方int main ()举止search(0) /递归检索以下void搜索(PS m )举止PS；找到一组if(m=8) /解时打印结果()； /输出当前结果else举止for(i=0； i8； i ) /当前行中0到7列的所有位置举止if(canplace(m，i) /判断第二个格子是否能放置堡垒举止把女王放在place(m，I) /(m，I )格子上递归查找search(m 1) /下一行takeout(m，I) /去除格子上的女王以

9、下以下以下以下int canplace(int row，int col )举止PS；for(i=0； I#includevoid搜索(int )void init ()； /初始化void打印结果()； /打印结果int isprime(int) /判断该数是否为素数更换语音交换(入，入) ai和ai。PS 21 ； /a数组存储素数循环int main ()举止init ()；搜索(2)/递归搜索以下int isprime(int num )举止PS，R；k=sqrt(num )for(i=2； i=k； PS )PS (数字% I=0)返回(0)返回(1)以下void打印结果()举止PS；

10、for(i=1； i=20； PS )打印(=， ai )；printf(n )；以下void搜索(PS m )举止PS；找到if(m20) /叶节点时举止if (isprime (a 1 a 20 )/a 1 a 20 也是素数的话打印结果()； /输出当前解返回；以下else举止for(i=m； i=20； i ) /(数组树)举止交换交换(m，i) am和ai。确定if (isprime (a m-1 a m )/a m-1 a m 是否为素数递归搜索search(m 1) /下一个位置交换交换(m，i) am和ai。以下以下以下void swap(int m，int i )举止PR；t=am；am=ai；ai=t；以下void init ()举止PS；for(i=0； i21； PS