《算法分析与设计》实验指导书.doc

编 著 说 明 本书是为配合算法分析与设计实验教学大纲而编写的上机指导，其目的是使学生消化理论知识，加深对讲授内容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。本书共分810个实验，其具体要求和步骤如下：目 录实验一、C/C+环境及递归算法实验二、递归与分治策略20实验三、动态规划算法（一）24实验四、动态规划算法（二）27实验五、贪心算法（一）30实验六、贪心算法（二）32实验七、回溯法（一）35实验八、回溯算法（二）37实验九、分支限界法39实验十：随机化算法（选学）44实验二、递归与分治策略一、实验目的与要求1、进一步熟悉C/C+语言的集成开发环境；2、通过本实验加深对递归与分治策略的理解和运用；二、实验内容：1、分析并掌握“棋盘覆盖问题”的递归与分治算法示例；2、分析并掌握“二分搜索问题”的递归与分治算法示例；3、练习使用递归与分治策略求解众数问题或集合划分问题；三、实验题 众数问题：给定含有N个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数，多重集合S中重数最大的元素称为多重集合S的众数，众数的重数称为多重集合S的重数，试求一个给定多重结合的重数和众数；例如：S=a,b,b,b,f,f,4,5的重数是3，众数是b 集合划分问题：N个元素的集合1，2，N可以划分为若干个非空集合的子集，例如，当N=4时，集合1，2，3，4可划分为15个不同的非空子集如下：1，2，3，4； 1，2，3，4； 1，3，2，4；1，4，2，3； 2，3 ，1，4； 2，4，1，3 ；3，4 ，1，2； 1，2 ，3，4； 1，3 ，2，4；1，4 ，3，2 ； 2，3，4，1； 1，3，4，2；1，2， 4，3； 1，2，3，4； 1，2，3，4；给定正整数N，计算出N个元素的集合1，2，N可以划分多少个非空集合的子集；四、实验步骤 1理解递归和分治策略的基本思想和算法示例；2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、递归与分治算法示例程序1、棋盘覆盖问题：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖；void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘/ 覆盖左上角子棋盘 if (dr tr + s & dc tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 boardtr + s - 1tc + s - 1 = t; / 用 t 号L型骨牌覆盖右下角chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖其余方格 / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格boardtr + s - 1tc + s = t; / 用 t 号L型骨牌覆盖左下角 / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中chessBoard(tr+s, tc+s, dr, dc, s); else boardtr + stc + s = t; / 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s); / 覆盖其余方格 2、二分搜索问题：、设：a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。、设：有n个不同的整数排好序后存放于t0:n-1中，若存在一个下标I，0in，使得ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。、用I，j做参数，且采用传递引用或指针的形式带回值。bool BinarySearch(int a,int n,int x,int& i,int& j)int left=0; int right=n-1; while(leftamid) left=mid+1;else right=mid-1; i=right; j=left; return false;int SearchTag(int a,int n,int x) int left=0; int right=n-1; while(leftamid) right=mid-1; else left=mid+1; return -1;实验三、动态规划算法（一） 一、实验目的与要求通过动态规划算法的示例程序理解动态规划算法的基本思想；运用动态规划算法解决实际问题加深对动态规划算法的理解和运用；二、实验内容：分析并掌握“最长公共子序列” 问题的动态规划算法求解方法；练习使用动态规划算法求解“游艇租用”问题；三、实验题 游艇租用问题：长江旅游俱乐部在长江上设置了N个游艇出租站1，2，3，N,游客在这些站中租用游艇，并在下游的任何一个游艇出租站归还，游艇出租站i到游艇出租站j之间的租金为r(i,j),1ijN；试求出从游艇出租站1到游艇出租站N所需的最少租金及其游艇租用和归还方案；四、实验步骤 1理解动态规划算法思想和算法示例； 2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、动态规划算法示例程序最长公共子序列问题：若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。 include stdlib.h#include string.hvoid LCSLength(char *x ,char *y,int m,int n, int *c, int *b) int i ,j; for (i = 1; i = m; i+) ci0 = 0; for (i = 1; i = n; i+) c0i = 0; for (i = 1; i = m; i+) for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i ,int j, char *x ,int *b) if (i =0 | j=0) return; if (bij= 1) LCS(i-1,j-1,x,b); printf(%c,xi); else if (bij= 2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b);实验四、动态规划算法（二）一、实验目的与要求 1、通过动态规划算法的示例程序进一步理解动态规划算法的基本思想；2、运用动态规划算法解决实际问题进一步加深对动态规划算法的理解和运用；二、实验内容：1、分析并掌握“最大字段和” 问题的动态规划算法求解方法；2、练习使用动态规划算法求解“石子合并”问题； 三、实验题 石子合并问题：在一个圆形操场的四周摆放着数量相同或不同的N堆石子，现将N堆石子有序地合并一堆，规定每次只能将相邻的2堆石子合并成新的一堆石子，并将新的一堆石子数记为该次合并的得分，试设计一个算法，计算出将N堆石子合并成一堆的最小和最大得分；四、实验步骤 1理解动态规划算法思想和算法示例； 2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、动态规划算法示例程序最大字段和问题：若给定个整数（可能有负整数）组成的序列，求该序列中形如形如，（ ）的字段和的最大值。int MaxSum(int n,int *a,int &besti,int &bestj) int sum=0; for(int i=1;i=n;i+) for(int j=i;j=n;j+) int thissum=0; for(int K=i;ksum) sum=thissum; besti=i; bestj=j; return sum;int MaxSum(int n,int *a,int &besti,int &bestj)int sum=0; for(int i=1;i=n;i+) int thissum=0; for(intj=i;jsum) sum=thissum; besti=i; bestj=j; return sum; 实验五、贪心算法（一）一、实验目的与要求：1、通过贪心算法的示例程序理解贪心算法的基本思想；2、运用贪心算法解决实际问题加深对贪心算法的理解和运用；二、实验内容：1、分析并掌握“多机调度” 问题的贪心算法求解方法；2、练习使用贪心算法求解“会场安排”问题； 三、实验题 会场安排问题：假设在足够多的会场里安排一批活动（N个活动），每个活动事先给定活动的开始时间和结束时间，试用贪心算法求出最少需要多少会场，并求出每个活动安排在第几个会场；例如:5个活动的开始时间和结束时间和会场安排如下活动i12345开始时间112252736结束时间2328358050会场安排一二一三一四、实验步骤 1理解贪心算法思想和算法示例； 2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、贪心算法示例程序多机调度问题：要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。实验提示1、把作业按加工所用的时间从大到小排序；2、如果作业数目比机器的数目少或相等，则直接把作业分配下去；3、如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业；typedef struct Job int ID;/作业号 int time;/作业所花费的时间Job;typedef struct JobNode /作业链表的节点 int ID; int time; JobNode *next;JobNode,*pJobNode;typedef struct Header /链表的表头 int s; pJobNode next;Header,pHeader;int SelectMin(Header* M,int m) int k=0; for(int i=1;im;i+) if(Mi.smk.s)k=i; return k;实验六、贪心算法（二）一、实验目的与要求：1、通过贪心算法的示例程序进一步理解贪心算法的基本思想；2、运用贪心算法解决实际问题进一步加深对贪心算法的理解和运用；二、实验内容：1、分析并掌握“单源最短路径” 问题的贪心算法求解方法；2、练习使用贪心算法求解“删数”问题或“汽车加油”问题； 三、实验题 1、删数问题：任意给定一个位正整数，去掉其中任意个数字后；剩下的数字按照原有次序排列组成的一个新的正整数，试用贪心算法求出一个删除方案使得值最小；例如：178543删除4位后得到的最小数是13 2、汽车加油问题：一辆汽车加满油后可以行驶N千米，汽车从A地开往B地，途中有K个加油站，已知AB两地距离最近一个加油站的距离以及各个加油站和之间的距离（各个加油站之间的距离不完全相等）。设计一个有效的贪心算法使沿途的加油次数最少，并指出应在哪些加油站停靠加油；提示：把两加油站的距离放在数组中，a1.n表示从起始位置开始跑，经过n个加油站，ak表示第k1个加油站到第k个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油；四、实验步骤 1理解贪心算法思想和算法示例； 2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、贪心算法示例程序单源最短路径问题： 给定一个带权有向图G=（V，E），其中每条边的权值为正实数。另外，还给定V中的一个顶点，称为源，现在计算从源到所有其它各顶点的最短路径的长度。这里的路径长度是指路上各边的权值和。设：cij表示边（i，j）的权值，若边 ，则cij为一个很大的数； disti表示当前从源到定点i的最短路径长度；void Dijkstra(int n,int v,Type dist,int prev,Type * c)bool smaxint;for(int i=1;i=n;i+)disti=cvi;si=false;if(disti=maxint) previ=0;else previ=v;distv=0;sv=true;for (int i=1; in; i+)int temp=maxint;int u=v;for (int j=1; j=n; j+)if (!sj)&( distjtemp) )u=j;temp=distj;su=true;for (int j=1; j=n; j+)if (!sj)&( cujmaxint) )Type newdist=distu+cuj;if (newdisthalf)|(t*(t-1)/2-counthalf) return; if (tn) sum+; else for (int i=0;i2;i+) p1t=i; count+=i; for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1; Backtrack(t+1); for (int j=2;j=t;j+) count-=pjt-j+1; count-=i; 实验八、回溯算法（二）一、实验目的与要求：1、通过回溯算法的示例程序进一步理解贪心算法的基本思想；2、运用回溯算法解决实际问题进一步加深对回溯算法的理解和运用；二、实验内容：1、分析并掌握“01背包” 问题的回溯算法求解方法；2、练习使用回溯法求解“整数变换”问题； 三、实验题 整数变换问题：整数i的两种变换定义为，（向下取整）；设计一个算法求给定两个整数a和b，用最少次数的和变换将整数a变换为b；例如四、实验步骤 1理解回溯算法思想和算法示例； 2上机输入和调试算法示例程序；3理解实验题的问题要求；4上机输入和调试自己所编的实验题程序； 5验证并分析实验题的实验结果；6整理出实验报告；五、回溯示例程序01背包：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得在总重量不超过背包的容量C的前提下装入背包中物品的总价值最大；实验提示templateTypep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i H(1000); T *MinOut = new T n+1; / 计算MinOut = 离开顶点i的最小耗费边的耗费 T MinSum = 0; / 离开顶点i的最小耗费边的数目 for (int i = 1; i = n; i+) T Min = NoEdge; for (int j = 1; j = n; j+) if (aj != NoEdge & (aj Min | Min = NoEdge) Min = aj;if (Min = NoEdge) return NoEdge; / 此路不通 MinOut = Min; MinSum += Min; ；/ 把E-节点初始化为树根 MinHeapNode E; E.x = new int n; for (i = 0; i n; i+) E.x = i + 1; E.s = 0; / 局部旅行路径为x 1 : 0 E.cc = 0; / 其耗费为0E.rcost = MinSum; T bestc = NoEdge; / 目前没有找到旅行路径 / 搜索排列树 while (E.s n - 1) / 不是叶子 if (E.s = n - 2) / 叶子的父节点 / 通过添加两条边来完成旅行 / 检查新的旅行路径是不是更好 if (aE.xn-2E.xn-1 != NoEdge & aE.xn-11 != NoEdge & (E.cc + aE.xn-2E.xn-1 + aE.xn-11 bestc | bestc = NoEdge) / 找到更优的旅行路径 bestc = E.cc + aE.xn-2E.xn-1 + aE.xn-11; E.cc = bestc; E.lcost = bestc; E . s + + ; H . I n s e r t ( E ) ; else delete E.x; else / 产生孩子 for (int i = E.s + 1; i n; i+) if (aE.xE.sE.x != NoEdge) / 可行的孩子, 限定了路径的耗费 T cc = E.cc + aE.xE.sE.x; T rcost = E.rcost - MinOutE.xE.s; T b =