算法设计与分析实验报告.doc

算法设计与分析实验报告实验一 递归与分治策略应用基础学号：*姓名：*班级：*日期：2014-2015学年第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; im; i+) cout listi ; cout endl; return; else for (int i=m; ik; i+) swap(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; coutn; cout请输入数据：; for(i=0;iai; cout该数据的全排列：endl; Perm(a,n,0); return 0;算法设计与分析实验报告实验二 递归与分治策略应用提高 学号：*姓名：*班级：*日期：2014-2015学年第1学期一、实验目的 1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法 3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。1、Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的（0，1）串，相邻元素恰好只有一位不同。设计一个算法对任意的n构造相应的Gray码。2、马的Hamilton周游路线问题。对于给定的m*n的国际象棋棋盘，m和n均为大于5的偶数，且|m-n|=2，计算m*n的国际象棋 棋盘上的一条Hamilton周游路线。3、对于给定的n个自然数组成的多重集S，计算S的众数及其重数。提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include iostreamusing namespace std;int main()int a50;int i,j,maxCount=0,index=0,nCount=0;int n;cout输入要输入数字的个数：n;cout输入数字：endl;for(i=0;iai;for(i=0;in;i+) for(j=0;jmaxCount) maxCount=nCount; index=i; nCount=0; coutaindexnmaxCount;算法设计与分析实验报告实验三 动态规划策略应用基础学号：姓名： 班级：日期：2014-2015学年第1学期一、实验目的 1、理解动态规划策略的基本思想。2、了解适用动态规划策略的问题类型，并能利用动态规划策略设计相应的算法，解决具体问题。 3、掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。1、矩阵连乘问题。2、最长公共子序列问题。3、流水作业调度问题。 4、最少硬币问题 提交结果：程序设计的源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include using namespace std; const int MAX = 100;int pMAX+1,mMAXMAX,sMAXMAX;int n;void matrixChain() for(int i=1;i=n;i+)mii=0; for(int r=2;r=n;r+) for(int i=1;i=n-r+1;i+) int j = r+i-1; mij=mii+mi+1j+pi-1*pi*pj; sij=i; for(int k = i+1;kj;k+) int temp=mik+mk+1j+pi-1*pk*pj; if(tempmij) mij=temp; sij=k; void traceback(int i,int j) if(i=j)return ; traceback(i,sij); traceback(sij+1,j); coutMultiply Ai,sijand Asij+1,jn; for(int i=0;ipi; matrixChain(); traceback(1,n); coutm1nendl;system(pause); return 0;算法设计与分析实验报告实验四 动态规划策略应用提高学号：*姓名：*班级：*日期：2014-2015学年第1学期一、实验目的 1、深入理解动态规划策略的基本思想。2、能正确采用动态规划策略设计相应的算法，解决实际问题。 3、掌握动态规划算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。1、编辑距离问题。2、石子合并问题。3、租用游艇问题。提交结果：程序设计的源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include #include using namespace std;int min(int a, int b) return a b ? a : b;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 max1 + 1 ;i+) ptri = new intmax2 + 1; for(i = 0 ;i max1 + 1 ;i+) ptri0 = i; for(i = 0 ;i max2 + 1;i+) ptr0i = i; for(i = 1 ;i max1 + 1 ;i+) for(int j = 1 ;j max2 + 1; j+) int d; int temp = min(ptri-1j + 1, ptrij-1 + 1); if(str1i-1 = str2j-1) d = 0 ; else d = 1 ; ptrij = min(temp, ptri-1j-1 + d); cout * endl; for(i = 0 ;i max1 + 1 ;i+) for(int j = 0; j max2 + 1; j+) cout ptrij ; cout endl; cout * endl; int dis = ptrmax1max2; for(i = 0; i max1 + 1; 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 the dis is : r endl; return 0;算法设计与分析实验报告实验五 贪心策略应用基础学号： 姓名： 班级：日期：2014-2015学年第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;i=n;i+) if(i!=pos) lowi=mapposi; for(i=1;in;i+) min=MaxInt; for(j=1;jlowj) min=lowj;pos=j; result+=min; visitedpos=1; for(j=1;jmapposj) lowj=mapposj; return result;int main() int i,v,j,ans; while(scanf(%d,&n)!=EOF) memset(map,MaxInt,sizeof(map); for(i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&v); mapij=mapij=v; ans=prim(); printf(%dn,ans); return 0;算法设计与分析实验报告实验六 贪心策略应用提高学号：姓名： 班级：日期：2014-2015学年第1学期一、实验目的 1、深入理解贪心策略的基本思想。2、能正确采用贪心策略设计相应的算法，解决实际问题。 3、掌握贪心算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用动态规划策略设计解决方案。1、磁带最优存储问题。2、最优服务次序问题。3、汽车加油问题。提交结果：程序设计的源代码及其分析说明和测试运行报告。三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include#include #includeusing namespace std;using std:vector;double greedy(vectorx,int s)vectorst(s+1,0);vectorsu(s+1,0);int n=x.size();sort(x.begin(),x.end();int i=0,j=0;while(in)stj+=xi;suj+=stj;i+;j+;if(j=s)j=0;double t=0;for(i=0;is;i+)t+=sui;t/=n;return t;void main()int n; int s; int i;int a;int t;vectorx;coutn;couts;cout请输入服务顾客所需时间:endl;for(i=1;i=n;i+)coutNo.ia;x.push_back(a);t=greedy(x, s);cout平均最短服务时间:ti;算法设计与分析实验报告实验七 回溯策略应用基础学号：姓名： 班级：日期：2014-2015学年第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;j=xi-2*(m-1);j+)if(yjm)for(int k=1;k=m-yj;k+)if(yj+kyj+xi-1*k)yj+xi-1*k=yj+k;while(yrn)if(r-1maxvalue)maxvalue=r-1;for(int j=1;j=n;j+)bestxj=xj;return;int *z=new intmaxl+1;for(int k=1;k=maxl;k+)zk=yk;for(j=xi-1+1;j=r;j+)xi=j;Backtrack(i+1,r);for(int k=1;k=maxl;k+)yk=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;i=n;i+)X.xi=0;for(i=1;i=maxl;i+)X.yi=maxint;X.x1=1;X.y0=0;X.Backtrack(2,1);cout当前最优解:;for(i=1;i=n;i+)coutbestxi ;coutendl;delete X.x;delete X.y;return X.maxvalue;void main()int *bestx;int n;int m;coutn;coutm;bestx=new intn+1;for(int i=1;i=n;i+)bestxi=0;cout最大邮资:MaxStamp(n,m,bestx)endl;算法设计与分析实验报告实验八 回溯策略应用提高学号：姓名： 班级：日期：2014-2015学年第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:MinWmechi