2021算法设计与分析实验报告

算法设计与分析实验报告算法设计与分析实验报告实验一递归与分治策略应用基础学号：*姓名：*班级：*日期：2014-2021学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。1、求n个元素的全排。（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。（30分）3、设有n=2k个运动员要进行网球循环赛。设计一个满足要求的比赛日程表。（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include iostreamusing namespace std;#define N 100void Perm(int* list, int k, int m)if (k = m)for (int i=0; icout cout return;elsefor (int i=m; iswap(listm, listi);Perm(list, k, m+1);swap(listm, listi);void swap(int a,int b)int temp;temp=a;a=b;b=temp;int main()int i,n;int aN;coutcinn;coutfor(i=0;icinai;coutPerm(a,n,0);return 0;算法设计与分析实验报告实验二递归与分治策略应用提高学号：*姓名：*班级：*日期：2014-2021学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。1、Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有一位不同。设计一个算法对任意的n构造相应的Gray码。2、马的Hamilton周游路线问题。对于给定的m*n的国际象棋棋盘，m和n均为大于5的偶数，且|m-n|3、对于给定的n个自然数组成的多重集S，计算S的众数及其重数。提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include iostreamusing namespace std;int main()int a50;int i,j,maxCount=0,index=0,nCount=0;int n;coutcoutfor(i=0;icinai;for(i=0;ifor(j=0;jif(aj=ai)nCount+;if(nCountmaxCount)maxCount=nCount;index=i;nCount=0;cout算法设计与分析实验报告实验三动态规划策略应用基础学号：姓名：班级：日期：2014-2021学年第1学期一、实验目的1、理解动态规划策略的基本思想。2、了解适用动态规划策略的问题类型，并能利用动态规划策略设计相应的算法，解决具体问题。3、掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。1、矩阵连乘问题。2、最长公共子序列问题。3、流水作业调度问题。4、最少硬币问题提交结果：程序设计的源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#includeusing namespace std;const int MAX = 100;int pMAX+1,mMAXMAX,sMAXMAX;int n;void matrixChain()for(int i=1;ifor(int r=2;rfor(int i=1;iint j = r+i-1;mij=mii+mi+1j+pi-1*pi*pj;sij=i;for(int k = i+1;kint temp=mik+mk+1j+pi-1*pk*pj;if(tempmij=temp;sij=k;void traceback(int i,int j)if(i=j)return ;traceback(i,sij);traceback(sij+1,j);coutint main()cinn;for(int i=0;imatrixChain();traceback(1,n);coutsystem(pause);return 0;算法设计与分析实验报告实验四动态规划策略应用提高学号：*姓名：*班级：*日期：2014-2021学年第1学期一、实验目的1、深入理解动态规划策略的基本思想。2、能正确采用动态规划策略设计相应的算法，解决实际问题。3、掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。1、编辑距离问题。2、石子合并问题。3、租用游艇问题。提交结果：程序设计的源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include #include using namespace std;int min(int a, int b)return a int edit(string str1, string str2)int max1 = str1.size();int max2 = str2.size();int *ptr = new int*max1 + 1;for(int i = 0; i ptri = new intmax2 + 1;for(i = 0 ;i ptri0 = i;for(i = 0 ;i ptr0i = i;for(i = 1 ;i for(int j = 1 ;jint d;int temp = min(ptri-1j + 1, ptrij-1 + 1);if(str1i-1 = str2j-1)d = 0 ;elsed = 1 ;ptrij = min(temp, ptri-1j-1 + d);cout for(i = 0 ;i for(int j = 0; jcout cout cout int dis = ptrmax1max2;for(i = 0; i delete ptri;ptri = NULL;delete ptr;ptr = NULL;return dis;int main(void)string str1 = sailn;string str2 = failing;int r = edit(str1, str2);cout return 0;算法设计与分析实验报告实验五贪心策略应用基础学号：姓名：班级：日期：2014-2021学年第1学期一、实验目的1、深入理解贪心策略的基本思想。2、能正确采用贪心策略设计相应的算法，解决实际问题。3、掌握贪心算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容最小生成树问题。三、设计分析此算法需要建立辅助数组，来存放U和V-U之间的边，数组按如图所示的方式变化：棕色虚线表示的边是数组中的边，实线表示的边是要加入到最小生成树中的边，该边即将在数组中被删除。四、算法描述及程序五、测试与分析六、实验总结与体会#include #include #define MaxInt 0x3f3f3f3f#define N 110int mapNN,lowN,visitedN;int n;int prim()int i,j,pos,min,result=0;memset(visited,0,sizeof(visited);visited1=1;pos=1;for(i=1;iif(i!=pos) lowi=mapposi;for(i=1;ilowj)min=lowj;pos=j;result+=min;visitedpos=1;for(j=1;jif(visitedj=0&lowjmapposj)lowj=mapposj;return result;int main()int i,v,j,ans;while(scanf(%d,&n)!=EOF)memset(map,MaxInt,sizeof(map);for(i=1;ifor(j=1;jscanf(%d,&v);mapij=mapij=v;ans=prim();printf(%dn,ans);return 0;算法设计与分析实验报告实验六贪心策略应用提高学号：姓名：班级：日期：2014-2021学年第1学期一、实验目的1、深入理解贪心策略的基本思想。2、能正确采用贪心策略设计相应的算法，解决实际问题。3、掌握贪心算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。1、磁带最优存储问题。2、最优服务次序问题。3、汽车加油问题。提交结果：程序设计的源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include#include #includeusing namespace std;using std:vector;double greedy(vectorvectorvectorint n=x.size();sort(x.begin(),x.end();int i=0,j=0;while(istj+=xi;suj+=stj;i+;j+;if(j=s)j=0;double t=0;for(i=0;it+=sui;t/=n;return t;void main()int n;int s;int i;int a;int t;vectorcoutcinn;coutcins;coutfor(i=1;icoutcina;x.push_back(a);t=greedy(x, s);coutcini;算法设计与分析实验报告实验七回溯策略应用基础学号：姓名：班级：日期：2014-2021学年第1学期一、实验目的1、深入理解回溯策略的基本思想。2、能正确采用回溯策略设计相应的算法，解决实际问题。3、掌握回溯算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用回溯策略设计解决方案。1.连续邮资问题。2.n后问题。3.0-1背包问题。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#includeusing namespace std;class Stampfriend int MaxStamp(int ,int ,int );private:int Bound(int i);void Backtrack(int i,int r);int n;/邮票面值数int m;/每张信封最多允许贴的邮票数int maxvalue;/当前最优值int maxint;/大整数int maxl;/邮资上界int *x;/当前解int *y;/贴出各种邮资所需最少邮票数int *bestx;/当前最优解;void Stamp:Backtrack(int i,int r)for(int j=0;jif(yjfor(int k=1;kif(yj+kyj+xi-1*k=yj+k;while(yrr+;if(in)if(r-1maxvalue)maxvalue=r-1;for(int j=1;jbestxj=xj;return;int *z=new intmaxl+1;for(int k=1;kzk=yk;for(j=xi-1+1;jxi=j;Backtrack(i+1,r);for(int k=1;kyk=zk;delete z;int MaxStamp(int n,int m,int bestx)Stamp X;int maxint=32767;int maxl=1500;X.n=n;X.m=m;X.maxvalue=0;X.maxint=maxint;X.maxl=maxl;X.bestx=bestx;X.x=new int n+1;X.y=new int maxl+1;for(int i=0;iX.xi=0;for(i=1;iX.yi=maxint;X.x1=1;X.y0=0;X.Backtrack(2,1);coutfor(i=1;icoutcoutdelete X.x;delete X.y;return X.maxvalue;void main()int *bestx;int n;int m;coutcinn;coutcinm;bestx=new intn+1;for(int i=1;ibestxi=0;cout算法设计与分析实验报告实验八回溯策略应用提高学号：姓名：班级：日期：2014-2021学年第1学期一、实验目的1、深入理解回溯策略的基本思想。2、能正确采用回溯策略设计相应的算法，解决实际问题。3、掌握回溯算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用回溯策略设计解决方案。1、最小重量机器设计问题。（课后习题5-3）2、运动员最佳配对问题。（课后习题5-4）提交结果：程序设计的源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#includeusing namespace std;#define N 50class MinWmechineint n; /部件个数int m; /供应商个数int COST; /题目中的Cint cw; /当前的重量int cc; /当前花费int bestw; /当前最小重量int bestxN;int savexN;int wNN;int cNN;public:MinWmechine();void machine_plan(int i);void prinout();MinWmechine:MinWmechine()cw=0; /当前的重量cc=0; /当前花费bestw=-1; /当前最小重量bestxN;savexN;coutcinn;coutcinm;coutcinCOST;for(int j=0;jfor(int i=0;icoutcinwij;coutcincij;if(wijcouti=i-1;void MinWmechine:machine_plan(int i)if(i=n)if(cw bestw=cw;for(int j=0;jsavexj=bestxj;return;for(int j=0; jm; j+) /依次递归尝试每个供应商if(cc+cijcc+=cij;cw+=wij;bestxi=j;machine_plan(i+1);bestxi=-1;cc-=cij;cw-=wij;void MinWmechine:prinout()int i,j,ccc=0;for(j=0;jfor(i=0;icoutfor(j=0; jbestxj=-1;machine_plan(0);coutfor(int k=0; kcoutccc+=cksavexk;coutcoutint main(void)MinWmechine Y;Y.prinout();return 0;