算法設(shè)計與分析實驗報告

算法設(shè)計與分析報告學(xué)生姓名學(xué)號專業(yè)班級指導(dǎo)教師完成時間、課程內(nèi)容二、算法分析1、分治法(1)分治法核心思想(2)MaxMin算法分析2、動態(tài)規(guī)劃(1)動態(tài)規(guī)劃核心思想(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、最優(yōu)裝載.1.7.5、N皇后問題（非遞歸）176、N皇后問題（遞歸）18四、心得體會18五、算法對應(yīng)的例子代碼.19.1、求最大值最小值192、矩陣連乘問題213、背包問題24.4、裝載問題285、N皇后問題（非遞歸）316、N皇后問題（遞歸）344、課程內(nèi)容1、 分治法，求最大值最小值，maxmin算法；2、 動態(tài)規(guī)劃，矩陣連乘，求最少連乘次數(shù)；3、 貪心法，1）背包問題，2）裝載問題；4、 回溯法，N皇后問題的循環(huán)結(jié)構(gòu)算法和遞歸結(jié)構(gòu)算法二、算法分析1、分治法（1）分治法核心思想當(dāng)要求解一個輸入規(guī)模為n,且n的取值相當(dāng)大的問題時，直接求解往往是非常困難的。如果問題可以將n個輸入分成k個不同子集合，得到k個不同的可獨立求解的子問題 ，其中1<kwn,而且子問題與原問題性質(zhì)相同 ，原問題的解可由這些子問題的解合并得出。那末，這類問題可以用分治法求解。分治法的核心技術(shù)1） 子問題的劃分技術(shù)。2）遞歸技術(shù)。反復(fù)使用分治策略將這些子問題分成更小的同類型子問題 ，直至產(chǎn)生出不用進一步細分就可求解的子問題)合并技術(shù)。MaxMin算法分析問題：在含有n個不同元素的集合中同時找出它的最大和最小元素 。分治策略設(shè)計思想：將任一實例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的時間復(fù)雜性分析用T(n)表示比較次數(shù)，則所導(dǎo)出的遞歸關(guān)系式0T(n) 1T(n/2)T(n/2) 2當(dāng)n是2的幕時，即對于某個正整數(shù)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,存在整數(shù)k,有2k-1<n<2k,T(n)<3n/2-22、動態(tài)規(guī)劃動態(tài)規(guī)劃核心思想,但是動態(tài)規(guī)劃法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題,但是經(jīng)分解得到的子問題往往不是互相獨立的 。用分治法求解時，有些子問題被重復(fù)計算了許多次。如果能夠保存已解決的子問題的答案 ，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。設(shè)計動態(tài)規(guī)劃法的步驟：1、 劃分階段(子問題)，分析最優(yōu)子結(jié)構(gòu)性質(zhì)。2、找出階段間的最優(yōu)決策的遞推關(guān)系 ，寫出動態(tài)規(guī)劃方程；3、設(shè)計自底向上計算出最優(yōu)值的步驟 。4、從最終決策的回溯子問題的決策 ，構(gòu)造一個最優(yōu)解。矩陣連乘算法分析問題：給定n個矩陣{A1,A2,…,An},其中Ai與Ai+1是可乘的，i=1,2…，n-1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少 。兩個矩陣相乘所需做的數(shù)乘次數(shù)為 l*n*m,矩陣乘法滿足結(jié)合律,故矩陣連乘有可以有許多不同的計算順序。計算順序由加括號的方式確定，加括號的方式?jīng)Q定了矩陣連乘的計算量。核心算法如下：依次計算各層的子問題集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)貪心法核心思想顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇 。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。希望通過局部最優(yōu)選擇達到全局的最優(yōu)作出貪心決策的依據(jù)稱為貪心準(zhǔn)則 (greedycriterion)。雖然貪心算法不能對所有問題都得到整體最優(yōu)解 ，但對許多問題它能產(chǎn)生整體最優(yōu)解。貪心法一般方法根據(jù)題意，選取一種量度標(biāo)準(zhǔn)。按這種量度標(biāo)準(zhǔn)對這n個輸入排序，依次選擇輸入量加入部分解中 。如果當(dāng)前這個輸入量的加入，不滿足約束條件，則不把此輸入加到這部分解中。(2)背包問題算法分析問題：已知有n種物品和一個可容納M重量的背包，每種物品i的重量為wi。假定將物品i的一部分xi放入背包就會得到 pixi的效益，這里，0<xi<1,pi>0。如果這些物品重量的和大于M,要求所有選中要裝入背包的物品總重量不得超過 M,而裝入背包物品獲得的總效益最大。即maxpixi, WjXj M1in iin滿足約束條件的任一集合(x1，…，xn)是一個可行解(即能裝下)，使目標(biāo)函數(shù)取最大值的可行解是最優(yōu)解。核心算法如下用利潤/重量為量度即每一次裝入的物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的單位效益 。這就需使物品的裝人次序按 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。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下 ，將盡可能多的集裝箱裝上輪船設(shè)裝載入船的集裝箱的子集為 Smax{習(xí)|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、回溯法回溯法核心思想回溯法是一種組織得井井有條的 ，能避免不必要搜索的窮舉式搜索法 。這種方法適用于解一些組合數(shù)相當(dāng)大的問題 。回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點出發(fā)搜索解空間樹 。算法搜索至解空間樹的任意一點時 ，先判斷該結(jié)點是否滿足約束。如果不滿足，則跳過對該結(jié)點為根的子樹的搜索 ，逐層向其祖先結(jié)點回溯；否則，進入該子樹，繼續(xù)按深度優(yōu)先策略搜索。回溯法的一般步驟：針對所給問題，定義問題的解空間；確定易于搜索的解空間結(jié)構(gòu)；3以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索 。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是當(dāng)前行;X(k)是當(dāng)前列//Whilek>0do //對所有的行執(zhí)行以下語句//{X(k)—X(k)+1 //移到下一列//WhileX(k)wnandnotPLACE(k)doX(k)—X(k)十IifX(k)wn //找到一個位置//thenifk=n//是一個完整的解嗎//thenprint(X) //是，打印這個數(shù)組//else {k—k+1;X(k)—0;}elsek—k—1//回溯//}endNQUEENS測試X(K)是否合理procedurePLACE(k)//如果一個皇后能放在第 k行和X(k)列，則返回true;否則返回false。X是一個全程數(shù)組，進入此過程時已置了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皇后問題遞歸算法分析使用遞歸算法使，反復(fù)的調(diào)用判斷函數(shù)，判斷后在決定位置核心算法如下publicvoidsetposition(intn)//npublicvoidsetposition(intn)//n表示在第n行，table[n]表示列數(shù){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）//如果沒有皇后在同一列或斜線上（因為是按行依次放置故不可能在同一行上，又因為是每一行是從左到右放置故不可能出現(xiàn)右斜線上有皇后 ）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//一個棋盤未放滿時繼續(xù)放置setposition(n+1);}}}三、例子說明經(jīng)上機操作，各個經(jīng)典問題的算法實現(xiàn)實現(xiàn)如下 ：1、MaxMin問題比較10個數(shù)字的大小，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,三個物品的質(zhì)量分別是 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、最優(yōu)裝載船的稱重量為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排序潔的數(shù)皓為：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四、心得體會學(xué)習(xí)了欒老師的算法課，解決很多冋題，老師說程序=算法+數(shù)據(jù)結(jié)構(gòu)，首先老師教的知識對于邏輯思維能力有很大幫助，它可以培養(yǎng)我們思考分析問題能力所謂算法簡單來說，就是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令,，之前學(xué)習(xí)，學(xué)習(xí)了算法的時間空間復(fù)雜度分析，之后講的就是分治法，任何一個可用計算機求解的問題所需要的計算時間都與其規(guī)模有關(guān) ?問題的規(guī)模越小，越容易直接求解，解題所需要的時間也越少，分治法的設(shè)計思想就是將一個難以解決的大問題分割成為規(guī)模小的問題，分別解決.之后有動態(tài)規(guī)劃問題各種問題，算法是一門基礎(chǔ)學(xué)科應(yīng)該學(xué)好?對于自己在以后的學(xué)習(xí)會有很大的幫助?五、算法對應(yīng)的例子代碼1、求最大值最小值/*使用分治法求最大值最小值 T(n)=3n/2-2*/publicclassMaxMin{staticintcount=0;publicstaticvoidmain(Stringargs[]){//實例化對象MaxMinmaxmin=newMaxMin();//創(chuàng)建數(shù)組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的三重循環(huán)，時間復(fù)雜度為0（n立方）*/publicclassMatrixChainOrder{int[]p;//矩陣維數(shù)int[][]m;//最少乘次數(shù)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;//重復(fù)計算子問題，長度由1,到lengthintt=Integer. MAX_VALUE;//定義當(dāng)前最大值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實現(xiàn)*/publicclassKnapsack{privatefloatm;//背包容量float[]v;//三個物品的價值float[]w;//三個物品的質(zhì)量float[]x;//往背包裝東西的比例intn;//物品個數(shù)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打印輸岀數(shù)組intlen=a.length;for(inti=0;i<len;i++){System.out.print(a[i]+ "");}}publicvoidprint(Stringstr){//打印輸岀數(shù)組System,out.print(str+ "\n");}publicvoidSort(double[]a,float[]b,float[]c){//冒泡排序,實現(xiàn)排序功能intlen=a.length;//獲得數(shù)組長度doubletemp;//臨時變量，用于交換值floatw_temp;floatv_temp;for(inti=0;i<len-1;i++){ //通過循環(huán)實現(xiàn)主要算法for(intj=0;j<len-1-i;j++){if(a[j+1]>a[j]){ //如果后一下值比前一個值大 ，則交換兩個值的大小//以下幾行代碼是實現(xiàn)數(shù)值交換的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、裝載問題/*裝載問題，貪心法，時間復(fù)雜度上界函數(shù)為 O(n方)*/publicclassLoading{private floatm;//船的稱重量private floatw[];〃物品的質(zhì)量int[]x;〃物品的選擇intn;//物品個數(shù)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("排序后的數(shù)據(jù)為:");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皇后問題，非遞歸算法，時間復(fù)雜度為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))){ //如果當(dāng)前第k列皇后未岀界或者和其他皇后沖突x[k]+=1; //第k列皇后向