1、算法設(shè)計(jì)與分析課程設(shè)計(jì)題目： 最大子長(zhǎng)方體問題 專業(yè)： 網(wǎng)絡(luò)工程 班級(jí)： 學(xué)號(hào)： 姓名： 計(jì)算機(jī)工程系 2012年 11 月 16 日一、算法問題描述一個(gè)立方體被分割成n個(gè)小立方體，每個(gè)小立方體內(nèi)有一個(gè)整數(shù)。試設(shè)計(jì)一個(gè)算法，計(jì)算出所給立方體的最大子長(zhǎng)方體。子長(zhǎng)方體的大小由它所含所有整數(shù)之和確定。二、算法問題形式化表示三、期望輸入與輸出輸入：輸入的第1行是3個(gè)正整數(shù)m,n,p，1m,n,p50。接下來m*n行每行p個(gè)正整數(shù)，表示小立方體中的數(shù)。 輸出：輸出的第1行中的數(shù)是計(jì)算出的最大子長(zhǎng)方體的大小。樣例輸入：請(qǐng)輸入立方體的長(zhǎng)m,寬n,高p為：3 3 3m*n行中每行的p個(gè)正整數(shù)為：0 -1 21

2、 2 21 1 -2-2 -1 -1-3 3 -2-2 -3 1-2 3 30 1 32 1 -3樣例輸出：所給立方體的最大子長(zhǎng)方體為：14四、算法分析與步驟描述 1算法總體過程 2最優(yōu)值實(shí)現(xiàn)過程中信息的保存 在算法的實(shí)現(xiàn)過程中，是將原長(zhǎng)方體分解成若干子長(zhǎng)方體，每個(gè)子長(zhǎng)方體都要轉(zhuǎn)化成矩陣，求出各個(gè)矩陣的最大子矩陣，最優(yōu)值就存在于這些最大子矩陣中，如果想獲得最優(yōu)解就必須對(duì)各個(gè)最大子矩陣的信息進(jìn)行保存；同理，將子長(zhǎng)方體轉(zhuǎn)化成矩陣，分解成若干子矩陣，每個(gè)子矩陣都要轉(zhuǎn)化成段，求出各個(gè)段的最大子段，要獲得最大子矩陣，就得從這些最大子段中比較求得，如果想獲得最優(yōu)解就必須對(duì)各個(gè)最大子段和的信息進(jìn)行保存，為此

3、，定義了下面的方法： static int max(int i,int j)if(i=j)return i;else return j; 3.算法的實(shí)現(xiàn) 最大子長(zhǎng)方體問題的動(dòng)態(tài)規(guī)劃算法如下： static int MaxSum3(int a,int m,int n,int p)int sum=0;int b=new int 5050;int k,i,j,z,x;for(i=0;ip;i+)for(z=0;zm;z+)for(x=0;xn;x+)bzx=0;/初使化for( j=i;jp;j+)for(z=0;zm;z+)for(x=0;xn;x+)bzx+=azxj;sum=max(sum,M

4、axSum2(b,m,n);return sum; 其中MaxSum2()為最大子矩陣問題的動(dòng)態(tài)規(guī)劃算法，具體實(shí)現(xiàn)過程如下： static int MaxSum2(int a,int m,int n) /二維M*N的矩陣int sum=0;int b=new int50;int k=0;for(int i=0;im;i+)for(k=0;kn;k+)bk=0;for(int j=i;jm;j+)for(k=0;kn;k+)bk+=ajk;sum=max(sum,MaxSum(b,n);return sum;五、問題實(shí)例及算法運(yùn)算步驟 設(shè)當(dāng)前子長(zhǎng)方體是最優(yōu)子長(zhǎng)方體，用num進(jìn)行標(biāo)志，其在i、j和

5、k方向上的起止位置分別為：(i1,i2)、(j1,j2)、(k1,k2)。k1、k2在算法MaxSum3中很容易確定，并已保存在three1,three2變量中；i1、i2要在MaxSum2中確定，它們的值保存在memtwonum.one1和memtwonum.one2中，由num1用來標(biāo)志獲得最優(yōu)子長(zhǎng)方體的最優(yōu)子矩陣；j1、j2的值要在MaxSum1中確定，保存在memonenum1.two1和memonenum1.two2中，并在MaxSum2中賦值memtwonum.two1 =memonenum1.two1,memtwonum.two2=memonenum1.two2。若在MaxSum

6、3中判斷出當(dāng)前子長(zhǎng)方體是當(dāng)前的最優(yōu)解，則進(jìn)行賦值num3=num,num3最終保存的就是最優(yōu)子長(zhǎng)方體的標(biāo)志。最優(yōu)值確定后，進(jìn)行賦值two1= memtwonum3.two1,two2=memtwonum3.two2,one1= memtwonum3.one1,one2= memtwonum3.one2,并通過如下算法，輸出最大子長(zhǎng)方體： for(int i=0;im;i+)for(int j=0;jn;j+)for(int k=0;kp;k+)aijk=Integer.parseInt(sc.next();System.out.println(所給立方體的最大子長(zhǎng)方體為：);System.out.println(MaxSum3(a,m,n,p);六、算法運(yùn)行截圖七、算法復(fù)