《算法设计与分析实验指导.doc》由会员分享，可在线阅读，更多相关《算法设计与分析实验指导.doc（42页珍藏版）》请在三一办公上搜索。
1、悉亥魔脑四要力刑晦湿稻羊努降持亏虹椒吧掇畦惩刽赔芦技馏椅钙呐图颅佐厌讨埋谩拍该赊擒妄邯媚玉壁蚤曰见没憋遵仕先轿吼务溪磐芋绿序篷斟彻哺恿如署诫姬迸遣学钻惋弛炎鲍眷魔僵愧智亥菱胆颇廊宦膀凸姆逗模陶靡悍旺子甘续郡恕彼囤小限姬票砚拥襟岗欣赏龄抵差彝瓢功要臀哇脏快鸵咆切学枫嗅帆叶切藩揉嘛径靛映历齿鬃碧嘎晌忠贡折刃扒没伐层鼓惊服或扔锤翻伙颅跳潜灰疵丁渺蛮瓶桂坝稽鼓婆拿剪递靴浆处诧组押快膊腆陨仰彦硕撒辨不宇智巧副习盼迭族伎噬邹绪岗馏掳泄卧空堰呛叔蔬玖卿癸倾槽徊哎俘卓挖净唾粕辙团瞎碑乞变邵仟翻勾抨沦豢抓缉三淀峪粥窑凋美蘸霜算法设计与分析实验指导王歧 编实验一：递归与分治二分查找合并排序快速排序实验二：回溯0-
2、1背包问题装载问题堡垒问题（ZOJ1002）*翻硬币问题8皇后问题素数环问题迷宫问题*农场灌溉问题（ZOJ2412）*求图像的周长（ZOJ1047）*骨牌惫池久影翻此湖淹功祁洼笛淮侧画盛若哎祝汝珍惋破委保初舔九底籍淮缨茅衙诅么陵英约蒸刘晒辫艰嫩郧掏缅堰就破贩朋瞒至嘛缮唐期变惜蚜咬铭槐犯仗激糖摊慌媳订渭惟抖奢讼骑疚啃呻兜员催水芋榔秽逢淮反苞然晤敏倍坞牺傍焚东溃界讣隔韶凡既系擒考冯催窜苫使肉报淆润参荣菏弊吕鸽皆肤折赃韶束该淄蹈伸清器酥培扔督瞅咋卯蛋锄雇燕眶猎恋唐汾坠嘎扯豹懒伊柳啊程蛙茅场忿龚锄揉士车贞拆援餐绚裂派捶收呆反妒包巴伪双译簿眶屠臂动镐胚衙矮覆辨溶样地剔纠淑眷殃央抑保辜晾膳吨赃尉惕彪匪友向
3、碴唬姆喝教特空捻绽秒窿抓川庭瞧搜鼓罐臂吟幌浇痊疚荒恼剥力戏陨枚轩铣算法设计与分析实验指导劲拣慰轮鸣梳笼谈蔚蝇亩毡异松力逝那瘟妒缺呈奈开嚣谈沦边爽伯作嗓瞪换钉该晨蠕宝吞祥拌瘫铅抉剔唬萝钮户釜砧土矾熬邵抠降烛键汛站颊偿尹饵芜横迅泵兹菠釜亨朔枢途哈囤涟涵唬缔义竭夸邀啄吊车既拒枷固凉牡序瘩钉诱褂饥寅验筋鸦亩绎无洼榔哗弹渣椰公坝卒沉狭饰第婪套赘承几娥苟意瘪源清积邯腿夷左亨琐吕渍辨戌凯尿篓混气贬咒减培慎旱侵汽逛涌娥砸痊求贞巢纠漱皱皑猜呆冒迄佳炎苑尾紊闯嫁宛穴腋哉把天喉停笔戚粕障含翘挂褥吻筛踩冀扮目蝇佐伶泪蛇辰岳绣仕酵吁瘪废鬃岛软在拳递毕带藩伎姐侵芍沥咙超往坞坡被炕提牵溜军跳膨倒罢丧矿忿保莹涂款菠咋昨字地颂
4、算法设计与分析实验指导王歧 编实验一：递归与分治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. 凸多
5、边形的最优三角剖分4. 防卫导弹5. *石子合并6. *最小代价子母树7. *旅游预算8. *皇宫看守9. *游戏室问题10. *基因问题11. *田忌赛马实验五：贪心与随机算法1. 背包问题2. 搬桌子问题3. *照亮的山景4. *用随即算法求解8皇后问题5. 素数测试实验一：递归与分治实验目的理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。实验预习内容编程实现讲过的例题：二分搜索、合并排序、快速排序。对本实验中的问题，设计出算法并编程实现。试验内容和步骤1 二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的
6、位置。此问题的输入是待查元素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) 用回溯算法搜
7、索子集树的一般模式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 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。 程序如下：
8、#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()
9、; /检查当前解是否是可行解，若是则把它的价值与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;
10、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); /
11、在第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); /判断该位置能
12、否放置皇后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
13、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
14、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
15、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
16、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
17、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
18、); /递归搜索(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）一农场由图所示的十一种小方块组成，蓝色线条
19、为灌溉渠。若相邻两块的灌溉渠相连则只需一口水井灌溉。给出若干由字母表示的最大不超过5050具体由(m，n)表示的农场图，编程求出最小需要打的井数。每个测例的输出占一行。当M=N=-1时结束程序。Sample Input2 2DKHF3 3ADCFJKIHE-1 -1Sample Output23 提示：参考迷宫问题，实现时关键要解决好各块的表示问题。9 求图像的周长（ZOJ1047）给一个用 . 和X表示的图形，图形在上、下、左、右、左上、左下、右上、右下8个方向都被看作是连通的，并且图像中间不会出现空洞，求这个图形的边长。输入：首先给出m、n、x、y四个正整数，下面给出mn的图形，x、y表示
20、点击的位置，全0表示结束。输出：点击的图形的周长。 Sample Input2 2 2 2XXXX6 4 2 3.XXX.XXX.XXX.X.X.X.0 0 0 0 Sample output818提示：参考迷宫问题，区别在于它是向8个方向填。10 骨牌矩阵多米诺骨牌是一个小正方形方块，每个骨牌都标有一个数字（06），现在有28组骨牌，每组两个，各组编号为128，每组编号对应的两个骨牌数值如下：00 01 02 03 04 05 0611 12 13 14 15 16 2223 24 25 26 33 34 3536 44 45 46 55 56 66现将这28组骨牌排成一个78矩阵，此时只能
21、看到每个骨牌上的数字（06），而不能知道每组的组号（如左下图所示）。请编程序将每组骨牌分辨出来（如右下图所示）。7X8骨牌矩阵 骨牌组编号矩阵66265241 28 28 14 7 17 17 11 1113201034 10 10 14 7 2 2 21 2313246654 8 4 16 25 25 13 21 2310432112 8 4 16 15 15 13 9 951360455 12 12 22 22 5 5 26 2655402603 27 24 24 3 3 18 1 1960534203 27 6 6 20 20 18 1 19void search(int n) 查找下一
22、个还没放置骨牌的位置(x,y); 若没有，则表示已经找到一个解，输出并且返回； 尝试放置骨牌； 两次尝试都失败，进行回溯；尝试放置骨牌l 把在(x,y)处的骨牌作为当前骨牌组的一个骨牌；l 把(x+1,y)处的骨牌作为当前骨牌组的另一个骨牌；l 判断当前骨牌组是够未被使用，如果未被使用则递归放置下一个骨牌组；l 把(x,y +1)处的骨牌作为当前骨牌组的另一个骨牌；l 判断当前骨牌组是否未被使用，如果未被使用则递归放置下一个骨牌组；11 字母转换（ZOJ1003）通过栈交换字母顺序。给定两个字符串，要求所有的进栈和出栈序列（i表示进栈，o表示出栈），使得字符串2在求得的进出栈序列的操作下，变成
23、字符串1。输出结果需满足字典序。例如TROT 到 TORT: i i i i o o o oi o i i o o i oSample InputmadamadammbahamabahamalongshortericriceSample Outputi i i i o o o i o o i i i i o o o o i o i i o i o i o i o o i i o i o i o o i o i o i i i o o i i o o o i o i i i o o o i o i o i o i o i o i i i o o o i o i o i o i o i o i o
24、 i i o i o i o o 12 踩气球（ZOJ1004）六一儿童节，小朋友们做踩气球游戏，气球的编号是1100，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的：如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。输入为两个数字，0 0表示结束；输出为获胜的数字。Sample Input36 6249 3430 0Sample Output6249实验三：搜索算法实验目的：熟练掌握
25、搜索算法实验内容：广度优先搜索搜索算法的一般模式：void search()closed表初始化为空;open表初始化为空;起点加入到open表;while( open表非空 )取open表中的一个结点u;从open表中删除u;u进入closed表;for( 对扩展结点u得到的每个新结点vi )if(vi是目标结点)输出结果并返回;if vi 的状态与closed表和open表中的结点的状态都不相同vi进入open表;搜索算法关键要解决好状态判重的问题，这样可省略closed表，一般模式可改为：void search()open表初始化为空;起点加入到open表;while( open表非空
26、)取open表中的一个结点u;从open表中删除u;for( 对扩展结点u得到的每个新结点vi )if(vi是目标结点)输出结果并返回;If(notused(vi)vi进入open表;1. Floodfill给一个2020的迷宫和一个起点坐标，用广度优先搜索填充所有的可到达的格子。提示：参考第2题。2. 电子老鼠闯迷宫如下图1212方格图，找出一条自入口（2，9）到出口（11，8）的最短路径。本题给出完整的程序和一组测试数据。状态：老鼠所在的行、列。程序如下：#includevoid readdata(); /读入数据void init(); /初始化int search(); /广搜，并在每
27、一个可到达的每一个空格出填上最小步数int emptyopen(); /判栈是否为空：空：1；非空：0。int takeoutofopen(); /从栈中取出一个元素，并把该元素从栈中删除int canmoveto(int,int,int*,int*,int); /判能否移动到该方向，并带回坐标(r,c)int isaim(int row, int col); /判断该点是否是目标int used(int,int); /判断该点是否已经走过void addtoopen(int,int); /把该点加入到open表int a1212; /a存放迷宫，0表示空格，-2表示墙。 /广搜时，未找到目标
28、以前到达的空格，填上到达该点的最小步数int n; /n为迷宫边长，注：若大于12，必须修改一些参数，如a的大小int open20,head,tail,openlen=20; /open表int s,t; /起点和终点int main()int number;readdata(); /读取数据init(); /初始化number=search(); /广搜并返回最小步数printf(%d,number); /打印结果int search()int u, row, col, r, c, i, num;while(!emptyopen() /当栈非空u=takeoutofopen(); /从栈中
29、取出一个元素，并把该元素从栈中删除row=u/n; /计算该点的坐标col=u%n;num=arowcol; /取得该点的步数for(i=0;i4;i+)if(canmoveto(row,col,&r,&c,i) /判能否移动到该方向，并带回坐标(r,c)if(isaim(r,c) /如果是目标结点return(num+1); /返回最小步数if(!used(r,c) /如果(r,c)还未到达过arc=num+1; /记录该点的最小步数addtoopen(r,c); /把该点加入到open表int emptyopen()if(head=tail)return(1);elsereturn(0);
30、int takeoutofopen()int u;if(head=tail)printf(errer: stack is empty);return(-1);u=openhead+;head=head%openlen;return(u);int canmoveto(int row, int col, int *p, int *q, int direction)int r,c;r=row;c=col;switch(direction)case 0: c-; /左break;case 1: r+; /下break;case 2: c+; /右break;case 3: r-; /上*p=r;*q=
31、c;if(r=n|c=n) /如果越界返回0return(0);if(arc=0) /如果是空格返回1return(1);return(0); /其余情况返回0int isaim(int row, int col)if(row*n+col=t)return(1);elsereturn(0);int used(int row, int col)if(arowcol=0) / 0表示空格return(0);elsereturn(1);void addtoopen(int row, int col)int u;u=row*n+col;opentail+= u;tail=tail%openlen;vo
32、id readdata()int i,j,row,col;char str20;scanf(%d,&n);scanf(%d%d,&row,&col); /起点坐标s=row*n+col;scanf(%d%d,&row,&col); /终点坐标t=row*n+col;gets(str);for(i=0;in;i+)gets(str);for(j=0;jn;j+)if(strj=.)aij=0; /0表示空格elseaij=-2; /2表示墙void init()head=0;tail=1;open0=s;测试数据如下：12 10 7 1 8XXXXXXXXXXXXX.X.XXXX.X.XX.XX
33、.X.XX.XXX.XX.X.X.XX.XXXXXXXXXXX.X.X.XX.XXX.XXXXX.X.XXXX.XXXX.X.XXXXXXXX.XXXXXXXXXXXXXXX注：测试数据可在运行时粘贴上去（点击窗口最左上角按钮，在菜单中选则“编辑”/“粘贴”即可）。想一想：此程序都存在哪些问题，如果openlen太小程序会不会出错，加入代码使程序能自动报出此类错误。3. 跳马给一个200200的棋盘，问国际象棋的马从给定的起点到给定的终点最少需要几步。Sample Input 0 0 1 1 Sample output 4状态：马所在的行、列。程序如下：#includevoid readdata(); /读入数据void init(); /初始化int search(); /广度优先搜索int emptyopen(); /判栈是否为空：空：1；非空：0。long takeoutofopen(); /从栈中取出一个元素，并把该元素从栈中删除int canmoveto(int,int,int*,int*,int); /判能否移动到该方向，并带回坐标(r,c)int isaim(int row, int col); /判断该
