數(shù)字三角問題

1、算法設(shè)計與分析上 機 實 驗 報 告專 業(yè)軟件工程班 級軟件1101學 號04113033學生姓名岳彥利完成日期2013-11-71. 上機題目及實驗環(huán)境1.1上機題目：數(shù)字三角形問題1.2實驗環(huán)境：CPU：英特爾 第二代酷睿i3-2330M 2.2GHz 雙核內(nèi)存：4G操作系統(tǒng)：windows 7軟件平臺：ubuntu2. 算法設(shè)計與分析小1）根據(jù)題意找出最優(yōu)解的性質(zhì)，并刻畫出其結(jié)構(gòu)特性。 2）.以自底向上的方式計算出最優(yōu)值。 3）.根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。 4）.從倒數(shù)第二an-20 開始，將自己與下一行同列的數(shù)組相加在和自己與下一行下一列的數(shù)相加的結(jié)果比較，將大的存放在自

2、己中。 5）.找到最大和之后，又從上往下找到組成這條最大和的路徑。3. 核心代碼 void maxsum(int (*a)max_num+10,int n)int i,j,max,t;int bn;FILE *fp1;for(i=n-1;i>=1;i-)/從倒數(shù)第二層向上求最大和for(j=1;j<=i;j+)if(aij+ai+1j)<(aij+ai+1j+1)aij=(aij+ai+1j+1);elseaij=(aij+ai+1j);if(a21<a22)/由最大和找第二層的路徑t=2;max=a22;b1=a11-a22;elset=1;max=a21;b1=a1

3、1-a21;for(i=3;i<=n;i+)從第三層開始找最大和的路徑知道第n層if(ait<ait+1)t=t+1;bi-1=max-ait;max=ait;elsebi-1=max-ait;max=ait;bn=ait;printf("路徑：n");for(i=1;i<=n;i+)printf("%d ",bi);fp1=fopen("output.txt","wt"); if(fp1=NULL) printf("cannot open!"); exit(0); fprin

4、tf(fp1,"%d",a11);printf("noutput.txt:n");fp1=fopen("output.txt","r"); if(fp1=NULL) printf("cannot open!"); exit(0); / for(i=0;!feof(fp1);i+)/printf("");fscanf(fp1,"%d",&a11);printf("%dn",a11);4. 運行與調(diào)試 圖一.寫程序時遇到的問題 （路

5、徑出錯） 圖二.修改后的正確結(jié)果 圖三. 另一組數(shù)組測試 5. 結(jié)果分析和小結(jié)如圖一，在寫路徑時最后一個數(shù)輸出結(jié)果過錯誤，經(jīng)過調(diào)試 ，發(fā)現(xiàn)路徑循環(huán)是到倒數(shù)第二行為止的，經(jīng)過修改輸出正確結(jié)果如圖二。如圖二，第一行的數(shù)代表行數(shù)，從第二行開始想最后一行找一條和最大的路徑，如圖二。如圖三， 另一組測試結(jié)果。（2）本次上機實驗的收獲、心得體會。這次的上機實驗，使我對動態(tài)規(guī)劃法有了更進一步的認識，編程的時候也有了更多的思路， 在編程之前一定把思路清晰，這樣寫的時候就比較輕松了。解決問題的時候，可以將帶求解的問題分為若干子問題求解，保存子問題的結(jié)果，遇到下一個相同的子問題直接調(diào)用就可以了?？梢源蟠蠊?jié)省時間，

6、從而更好的計算出結(jié)果，對找路徑也有了另一種視野。附錄（C/C+源代碼）#include<stdio.h>#include<stdlib.h>#include<math.h>#include<time.h>#define max_num 100int amax_num+10max_num+10;void maxsum(int (*a)max_num+10,int n)int i,j,max,t;int bn;FILE *fp1;for(i=n-1;i>=1;i-)/從倒數(shù)第二層向上求最大和for(j=1;j<=i;j+)if(aij+a

7、i+1j)<(aij+ai+1j+1)aij=(aij+ai+1j+1);elseaij=(aij+ai+1j);if(a21<a22)/由最大和找第二層的路徑t=2;max=a22;b1=a11-a22;elset=1;max=a21;b1=a11-a21;for(i=3;i<=n;i+)從第三層開始找最大和的路徑知道第n層if(ait<ait+1)t=t+1;bi-1=max-ait;max=ait;elsebi-1=max-ait;max=ait;bn=ait;printf("路徑：n");for(i=1;i<=n;i+)printf(&

8、quot;%d ",bi);fp1=fopen("output.txt","wt"); if(fp1=NULL) printf("cannot open!"); exit(0); fprintf(fp1,"%d",a11);printf("noutput.txt:n");fp1=fopen("output.txt","r"); if(fp1=NULL) printf("cannot open!"); exit(0); / fo

9、r(i=0;!feof(fp1);i+)/printf("");fscanf(fp1,"%d",&a11);printf("%dn",a11);main()int i,j;int n;FILE *fp;printf("input.txt:n");fp=fopen("input.txt","r");if(fp=NULL)printf("cannot open!");exit(0);fscanf(fp,"%d",&n);printf("%dn",n);for(i=1;i<=n;i+)/輸出成到三角形式for(j=1;j<=i;j+) f