數(shù)字三角問(wèn)題

1、算法設(shè)計(jì)與分析上 機(jī) 實(shí) 驗(yàn) 報(bào) 告專 業(yè)軟件工程班 級(jí)軟件1101學(xué) 號(hào)04113033學(xué)生姓名岳彥利完成日期2013-11-71. 上機(jī)題目及實(shí)驗(yàn)環(huán)境1.1上機(jī)題目：數(shù)字三角形問(wèn)題1.2實(shí)驗(yàn)環(huán)境：CPU：英特爾 第二代酷睿i3-2330M 2.2GHz 雙核內(nèi)存：4G操作系統(tǒng)：windows 7軟件平臺(tái)：ubuntu2. 算法設(shè)計(jì)與分析小1）根據(jù)題意找出最優(yōu)解的性質(zhì)，并刻畫(huà)出其結(jié)構(gòu)特性。 2）.以自底向上的方式計(jì)算出最優(yōu)值。 3）.根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。 4）.從倒數(shù)第二an-20 開(kāi)始，將自己與下一行同列的數(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+)從第三層開(kā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. 運(yùn)行與調(diào)試 圖一.寫(xiě)程序時(shí)遇到的問(wèn)題 （路

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

6、從而更好的計(jì)算出結(jié)果，對(duì)找路徑也有了另一種視野。附錄（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+)從第三層開(kā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