算法设计与分析实验指导.doc
《算法设计与分析实验指导.doc》由会员分享,可在线阅读,更多相关《算法设计与分析实验指导.doc(41页珍藏版)》请在三一文库上搜索。
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. 计算矩阵连乘积3. 凸多
2、边形的最优三角剖分4. 防卫导弹5. *石子合并6. *最小代价子母树7. *旅游预算8. *皇宫看守9. *游戏室问题10. *基因问题11. *田忌赛马实验五:贪心与随机算法1. 背包问题2. 搬桌子问题3. *照亮的山景4. *用随即算法求解8皇后问题5. 素数测试实验一:递归与分治实验目的理解递归算法的思想和递归程序的执行过程,并能熟练编写递归程序。掌握分治算法的思想,对给定的问题能设计出分治算法予以解决。实验预习内容编程实现讲过的例题:二分搜索、合并排序、快速排序。对本实验中的问题,设计出算法并编程实现。试验内容和步骤1 二分查找在对线性表的操作中,经常需要查找某一个元素在线性表中的
3、位置。此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息。程序略2 合并排序程序略3 快速排序程序略实验总结及思考合并排序的递归程序执行的过程实验二:回溯算法实验目的:熟练掌握回溯算法实验内容:回溯算法的几种形式a) 用回溯算法搜索子集树的一般模式void search(int m)if(mn) /递归结束条件 output(); /相应的处理(输出结果)elseam=0; /设置状态:0表示不要该物品search(m+1); /递归搜索:继续确定下一个物品am=1; /设置状态:1表示要该物品search(m+1); /递归搜索:继续确定下一个物品b) 用回溯算法搜
4、索子集树的一般模式void search(int m)if(mn) /递归结束条件 output(); /相应的处理(输出结果)elsefor(i=m;i=n;i+)swap(m,i); /交换am和aiif()if(canplace(m) /如果m处可放置search(m+1); /搜索下一层swpa(m,i); /交换am和ai(换回来)习题1 0-1背包问题在0 / 1背包问题中,需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品,每件物品i 的重量为wi ,价值为pi 。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。 程序如下:
5、#include void readdata();void search(int);void checkmax();void printresult();int c=35, n=10; /c: 背包容量;n:物品数int w10, v10; /wi、vi:第i件物品的重量和价值int a10, max; /a数组存放当前解各物品选取情况;max:记录最大价值 /ai=0表示不选第i件物品,ai=1表示选第i件物品int main()readdata(); /读入数据search(0); /递归搜索printresult();void search(int m)if(m=n)checkmax()
6、; /检查当前解是否是可行解,若是则把它的价值与max比较elseam=0; /不选第m件物品search(m+1); /递归搜索下一件物品am=1; /不选第m件物品search(m+1); /递归搜索下一件物品void checkmax()int i, weight=0, value=0;for(i=0;in;i+)if(ai=1) /如果选取了该物品weight = weight + wi; /累加重量value = value + vi; /累加价值if(weightmax) /且价值大于maxmax=value; /替换maxvoid readdata()int i;for(i=0;
7、in;i+)scanf(%d%d,&wi,&vi); /读入第i件物品重量和价值void printresult()printf(%d,max);2 装载问题有两艘船,载重量分别是c1、 c2,n个集装箱,重量是wi (i=1n),且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。提示:求出不超过c1的最大值max,若总重量max =n*n)checkmax(); /检查当前解是否是可行解,若是则把它的价值与max比较elsesearch(m+1); /该位置不放堡垒递归搜索下一个位置if(canplace(m) /判断第m个格子是否能放堡垒place(m); /
8、在第m个格子上放置一个堡垒search(m+1); /递归搜索下一个位置takeout(m); /去掉第m个格子上放置的堡垒4 翻硬币问题把硬币摆放成329的矩阵,你可以随意翻转矩阵中的某些行和某些列,问正面朝上的硬币最多有多少枚?提示:(1)任意一行或一列,翻两次等于没有翻; (2)对于9列的任何一种翻转的情况,每一行翻与不翻相互独立。5 8皇后问题在一个的棋盘里放置个皇后,要求这8个皇后两两之间互相都不“冲突”。#include #include void search(int);void printresult(); /打印结果int canplace(int,int); /判断该位置能
9、否放置皇后void place(int,int); /在该位置能否放置皇后void takeout(int,int); /把该位置放置皇后去掉int a8; /ai存放第i个皇后的位置int main()search(0); /递归搜索void search(int m)int i;if(m=8) /当已经找出一组解时printresult(); /输出当前结果elsefor(i=0;i8;i+) /对当前行0到7列的每一个位置if(canplace(m,i) /判断第m个格子是否能放堡垒place(m,i); /在(m,i)格子上放置一个皇后search(m+1); /递归搜索下一行take
10、out(m,i); /把(m,i)格子上的皇后去掉int canplace(int row, int col)int i;for(i=0;irow;i+)if(abs(i-row)=abs(ai-col)|ai=col)return(0);return(1);void place(int row, int col)arow=col;void takeout(int row, int col)arow=-1;void printresult()int i,j;for(i=0;i8;i+)for(j=0;j8;j+)if(ai=j)printf( A );elseprintf( . );print
11、f(n);printf(n);6 素数环问题把从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数。分析:用回溯算法,考察所有可能的排列。程序如下:#include #include void search(int);void init(); /初始化void printresult(); /打印结果int isprime(int); /判断该数是否是素数void swap(int,int); /交换am和aiint a21; /a数组存放素数环int main()init();search(2); /递归搜索int isprime(int num)int i,k;k=sqrt(nu
12、m);for(i=2;i=k;i+)if(num%i=0)return(0);return(1);void printresult()int i;for(i=1;i20) /当已经搜索到叶结点时if(isprime(a1+a20) /如果a1+a20也是素数printresult(); /输出当前解return;elsefor(i=m;i=20;i+) /(排列树)swap(m,i); /交换am和aiif(isprime(am-1+am) /判断am-1+am是否是素数search(m+1); /递归搜索下一个位置swap(m,i); /把am和ai换回来void swap(int m, i
13、nt i)int t;t=am;am=ai;ai=t;void init()int i;for(i=0;i21;i+)ai=i;7 迷宫问题给一个2020的迷宫、起点坐标和终点坐标,问从起点是否能到达终点。输入数据:.表示空格;X表示墙。程序如下:#include #include void search(int,int);int canplace(int,int);void readdata(); /读入数据void printresult(); /打印结果int a2020; /a数组存放迷宫int s,t;int main()int row, col;readdata();row=s/2
14、0;col=s%20;search(row,col); /递归搜索printresult();void search(int row, int col)int r,c;arowcol=1;r=row; /左c=col-1;if(canplace(r,c) /判断(r,c)位置是否已经走过search(r,c); /递归搜索(r,c)r=row+1; /下c=col;if(canplace(r,c) /判断(r,c)位置是否已经走过search(r,c); /递归搜索(r,c)r=row; /右c=col+1;if(canplace(r,c) /判断(r,c)位置是否已经走过search(r,c
15、); /递归搜索(r,c)r=row-1; /上c=col;if(canplace(r,c) /判断(r,c)位置是否已经走过search(r,c); /递归搜索(r,c)void printresult()int i,j;for(i=0;i20;i+)for(j=0;j20;j+)printf(%3d,aij);printf(n);void readdata()int i,j;for(i=0;i20;i+)for(j=0;j=0&row=0&col20&arowcol=0)return 1;elsereturn 0;8 农场灌溉问题(ZOJ2412)一农场由图所示的十一种小方块组成,蓝色线条
16、为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。给出若干由字母表示的最大不超过5050具体由(m,n)表示的农场图,编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。Sample Input2 2DKHF3 3ADCFJKIHE-1 -1Sample Output23 提示:参考迷宫问题,实现时关键要解决好各块的表示问题。9 求图像的周长(ZOJ1047)给一个用 . 和X表示的图形,图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的,并且图像中间不会出现空洞,求这个图形的边长。输入:首先给出m、n、x、y四个正整数,下面给出mn的图形,x、y表示
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 分析 实验 指导
链接地址:https://www.31doc.com/p-2533649.html