算法设计与分析实验报告

算法设计与分析报告学生姓名学号专业班级指导教师完成时间、课程内容二、算法分析1、分治法(1)分治法核心思想(2)MaxMin算法分析2、动态规划(1)动态规划核心思想(2)矩阵连乘算法分析3、贪心法(1)贪心法核心思想背包问题算法分析装载问题算法分析4、回溯法(1)回溯法核心思想N皇后问题非递归算法分析N皇后问题递归算法分析三、例子说明1、MaxMin问题目录4..5..6..7..9..9.1212.1214..5.1.5..16.2、矩阵连乘.16..1.6.3、背包问题.1.6.4、最优装载.1.7.5、N皇后问题（非递归）176、N皇后问题（递归）18四、心得体会18五、算法对应的例子代码.19.1、求最大值最小值192、矩阵连乘问题213、背包问题24.4、装载问题285、N皇后问题（非递归）316、N皇后问题（递归）344、课程内容1、 分治法，求最大值最小值，maxmin算法；2、 动态规划，矩阵连乘，求最少连乘次数；3、 贪心法，1）背包问题，2）装载问题；4、 回溯法，N皇后问题的循环结构算法和递归结构算法二、算法分析1、分治法（1）分治法核心思想当要求解一个输入规模为n,且n的取值相当大的问题时，直接求解往往是非常困难的。如果问题可以将n个输入分成k个不同子集合，得到k个不同的可独立求解的子问题 ，其中1<kwn,而且子问题与原问题性质相同 ，原问题的解可由这些子问题的解合并得出。那末，这类问题可以用分治法求解。分治法的核心技术1） 子问题的划分技术。2）递归技术。反复使用分治策略将这些子问题分成更小的同类型子问题 ，直至产生出不用进一步细分就可求解的子问题)合并技术。MaxMin算法分析问题：在含有n个不同元素的集合中同时找出它的最大和最小元素 。分治策略设计思想：将任一实例1=(n,A(1)，…，A(n))分成两个实例如果MAX1和MINI是11中的最大和最小元素，MAX2和MIN2是I2中的最大和最小元素，MAX1和MAX2中的大者就是I中的最大元素MAX,MINI和MIN2中的小者是I中的最小元素MIN。如果I只包含一个元素，则不需要作任何分割直接就可得到其解。核心算法如下：procedure MAXMIN(i,j,fmax,fmin)globaln,A[1:n]case{i=j： fmaxjfminJA[i] /*只有一个元素*/=j-1:ifA[i]<A[j]then /*两个元素*/fmaxjA[j] ;fminjA[i]elsefmaxjA[i];fminjA[j]else:midj /*分成两部分*/MAXMIN(i,mid,max1,min1)MAXMIN(mid+1,j,max2,min2)fmaxjmax(max1,max2)fminjmin(min1,min2)}MAXMIN的时间复杂性分析用T(n)表示比较次数，则所导出的递归关系式0T(n) 1T(n/2)T(n/2) 2当n是2的幕时，即对于某个正整数k，n=2k，有T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=4T(n/4)+4+=2k-1T(2)+2k-1+••…+2=2k-1+2k-2=3n/2-2对于任意n,存在整数k,有2k-1<n<2k,T(n)<3n/2-22、动态规划动态规划核心思想,但是动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题,但是经分解得到的子问题往往不是互相独立的 。用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案 ，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。设计动态规划法的步骤：1、 划分阶段(子问题)，分析最优子结构性质。2、找出阶段间的最优决策的递推关系 ，写出动态规划方程；3、设计自底向上计算出最优值的步骤 。4、从最终决策的回溯子问题的决策 ，构造一个最优解。矩阵连乘算法分析问题：给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的，i=1,2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少 。两个矩阵相乘所需做的数乘次数为 l*n*m,矩阵乘法满足结合律,故矩阵连乘有可以有许多不同的计算顺序。计算顺序由加括号的方式确定，加括号的方式决定了矩阵连乘的计算量。核心算法如下：依次计算各层的子问题集r=1,初始化

forij1tondom[i][i]J0从r=2至r=nforrj2to ndo计算所有大小为r的子问题MatrixChain(p[0:n] ,n,m[1:n][1:n],s[1:n][1:n]){ 1)forij{ 1)forij1tondo//初始化m[i][i]Jm[i][i]J0forrj2 to ndoforij1ton-r+1do{jji+r-1m[i][j]Jm[i+1][j]+p[i-1]*p[i]*p[s[i][j] Jiforkji+1toj-1do//子问题由小到大//子问题的起点//子问题的终点j] //初值考虑//记录分割点//求最好的分割k{tJm[i][k]+m[k+1][j]+p[i-1]*p[k]*p[ j];ift<m[i][j]then{m[i][j]Jts[i][j]Jk3、贪心法(1)贪心法核心思想顾名思义，贪心算法总是作出在当前看来最好的选择 。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。希望通过局部最优选择达到全局的最优作出贪心决策的依据称为贪心准则 (greedycriterion)。虽然贪心算法不能对所有问题都得到整体最优解 ，但对许多问题它能产生整体最优解。贪心法一般方法根据题意，选取一种量度标准。按这种量度标准对这n个输入排序，依次选择输入量加入部分解中 。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。(2)背包问题算法分析问题：已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi。假定将物品i的一部分xi放入背包就会得到 pixi的效益，这里，0<xi<1,pi>0。如果这些物品重量的和大于M,要求所有选中要装入背包的物品总重量不得超过 M,而装入背包物品获得的总效益最大。即maxpixi, WjXj M1in iin满足约束条件的任一集合(x1，…，xn)是一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。核心算法如下用利润/重量为量度即每一次装入的物品应使它占用的每一单位容量获得当前最大的单位效益 。这就需使物品的装人次序按 pi/wi比值的非增次序来考虑。procedureKNAPSACK(realP，W，M，X，n){〃P(1:n)和W(1:n)分别是n个物品的重量，它们已按P(i)/W(i)>P(i+1)/W(i+1)排序,x(1:n)是解向量//realcu;inti,n;Xj0//将解向量初始化为零//cujM//cu是背包剩余容量IIforij1tondo{ifW[i]>cuthenbreakX[i]j1cujcu-W[i]}ifiwnthenX[i]jcu/W[i]装载问题算法分析问题：有一批集装箱要装上一艘载重量为 M的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下 ，将尽可能多的集装箱装上轮船设装载入船的集装箱的子集为 Smax{习|i€S,1<iq}约束Ew[i]WM,1<i<n,i€S核心算法如下：采用重量最轻者先装的贪心选择策略Loading(M,n)globalW[1..n],X[1..n]//W[仁n]为非递减序XJ0II解向量清0cuJMforij1tondo{ifcu<W[i]thenbreakX[i]j1cuJcu-W[i]4、回溯法回溯法核心思想回溯法是一种组织得井井有条的 ，能避免不必要搜索的穷举式搜索法 。这种方法适用于解一些组合数相当大的问题 。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树 。算法搜索至解空间树的任意一点时 ，先判断该结点是否满足约束。如果不满足，则跳过对该结点为根的子树的搜索 ，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的一般步骤：针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；3以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索 。N皇后问题非递归算法分析问题：n皇后问题可以表示成 n-元组(x1,…,xn),其中xi是放在第i行的皇后所在的列号。于是，解空间由nn个n-元组组成。显示约束条件为 Si={1,2,••…：,n},1in。隐式约束条件之一为没有两个 xi相同(即任意两个皇后不在同一列上)。将其加入到显式条件中，于是解空间的大小由nn个元组减少到n!个元组。核心算法如下：procedureNQUEENS(n)X(1)-0;k-1〃k是当前行;X(k)是当前列//Whilek>0do //对所有的行执行以下语句//{X(k)—X(k)+1 //移到下一列//WhileX(k)wnandnotPLACE(k)doX(k)—X(k)十IifX(k)wn //找到一个位置//thenifk=n//是一个完整的解吗//thenprint(X) //是，打印这个数组//else {k—k+1;X(k)—0;}elsek—k—1//回溯//}endNQUEENS测试X(K)是否合理procedurePLACE(k)//如果一个皇后能放在第 k行和X(k)列，则返回true;否则返回false。X是一个全程数组，进入此过程时已置了k个值。//globalX(1:k)； integeri,ki—1whilei<kdo

ifX(i)=X(k)//在同一列有两个皇后IIorABS(X(i)—X(k))=ABS(i-k)//在同一一条斜角线上〃thenreturn(false)endifi—i+1repeatreturn(true) //满足约束//endPLACE（3） N皇后问题递归算法分析使用递归算法使，反复的调用判断函数，判断后在决定位置核心算法如下publicvoidsetposition(intn)//npublicvoidsetposition(intn)//n表示在第n行，table[n]表示列数{for(inti=0;i<=5;i++)//i{for(inti=0;i<=5;i++)//i表示在第i列上放置皇后x[n]=i;if(place(n)==false）//如果没有皇后在同一列或斜线上if(place(n)==false）//如果没有皇后在同一列或斜线上（因为是按行依次放置故不可能在同一行上，又因为是每一行是从左到右放置故不可能出现右斜线上有皇后 ）if(n==5) //棋盘满时输出方案{count++;System.out.println(”第”+count+"for(intj=0;j<=5;j++){System.out.print(x[j]+1+"");}System.out.println("");//print();}else//一个棋盘未放满时继续放置setposition(n+1);}}}三、例子说明经上机操作，各个经典问题的算法实现实现如下 ：1、MaxMin问题比较10个数字的大小，10,23,45,11,757,2,1236,768,1,-9比较得出最大值为1236，最小值为-9。Frdhlems@Javadoc.[^Declaration[erm[JivaApplicdtig]C:F亠■古时阪大值是：1236最小值是：-g2、矩阵连乘给定6个矩阵A(30*35),B(35*15),C(15*5),D(5*10),E(10*20)G(20*25)。I Troblens®JavadLoc DecLaration.>1^1Console般<terminited->ffla+riMChainDrder[JavaApplication]0：YProgruriFilesnn15~5：7i"532*511S75151257iQ25^5匸鴛12-5：：:；■B-一三讥飞3j■D10jj3500::■J2<，5o二，-3、背包问题给定3个背包：三个物品的价值分别为 60,120,100,三个物品的质量分别是 10,30,20,背包容量为50。得到装入物品的比例分别为 1,2/3,1，总重量为50，最大价值为240.出£FrobL^mz血J~匚耳，fteclaration:t«xnii.natcd^Knapi&ckLTavikpplLc^<ion]C:\Progrin*】£.D4.05.0e.o4,0乳a樹品一可口装入的比例：1.:物磊二可以装入的比例；!.：■物品三可以装入的比例；鬥住百r可以装入的最大价值为:曲上可以襄入的最大重量为5：*04、最优装载船的称重量为20,给定10个物品，重量分别是：1.0f,5.0f,2.0f,2.0f,4.0f,8.0f,3.0f,1.0f,6.0f，2.0fFroll^ms<5)Javadae|屬aratimj且Ccdeole2SCtferninated^L&-a.dang[J^va丸ppli亡sdiorjC:\ProgramFilesVJ给定的10个可选货物为；1.05.Q2.02.Dq.O■.03-01.D6.02.0排序洁的数皓为：1.-21.纭dQ2.j3.j4.05.C6.j=,Q资心选择対：1.01,0RO2.Q芥Q3.0£.05.G5、N皇后问题（非递归）给定4皇后问题，得到4种解。ProbleniE丁avacLoc,Declaratifit^xteirminated^-Queert[JavaAppliteation]C第二种格2 4 6133第三种林3^251§^152 63第畀申解：6、N皇后问题（递归）给定6皇后问题，得到4种解。Problems@Javadoc園Decliration旦Conso]■Cterminateil)1Qu«^nl[JaviApplicition]C:VFrogr^rn第谢解:45135第二种解：62 5丄弓第3种解；15263第弓种懈：51S42四、心得体会学习了栾老师的算法课，解决很多冋题，老师说程序=算法+数据结构，首先老师教的知识对于逻辑思维能力有很大帮助，它可以培养我们思考分析问题能力所谓算法简单来说，就是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令,，之前学习，学习了算法的时间空间复杂度分析，之后讲的就是分治法，任何一个可用计算机求解的问题所需要的计算时间都与其规模有关 •问题的规模越小，越容易直接求解，解题所需要的时间也越少，分治法的设计思想就是将一个难以解决的大问题分割成为规模小的问题，分别解决.之后有动态规划问题各种问题，算法是一门基础学科应该学好•对于自己在以后的学习会有很大的帮助•五、算法对应的例子代码1、求最大值最小值/*使用分治法求最大值最小值 T(n)=3n/2-2*/publicclassMaxMin{staticintcount=0;publicstaticvoidmain(Stringargs[]){//实例化对象MaxMinmaxmin=newMaxMin();//创建数组int[]array=newint[]{10,23,45,11,757,2,1236,768,1,-9};//取得最小值intmax=maxmin. getMax(array,0,array.length-1);intmin=maxmin.getMin(array,O,array.length也；//输出System.out.println("最大值是："+max);System.out.println("最小值是："+min);}/*求最大值*/publicstaticintgetMax(int[]array,inti,intj){intMaxi=0;intMax2=0;if(i==j){returnMaxi=Max2=array。];}elseif(i==(j-1)){Maxi=array[i];Max2=array。];returnMaxi>Max2?Maxi:Max2;}else{intmid=(i+j)/2;Maxi=getMax(array,i,mid);Max2=getMax(array,mid,j);//count++;//System.out.println(count);returnMaxi>Max2?Maxi:Max2;}}/*求最小值*/publicstaticintgetMin(int[]array,inti,intj){intMin1=0;intMin2=0;if(i==j){returnMin1=Min2=array[j];}elseif(i==(j-1)){Min1=array[i];Min2=array[j];returnMin1>Min2?Min2:Min1;}else{intmid=(i+j)/2;Min1=getMin(array,i,mid);Min2=getMin(array,mid,j);returnMin1>Min2?Min2:Min1;}}}2、矩阵连乘问题/*矩阵连乘问题，i,r,k的三重循环，时间复杂度为0（n立方）*/publicclassMatrixChainOrder{int[]p;//矩阵维数int[][]m;//最少乘次数int[][]s;//分割点intlength;publicMatrixChainOrder( int[]p,int[][]m,int[][]s){this.p=p;this」ength=p.length/2;this.m=m;this.s=s;init();clac();printM();}publicvoidinit(){ //m初始化for(inti=0;i<length;i++){m[i][i]=0;}}publicvoidclac(){for(inti=1;i<length;i++){for(intj=O;j<length-i;j++){intr=j+i;//重复计算子问题，长度由1,到lengthintt=Integer. MAX_VALUE;//定义当前最大值for(intk=j;k<r;k++){p[r*2+1];inttemp=m[j][k]+m[k+1][r]+ p『2]*p[k*2+1]*p[r*2+1];if(t>temp){t=temp;m[j][r]=temp;}}}}}publicvoidprintM(){for(inti=0;i<length;i++){for(intj=0;j<length;j++){System.out.print(m[i][j]+"\t");}System.out.println();}}publicstaticvoidmain(Stringargs[]){intp[]={30,35,35,15,15,5,5,10,10,20,20,25};intlength=6;int[][]m=newint[6][6];int[][]s=newint[6][6];newMatrixChainOrder(p,m,s);}}3、背包问题/* 利用贪心算法，对背包问题的java实现*/publicclassKnapsack{privatefloatm;//背包容量float[]v;//三个物品的价值float[]w;//三个物品的质量float[]x;//往背包装东西的比例intn;//物品个数double[]p_w_v;//每个物品的单位重量价值publicKnapsack(){this.m=50.0f; //背包容量为5060,120,100this.v=newfloat[]{60.0f,120.0f,100.0f}; //三个物品的价值分别为60,120,10010,30,20,thisw=newfloat[]{10.0f,30.0f,20.0f,}; //10,30,20,this.x=newfloat[3];II往背包装东西的比例this.n=3; II三个物品this.p_w_v=newdouble[n];II每个物品的单位重量价值II对物品的单位重量价值进行排序publicvoidsort(intn,float[]v,float[]w)throwsException{for(inti=0;i<n;i++){P_w_v[i]=v[i]Iw[i]; II单位重量价值}print(p_w_v);System.out.println("");Sort(p_w_v,w,v);print(p_w_v);}publicvoidprint(doublea[]){II打印输岀数组intlen=a.length;for(inti=0;i<len;i++){System.out.print(a[i]+ "");}}publicvoidprint(Stringstr){//打印输岀数组System,out.print(str+ "\n");}publicvoidSort(double[]a,float[]b,float[]c){//冒泡排序,实现排序功能intlen=a.length;//获得数组长度doubletemp;//临时变量，用于交换值floatw_temp;floatv_temp;for(inti=0;i<len-1;i++){ //通过循环实现主要算法for(intj=0;j<len-1-i;j++){if(a[j+1]>a[j]){ //如果后一下值比前一个值大 ，则交换两个值的大小//以下几行代码是实现数值交换的temp=a[j+1]; //从大到小排序w_temp= w[j+1];v_temp= v[j+1];a[j+1]=ajw[j+1]= w[j];v[j+1]= v[j];w[j]=w_temp;v[j]=v_temp;}}}}//贪心算法核心思想publicvoidknapsack()throwsException{sort(n,v,w);inti;for(i=0;i<n;i++){x[i]=0;}floatc=m;for(i=0;i<n;i++){if(w[i]>c){break;}x[i]=1；c-=w[i];}if(i<n){x[i]=c/w[i];}print("\n物品一可以装入的比例:"+x[0]);print("物品一可以装入的比例："+x[1]);print("物品二可以装入的比例："+x[2]);print("可以装入的最大价值为："+(x[0]*v[0]+x[1]*v[1]+x[2]*v[2]));print("可以装入的最大重量为“+(x[0]*w[0]+x[1]*w[1]+x[2]*w[2]));publicstaticvoidmain(String[]args)throwsException{Knapsackksp= newKnapsack();ksp.knapsack();}}4、装载问题/*装载问题，贪心法，时间复杂度上界函数为 O(n方)*/publicclassLoading{private floatm;//船的称重量private floatw[];〃物品的质量int[]x;〃物品的选择intn;//物品个数publicLoading(){this.m=20.0f;//船的称重量为20this.n=9;〃10个物品this.w=newfloat[]{1.0f,5.0f,2.0f,2.0f,4.0f,8.0f,3.0f,1.0f,6.0f,2.0f}; 〃10个物品的重量this.x=newint[n];System.out.println("给定的10个可选货物为:");for(inti=0;i<w.length;i++){System.out.print(w[i]+"");}System.out.println("");}//对物品按照重量进行排序publicvoidsort(){floattemp=0f;for(inti=0;i<n;i++){for(intj=O;j<n-i;j++){if(w[j]>w[j+1]){temp=w[j];w[j]=w[j+1];w[j+1]=temp;}}}System.out.println("排序后的数据为:");for(inti=0;i<w.length;i++){System.out.print(w[i]+"");}}publicvoidloading(){inti;System.out.println();System.out.println("贪心选择为：")；for(i=0;i<n;i++){x[i]=0;}for(i=0;i<n;i++){if(w[i]>m){break;}x[i]=1;m=m-w[i];if(m<0){break;}System.out.print(w[i]+"");}}publicstaticvoidmain(String[]args){Loadingload=newLoading();load.sort();load.loading();5、N皇后问题(非递归)/*回溯法N皇后问题，非递归算法，时间复杂度为O(n!)*/publicclassQueen1{staticintcount=0;staticintn=6;staticintx[]=newint[n+1];voidbacktrack。{intk=1;while(k>0){x[k]+=1; //第k列皇后向下移一行while((x[k]<=n)&&!(place(k))){ //如果当前第k列皇后未岀界或者和其他皇后冲突x[k]+=1; //第k列皇后向