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

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-)/從倒數第二層向上求最大和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. 運行與調試 圖一.寫程序時遇到的問題 （路

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

6、從而更好的計算出結果，對找路徑也有了另一種視野。附錄（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-)/從倒數第二層向上求最大和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