算法设计与分析实验指导

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

1、算法设计与分析实验指导实验目的：通过以K实验PJ容帮助学生理解与掌握并灵活运用算法的分析方法，算法的设计策略等实验一：递归与分治1.二分查找2.合并排序3.快速排序实验二：回溯1.0-1竹包问题2.装载问题3.堡垒问题(ZOJ1002)4.*翻硬币问题5.8皇后问题6.素数环问题7.迷宫问题8.*农场灌溉W题(ZOJ2412)9.*求阁像的周长(ZOJ1047)10.*骨牌矩阵11.*字母转换(ZOJ1003)12.*踩气球(ZOJ1004)实验三：搜索1.Floodfill2.电了老鼠闯迷宫3.跳马4.独轮车

2、5.皇宫小偷6.分酒问题7.*找倍数8.*8数码难题实验卩4:动态规划1.最长公共子序列2.计算矩阵连乘积3.凸多边形的最优三角剖分4.防卫导弹5.*石子合并6.*最小代价子母树7.*旅游预算8.*皇宫看守9.*游戏室问题10.*基因问题11.*田忌赛马实验五：贪心与随机算法1.背包问题2.搬桌了问题3.*照亮的山景4.*用随即兑法求解8皇后W题1.素数测试实验一：递归与分治实验目的理解递yI算法的思想和递归程序的执行过程，并能熟练编％递!n程序。掌掘分治算法的思想，对给定的问题能设计川分治算法予以解决。实验预

3、习内容编程实现讲过的例题：二分搜索、合弁排序、快速排序。对木实验屮的w题，设计出算法丼编程实现。试验内容和步骤1.二分査找在对线性表的操作屮，经常需要丧找某一个元素在线性表屮的位置。此问题的输入是待查元素x和线性表L,输出为x在L屮的位a或者x不在L屮的信怠。程序略2.合并排序程序略3.快速排序程序略实验总结及思考合并排序的递归程序执行的过程实验二：回溯算法实验H的：熟练掌握冋溯算法实验内容：回溯算法的儿种形式a）川回溯算法搜索了集树的一般模式voidsearch（intm）if(m>n)output();el

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

5、(m))//如果m处可放Ssearch(m+l);//搜索下一层swpa(m,i);//交换a[m]和a[i](换回來)习题1.0-1背包闷题在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物见，每件物品i的重量为wi,价伉为pi。对于付行的竹包装载，竹包中物品的总重量不能超过背包的容量，蝻佳装载是指所装入的物品价值蛣高。程序如下：//includevoidreaddata();voidsearch(int);voidcheckmax();voidprintrcsul

6、t();intc=35,n=10;intw[10],v[10];inta[10]，max;intmain()//c：背乜容量；n:物品数//w[i]、v[i]:第i件物品的重量和价值//a数组存放当前解各物品选取悄况；max：记录最人价位//a[i]=0表示不选第i件物品，a[i]=l表示选第i件物品readdata();//读入数据search(O);//递归搜索printresultO；}voidscarch(intm){if(m>=n)checkmax();//检否当前解是否是可行解，若是则把它的价位与m

7、ax比较elsea[m]=0;//不选弟m件物品search(m+l);//递归搜索F—件物品a[m]=l;//不选第m件物品search(m+l);//递归搜索下一件物品voidcheckmax()inti,weight=0,value=0;for(i=0;imax)max=value;}voidreaddata(){inti;for(i=0;i

8、i++)scanf("%d%d”,&w[i]，&v[i]);//如果选取了该物品//累加重量//累加价值//若为可行解//且价值人于max//替换max//读入第i件物品重3和价值voidprintrcsult()printf("%dH，max);2.裝载问题冇两艘船，载重最分别是cl、c2,n个集装箱，重量是Wi(i=l...n)，且所冇集装箱的总重景不超过cl+c2o确定是否有可能