算法设计与分析实验指导

《算法设计与分析实验指导》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法设计与分析实验指导王歧编实验一：递归与分治1.二分查找2.合并排序3.快速排序实验二：回溯1.0-1背包问题2.装载问题3.堡垒问题（ZOJ1002）4.*翻硬币问题5.8皇后问题6.素数环问题7.迷宫问题8.*农场灌溉问题（ZOJ2412）9.*求图像的周长（ZOJ1047）10.*骨牌矩阵11.*字母转换（ZOJ1003）12.*踩气球（ZOJ1004）实验三：搜索1.Floodfill2.电子老鼠闯迷宫3.跳马4.独轮车5.皇宫小偷6.分酒问题7.*找倍数8.*8数码难题实验四：动态规划1

2、.最长公共子序列2.计算矩阵连乘积3.凸多边形的最优三角剖分4.防卫导弹5.*石子合并6.*最小代价子母树7.*旅游预算8.*皇宫看守9.*游戏室问题10.*基因问题11.*田忌赛马实验五：贪心与随机算法1.背包问题2.搬桌子问题3.*照亮的山景4.*用随即算法求解8皇后问题5.素数测试实验一：递归与分治实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。实验预习内容编程实现讲过的例题：二分搜索、合并排序、快速排序。对本实验

3、中的问题，设计出算法并编程实现。试验内容和步骤1．二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。程序略2．合并排序程序略3．快速排序程序略实验总结及思考合并排序的递归程序执行的过程实验二：回溯算法实验目的：熟练掌握回溯算法实验内容：回溯算法的几种形式a)用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)else{a

4、[m]=0;//设置状态：0表示不要该物品search(m+1);//递归搜索：继续确定下一个物品a[m]=1;//设置状态：1表示要该物品search(m+1);//递归搜索：继续确定下一个物品}}b)用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)elsefor(i=m;i<=n;i++){swap(m,i);//交换a[m]和a[i]if()if(canplace(m))//如果m处可放置search(m

5、+1);//搜索下一层swpa(m,i);//交换a[m]和a[i](换回来)}}习题1．0-1背包问题在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。程序如下：#includevoidreaddata();voidsearch(int);voidcheckmax();voidprintresult();intc=35,n=

6、10;//c：背包容量；n：物品数intw[10],v[10];//w[i]、v[i]：第i件物品的重量和价值inta[10],max;//a数组存放当前解各物品选取情况；max：记录最大价值//a[i]=0表示不选第i件物品，a[i]=1表示选第i件物品intmain(){readdata();//读入数据search(0);//递归搜索printresult();}voidsearch(intm){if(m>=n)checkmax();//检查当前解是否是可行解，若是则把它的价值与max比较el

7、se{a[m]=0;//不选第m件物品search(m+1);//递归搜索下一件物品a[m]=1;//不选第m件物品search(m+1);//递归搜索下一件物品}}voidcheckmax(){inti,weight=0,value=0;for(i=0;imax)//且价值大于max

8、max=value;//替换max}voidreaddata(){inti;for(i=0;i