算法上機(jī)實(shí)驗(yàn)報告

第頁實(shí)驗(yàn)一最近點(diǎn)對問題實(shí)驗(yàn)內(nèi)容與要求已知平面上分布著點(diǎn)集P中的n個點(diǎn)p1,p2,...pn，點(diǎn)i的坐標(biāo)記為(xi,yi)，1≤i≤n。兩點(diǎn)之間的距離取其歐式距離，記為問題：找出一對距離最近的點(diǎn)。注：允許兩個點(diǎn)位于同一個位置，此時兩點(diǎn)之間的距離為0要求：用分治法實(shí)現(xiàn)最近點(diǎn)對的問題。算法設(shè)計（1）首先將所有的點(diǎn)按照x坐標(biāo)排序。排序過程需要O(nlogn)的時間，不會從整體上增加時間復(fù)雜度的數(shù)量級。（2）劃分：由于點(diǎn)已經(jīng)按x坐標(biāo)排序，所以空間上可以“想象”畫一條垂線，作為分割線，將平面上的點(diǎn)集分成左、右兩半PL和PR。如下圖所示：ddLdCdR分割線PLPR記,dL:PL中的最近點(diǎn)對距離；dR:PR中的最近點(diǎn)對距離；dC:跨越分割線的最近點(diǎn)對距離。則，最近的一對點(diǎn)或者在PL中，或者在PR中，或者一個在PL中而另一個在PR中（跨越分割線）。設(shè)點(diǎn)按它們的y坐標(biāo)排序，如果pi和某個pj的y坐標(biāo)相差大于δ，那么這樣的pi可以終止計算，繼續(xù)處理pi+1。算法描述如下：fori=1tonumPointsInStripdoforj=i+1tonumPointsInStripdoifpiandpj'sy-coordinatesdifferbymorethanδbreak;elseifdist(pi,pj)<δδ=dist(pi,pj);1.3實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)數(shù)據(jù)：（1）點(diǎn)對數(shù)目：6（2）點(diǎn)對坐標(biāo)：（1,3）（2,5）（3,12）（5,8）（6,9）（7,15）運(yùn)行結(jié)果：如圖顯示的是最近點(diǎn)對<5.00,8.00><6.00,9.00>的距離為1.411.4編程技術(shù)與方法縱觀整個過程，首先要對X坐標(biāo)排序時間為O（NlogN），這是分治之前的預(yù)處理。然后問題分成了N/2規(guī)模，然后用Q（N）的復(fù)雜度得到中間的最近點(diǎn)對，然后可以在常數(shù)時間內(nèi)得到最終的點(diǎn)對與最近值。So。。。T（N）=2T（N/2）+O（N），可以得到該算法的時間為O（NlogN）,在用分治法之前首先對Y坐標(biāo)進(jìn)行冒泡排序，將左右|d|范圍里的點(diǎn)按Y值排序，然后依次從每個點(diǎn)出發(fā)做水平線，并在其之上d的距離做水平線，這樣得到了一個2d*d的矩形，顯然，在此矩形之外的點(diǎn)無需開率啦，可以證明，矩形內(nèi)最多容下8個點(diǎn)（包括自己本身）。所以意味著在排好序的Y坐標(biāo)點(diǎn)中，只需要考慮其后的7個點(diǎn)就行了，此外已有人證明了事實(shí)上只需要考慮其后的4個點(diǎn)就行啦?？梢?，這些的時間復(fù)雜度最多Q（N）。1.5源程序及注釋#include<stdio.h>#include<stdlib.h>#include<math.h>#defineMAXLEN200intinit(float*x,float*y,int*ind){intn,i;while(1==scanf("%d",&n)){if(n>1)break;printf("ninvalid!\n");}for(i=0;i<n;i++){scanf("%f%f",x+i,y+i);ind[i]=i;}returnn;}voidpre_sort(float*x,float*y,int*ind,intn){//mustfinishinO(nlogn)buthereusingnormorlsortmethod//bubblesortinti,j;inttmp;floattmp_y,tmp_x;for(i=0;i<n;i++)for(j=n-1;j>i;j--)if(x[j-1]>x[j]){//swapxtmp_x=x[j-1];x[j-1]=x[j];x[j]=tmp_x;//swapytmp_y=y[j-1];y[j-1]=y[j];y[j]=tmp_y;//swapindnoneednow!/*tmp=ind[j-1];ind[j-1]=ind[j];ind[j]=tmp;*/}for(i=0;i<n;i++)for(j=n-1;j>i;j--)if(y[j-1]>y[j]){//swapytmp_y=y[j-1];y[j-1]=y[j];y[j]=tmp_y;//swapindtmp=ind[j-1];ind[j-1]=ind[j];ind[j]=tmp;}}floatget_pair_len(floatx1,floaty1,floatx2,floaty2){returnsqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));}voidfind_closest_pair(intst,inted,float*x,float*y,int*ind,float*closest,float*x1,float*y1,float*x2,float*y2){//keycodeif(ed-st==1){//only2point*closest=get_pair_len(x[ind[0]],y[0],x[ind[1]],y[1]);*x1=x[ind[0]];*y1=y[0];*x2=x[ind[1]];*y2=y[1];}elseif(ed-st==2){//only3pointfloatlen;*closest=get_pair_len(x[ind[0]],y[0],x[ind[1]],y[1]);*x1=x[ind[0]];*y1=y[0];*x2=x[ind[1]];*y2=y[1];len=get_pair_len(x[ind[0]],y[0],x[ind[2]],y[2]);if(len<*closest){*closest=len;*x1=x[ind[0]];*y1=y[0];*x2=x[ind[2]];*y2=y[2];}len=get_pair_len(x[ind[1]],y[1],x[ind[2]],y[2]);if(len<*closest){*closest=len;*x1=x[ind[1]];*y1=y[1];*x2=x[ind[2]];*y2=y[2];}}else{//atleast4pointsinti,cl,cr,ct;intmid;floatt_c1,t_c2;floatt_c1_x1,t_c1_y1,t_c1_x2,t_c1_y2;floatt_c2_x1,t_c2_y1,t_c2_x2,t_c2_y2;float*yl,*yr,*yct;int*indl,*indr,*indct;mid=(st+ed)/2;yl=(float*)malloc((mid-st+1)*sizeof(float));indl=(int*)malloc((mid-st+1)*sizeof(int));yr=(float*)malloc((ed-mid)*sizeof(float));indr=(int*)malloc((ed-mid)*sizeof(int));if(!yl||!yr||!indl||!indr)exit(-2);//nonenoughmmfor(i=0,cl=0,cr=0;i<=ed-st;i++){//storenewordery&indif(ind[i]<=mid){yl[cl]=y[i];indl[cl]=ind[i];cl++;}else{yr[cr]=y[i];indr[cr]=ind[i];cr++;}}//dividedfind_closest_pair(st,mid,x,yl,indl,&t_c1,&t_c1_x1,&t_c1_y1,&t_c1_x2,&t_c1_y2);find_closest_pair(mid+1,ed,x,yr,indr,&t_c2,&t_c2_x1,&t_c2_y1,&t_c2_x2,&t_c2_y2);if(t_c1<t_c2){*closest=t_c1;*x1=t_c1_x1;*y1=t_c1_y1;*x2=t_c1_x2;*y2=t_c1_y2;}else{*closest=t_c2;*x1=t_c2_x1;*y1=t_c2_y1;*x2=t_c2_x2;*y2=t_c2_y2;}//gettheclosestpairbetweenthetwopart(L&R)intv,ve;floatclosest_tmp;floatpart_line=(x[mid]+x[mid+1])/2.0;yct=(float*)malloc((ed-st+1)*sizeof(float));indct=(int*)malloc((ed-st+1)*sizeof(int));//getalltheyintherectfor(i=0,ct=0;i<=ed-st;i++)if(x[ind[i]]>part_line-*closest&&x[ind[i]]<part_line+*closest){yct[ct]=y[i];indct[ct]=ind[i];ct++;}//checkfollowedthe4pointsif(ct>1){for(i=0;i<ct-1;i++){ve=(i+4<ct-1?i+4:ct-1);v=i+1;while(v<=ve&&yct[v]-yct[i]<=*closest){closest_tmp=get_pair_len(x[indct[i]],yct[i],x[indct[v]],yct[v]);if(closest_tmp<*closest){*closest=closest_tmp;*x1=x[indct[i]];*y1=yct[i];*x2=x[indct[v]];*y2=yct[v];}v++;}}}free(yl);free(yr);free(indl);free(indr);free(yct);free(indct);}}intmain(){floatX[MAXLEN],Y[MAXLEN];intIND[MAXLEN],n;n=init(X,Y,IND);floatclosest,x1,y1,x2,y2;pre_sort(X,Y,IND,n);find_closest_pair(0,n-1,X,Y,IND,&closest,&x1,&y1,&x2,&y2);printf("theclosestvalueis:%-4.2f(%-4.2f,%-4.2f)(%-4.2f,%-4.2f)\n",closest,x1,y1,x2,y2);return0;}實(shí)驗(yàn)二大整數(shù)乘法2.1實(shí)驗(yàn)內(nèi)容與要求利用分治法設(shè)計一個計算兩個n位的大整數(shù)相乘的算法，要求計算時間低于O(n2)。大整數(shù)（biginteger）：位數(shù)很多的整數(shù)，普通的計算機(jī)不能直接處理，如：9834975972130802345791023498570345顯然，這樣的整數(shù)普通的計算機(jī)和程序語言是無法直接表示的。大整數(shù)運(yùn)算：給定兩個n位的整數(shù)I，J,加、減法：可以用O(n)的時間計算出I+J和I-J，即使I、J是大整數(shù)；乘法：若I、J超過普通計算機(jī)可以表示的數(shù)據(jù)范圍，怎么計算IxJ?如I=9834975972135791023498570345J=34324500180989723478923450232.2算法設(shè)計要求兩個位數(shù)為n的整數(shù)A和B的乘積AxB。如果用普通的乘法的話，要用n2次乘法和n-1次加法，所以時間復(fù)雜度是O(n2)。如果把A分解成A=a*10n/2+b把B分解成B=c*10n/2+d那么AxB=(a*10n/2+b)x(c*10n/2+d)=ac*10n+(ad+bc)*10n/2+bd=ac*10n+((a+b)(c+d)-ac-bd)*10n/2+bd這樣的話是3次乘法6次加法，當(dāng)然，可以遞歸計算ac,bd,(a+d)(c+d)由此可以產(chǎn)生下面遞推公式：T(n)=3T(n/2)+bn;n>1T(n)=d;n=1bd是大于0的常量。根據(jù)主定理T(n)=n1.59(1.59=log23)算法實(shí)現(xiàn)：//大整數(shù)乘法publicclassMultiplication{/***@paramargs*/publiclongmutiply(longa,longb){longn=getDigitsNum(a);//位數(shù)if(n<4)returna*b;longal=a%(int)Math.pow(10,n/2);//每個數(shù)字分成兩部分longau=a/(int)Math.pow(10,Math.ceil(n/2));longbl=b%(int)Math.pow(10,n/2);longbu=b/(int)Math.pow(10,Math.ceil(n/2));longac=mutiply(au,bu);//aclongbd=mutiply(al,bl);//bdlongabcd=mutiply(au+al,bu+bl);//(a+b)*(c+d)longr=ac*(long)Math.pow(10,2*(n/2))+(abcd-acbd)*(long)Math.pow(10,n/2)+bd;returnr;}//計算位數(shù),a與b的位數(shù)必須相等。時間復(fù)雜度是O(n)publicintgetDigitsNum(longa){inti=0;while(a>0){i++;a=a/10;}returni;}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstublonga=1683527,b=1528719;longresult=newMultiplication().mutiply(a,b);System.out.println(a*b);System.out.println(result);}}2.3實(shí)驗(yàn)結(jié)果與分析實(shí)驗(yàn)測試數(shù)據(jù)：1111111111*1111111111123456789*999888666555222程序運(yùn)行結(jié)果：（1）（2）經(jīng)計算器驗(yàn)算，計算結(jié)果均正確說明程序具有可行性。2.4編程技術(shù)與方法利用分治法進(jìn)行編程時往往計算量過大時就會溢出，此時采取數(shù)組的方式來存放數(shù)據(jù)，并且將其以字符串的形式存儲并輸出，每四位存儲在一個數(shù)組中由高到低，并且將進(jìn)位作為一個單獨(dú)的數(shù)組在下一個高位數(shù)組中進(jìn)行運(yùn)算時加進(jìn)去，其輸出數(shù)組由高位到地位組成一個新的字符串，該字符串顯示的結(jié)果就是運(yùn)算的結(jié)果了！2.5源程序及注釋#include<stdio.h>#include<string.h>voida2d(intx[],chara[]){inti,j;for(i=0;i<500;i++)x[i]=0;j=strlen(a)-1;for(i=0;j>=0;j--,i++)x[i]=a[j]-'0';}intmy_len(intx[]){inti;for(i=499;i>=0&&x[i]==0;i--);returni<0?0:i;}voidmulti(intx[],inty[]){intsum[500]={0},i,j,k,lx=my_len(x),ly=my_len(y);for(i=0;i<=lx;i++)for(j=0;j<=ly;j++)sum[i+j]+=x[i]*y[j];for(i=0;i<499;i++){sum[i+1]+=sum[i]/10;sum[i]%=10;x[i]=sum[i];}}intmain(){inti,x[500],y[500];chara[500],b[500];while(scanf("%s%s",a,b)!=EOF){a2d(x,a);a2d(y,b);multi(x,y);i=my_len(x);for(;i>=0;i--)printf("%d",x[i]);puts("");}return0;}實(shí)驗(yàn)三單源點(diǎn)3.1實(shí)驗(yàn)內(nèi)容與要求給定一個帶權(quán)有向圖G=（V,E），其中每條邊的權(quán)是非負(fù)實(shí)數(shù)，給定V中的一個定點(diǎn)，稱為源。計算從源到所有定點(diǎn)的最短路長度。這里的路的長度是指路上個邊權(quán)之和。這個問題稱之為單源點(diǎn)最短路徑。利用貪心算法設(shè)計一個程序來實(shí)現(xiàn)單源點(diǎn)最短距離的求取。3.2算法設(shè)計Dijkstra算法是解單源最短路徑的一個貪心算法其基本思想是，設(shè)置頂點(diǎn)集合S并不斷的做貪心選擇來擴(kuò)充這個集合。一個頂點(diǎn)屬于S當(dāng)且僅當(dāng)從源點(diǎn)到該頂點(diǎn)的最短路徑長度已知。初值時，S中僅含有源，設(shè)u是G中某一個頂點(diǎn)，把從源到u且中間只經(jīng)過S中的頂點(diǎn)的路徑（稱為特殊路徑）長度用數(shù)組dist記錄，Dijkstra算法每次從V-S中取出具有最短特殊路徑長度的頂點(diǎn)u，將u添加到S中，同時對數(shù)組dist做必要的修改，一旦S中包含了V中所有的頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)的最短路徑長度。3.3實(shí)驗(yàn)結(jié)果與分析測試數(shù)據(jù)：實(shí)驗(yàn)運(yùn)行結(jié)果：其中57表示這是一個有5個頂點(diǎn)7條邊組成的有向帶權(quán)圖，0到1的距離為100其余以此類推，輸入源點(diǎn)0，則其單源點(diǎn)最短路徑和距離分別為：0-1路徑為0-4-3-1距離為700-2路徑為0-2距離為30其余以此類推，經(jīng)手動驗(yàn)證，說明程序具有可行性，結(jié)果正確。3.4編程技術(shù)與方法該實(shí)驗(yàn)實(shí)現(xiàn)的主要方法是Dijkstra算法，試驗(yàn)程序中主要利用數(shù)組來存儲其有向帶權(quán)圖的鄰接矩陣，利用數(shù)組來進(jìn)行矩陣的一些運(yùn)算。為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的算法。譬如對于源頂點(diǎn)V0，首先選擇其直接相鄰的頂點(diǎn)中長度最短的頂點(diǎn)Vi，那么當(dāng)前已知可得從V0到達(dá)Vj頂點(diǎn)的最短距離dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根據(jù)這種思路：假設(shè)存在G=<V,E>，源頂點(diǎn)為V0，U={V0},dist[i]記錄V0到i的最短距離，path[i]記錄從V0到i路徑上的i前面的一個頂點(diǎn)。1.從V-U中選擇使dist[i]值最小的頂點(diǎn)i，將i加入到U中；2.更新與i直接相鄰頂點(diǎn)的dist。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})3.直到U=V，停止。3.5源程序及注釋/*Dijkstra求單源最短路徑2015.6.17*/#include<iostream>#include<stack>#include<stdlib.h>#defineM100#defineN100usingnamespacestd;typedefstructnode{intmatrix[N][M];//鄰接矩陣intn;//頂點(diǎn)數(shù)inte;//邊數(shù)}MGraph;voidDijkstraPath(MGraphg,int*dist,int*path,intv0)//v0表示源頂點(diǎn){inti,j,k;bool*visited=(bool*)malloc(sizeof(bool)*g.n);for(i=0;i<g.n;i++)//初始化{if(g.matrix[v0][i]>0&&i!=v0){dist[i]=g.matrix[v0][i];path[i]=v0;//path記錄最短路徑上從v0到i的前一個頂點(diǎn)}else{dist[i]=INT_MAX;//若i不與v0直接相鄰，則權(quán)值置為無窮大path[i]=-1;}visited[i]=false;path[v0]=v0;dist[v0]=0;}visited[v0]=true;for(i=1;i<g.n;i++)//循環(huán)擴(kuò)展n-1次{intmin=INT_MAX;intu;for(j=0;j<g.n;j++)//尋找未被擴(kuò)展的權(quán)值最小的頂點(diǎn){if(visited[j]==false&&dist[j]<min){min=dist[j];u=j;}}visited[u]=true;for(k=0;k<g.n;k++)//更新dist數(shù)組的值和路徑的值{if(visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]<dist[k]){dist[k]=min+g.matrix[u][k];path[k]=u;}}}}voidshowPath(int*path,intv,intv0)//輸出最短路徑上的各個頂點(diǎn){stack<int>s;intu=v;while(v!=v0){s.push(v);v=path[v];}s.push(v);while(!s.empty()){cout<<s.top()<<"";s.pop();}}intmain(intargc,char*argv[]){intn,e;//表示輸入的頂點(diǎn)數(shù)和邊數(shù)while(cin>>n>>e&&e!=0){inti,j;ints,t,w;//表示存在一條邊s->t,權(quán)值為wMGraphg;intv0;int*dist=(int*)malloc(sizeof(int)*n);int*path=(int*)malloc(sizeof(int)*n);for(i=0;i<N;i++)for(j=0;j<M;j++)g.matrix[i][j]=0;g.n=n;g.e=e;for(i=0;i<e;i++){cin>>s>>t>>w;g.matrix[s][t]=w;}cin>>v0;//輸入源頂點(diǎn)DijkstraPath(g,dist,path,v0);for(i=0;i<n;i++){if(i!=v0){showPath(path,i,v0);cout<<dist[i]<<endl;}}}return0;}實(shí)驗(yàn)四最優(yōu)二分檢索樹4.1實(shí)驗(yàn)內(nèi)容與要求. 實(shí)現(xiàn)最優(yōu)二分檢索樹算法，計算各C(i,j)、R(i,j)、W(i,j)的值，并推導(dǎo)樹的形態(tài)4.2算法設(shè)計最優(yōu)二分檢索樹算法描述及流程圖：在計算時，首先計算所有使得j-i=1的C[i][j]，其中C[i][i]=0，且W[i][i]=Q[i](0=<i<=n)，接著計算使得j-i=2的C[i][j]，在計算期間，記下每根樹的根結(jié)點(diǎn)Tij開始開始主函數(shù)main求出樹形態(tài)函數(shù)Root（）開始開始定義：內(nèi)部結(jié)點(diǎn)概率值數(shù)組P[N];外部結(jié)點(diǎn)概率值Q[N+1];成本C[N+1][N+1]，定義：內(nèi)部結(jié)點(diǎn)概率值數(shù)組P[N];外部結(jié)點(diǎn)概率值Q[N+1];成本C[N+1][N+1]，W[N+1][N+1];根R[N+1][N+1]（全局變量）實(shí)參m，n表示樹實(shí)參m，n表示樹Tmn輸入結(jié)點(diǎn)數(shù)目n，以及內(nèi)部結(jié)點(diǎn)概率值P[n];外部結(jié)點(diǎn)概率值Q[n+1];輸入結(jié)點(diǎn)數(shù)目n，以及內(nèi)部結(jié)點(diǎn)概率值P[n];外部結(jié)點(diǎn)概率值Q[n+1];i=0;N m=nY左右子樹為空，輸出*W[i][i]Q[i],R[i][[i]C[i][i]0左右子樹為空，輸出*W[i][i]Q[i],R[i][[i]C[i][i]0W[i][i+1]Q[i]+Q[i+1]+P[i+1]ii+1printf("%d",R[m][n]);輸出當(dāng)前結(jié)點(diǎn)Root(m,R[m][n]-1);printf("%d",R[m][n]);輸出當(dāng)前結(jié)點(diǎn)Root(m,R[m][n]-1);遞歸調(diào)用左子樹Root(R[m][n],n);遞歸調(diào)用右子樹i=i+1Ni=n W[i][i]=Q[i],R[i][[i]=C[i][i]YW[i][i]=Q[i],R[i][[i]=C[i][i]格式化輸出，調(diào)用函數(shù)Root（）輸出樹的形態(tài)格式化輸出，調(diào)用函數(shù)Root（）輸出樹的形態(tài)m=m+1m=1m=m+1m=1Yi=0j=i+mi=0j=i+mYm=n+1NW[i][j]=W[i][j-1]+P[j]+Q[j]尋找k滿足C[i][k-1]+C[k][j]取最小R[i][j]=k,C[i][j=W[i][j]+C[i][k-1]+C[k][j]W[i][j]=W[i][j-1]+P[j]+Q[j]尋找k滿足C[i][k-1]+C[k][j]取最小R[i][j]=k,C[i][j=W[i][j]+C[i][k-1]+C[k][j]i=i+1i=i+1實(shí)驗(yàn)結(jié)果與分析（1）按照如圖輸入得到的結(jié)果如下（其中最后樹形態(tài)輸出采用的是先序遍歷，且外部結(jié)點(diǎn)用*表示）：（2）按照如圖輸入得到的結(jié)果如下（其中最后樹形態(tài)輸出采用的是先序遍歷，且外部結(jié)點(diǎn)用*表示）：試驗(yàn)運(yùn)行結(jié)果均正確說明程序具有可行性時間及空間復(fù)雜度分析由于采用二維定大小數(shù)組存儲W及C，因此所需要的空間復(fù)雜度為O(N*N)；在計算時，找有m個節(jié)點(diǎn)的最優(yōu)樹的時間復(fù)雜度為O(n*n)（n表示輸入結(jié)點(diǎn)的個數(shù)，與N不一定相同）。此外，在構(gòu)造樹的形態(tài)函數(shù)Root（）中，時間復(fù)雜度為O（n*log源程序及注釋#include<stdio.h>#defineN100#defineMAX65535voidRoot(intm,intn);//求出樹的形態(tài)intR[N+1][N+1];voidmain(void){ floatP[N];//內(nèi)部結(jié)點(diǎn)概率值 floatQ[N+1];//外部結(jié)點(diǎn)概率值 floatC[N+1][N+1];//成本 floatW[N+1][N+1]; inti=0; intj=0; intm=0; intk=0; intk1=0; floatmin=0; intn;//結(jié)點(diǎn)數(shù)目 printf("請輸入內(nèi)結(jié)點(diǎn)數(shù)目（n<100）:"); scanf("%d",&n); for(i=0;i<n;i++) { printf("請輸入第%d個內(nèi)部部結(jié)點(diǎn)的概率值：",i+1);scanf("%f",&P[i]); } for(i=0;i<=n;i++) { printf("請輸入第%d個外部部結(jié)點(diǎn)的概率值：",i+1);scanf("%f",&Q[i]); }printf("\n結(jié)果顯示是：\n"); for(i=0;i<=n;i++) { for(j=0;j<=n;j++) { C[i][j]=MAX; W[i][j]=MAX; } } for(i=0;i<=n-1;i++)//置初值 { W[i][i]=Q[i]; R[i][i]=0; C[i][i]=0; W[i][i+1]=Q[i]+Q[i+1]+P[i];//含有一個結(jié)點(diǎn)的最優(yōu)樹 C[i][i+1]=W[i][i+1];//由計算規(guī)則簡化 R[i][i+1]=i+1;//選取根結(jié)點(diǎn) } W[n][n]=Q[n];//繼續(xù)賦初值 R[n][n]=0; C[n][n]=0; for(m=2;m<=n;m++)//找出m個結(jié)點(diǎn)的最優(yōu)樹 { for(i=0;i<=n-m;i++) { j=i+m; W[i][j]=W[i][j-1]+P[j-1]+Q[j]; k=i+1; min=W[i][j]+C[i][k-1]+C[k][j];//給min賦初值k1=k; k++; for(;k<=j;k++)//查找使C最小的K值，并計算C { if(min>(W[i][j]+C[i][k-1]+C[k][j]))//替換 { min=W[i][j]+C[i][k-1]+C[k][j]; k1=k; } }C[i][j]=min; R[i][j]=k1;//記錄K }