《算法設計與分析》上機實驗報告專業軟件工程班級1101學號學生姓名完成日期2013-11-03

上機題目及實驗環境1.1上機題目：數字三角形1.2實驗環境：CPU：3.20GHz內存：3.21GB操作系統：MicrosoftWindowsXP軟件平臺：MicrosoftVisualC++2.算法設計與分析算法設計：按三角形的行劃分階段，若行數為n，則可把問題看做一個n-1個階段的決策問題。從始點出發，依順向求出第一階段、第二階段……第n-1階段中各決策點至始點的最佳路徑，最終求出始點到終點的最佳路徑。算法分析：假設用a[i，j]表示三角形第i行的第j個數字，用p[i，j]表示從最頂層到a[i,j]這個數字的最佳路徑(路徑經過的數字總和最大)的數字和，易得問題的動態轉移方程為：p[0,0]=0

p[i,j]=max{p[i-1,j]+a[i,j],p[i-1,j-1]+a[i,j]}

(1≤j≤i≤n，其中n為總行數),則max{p[n,j]}1≤j≤n為問題解。3.核心代碼3.1求三角形的最大路徑voidMaxPath(int*array,intline,intsize) { inti,j,k; for(i=2,j=2,k=1;i<=size&&j<=line;i++) //從第二行開始求三角形的每行每列到頂點的最大值 { if(k==1) //當前點為第一列 { array[i]+=array[i-j+1]; k++; continue; } if(k>1&&k<j) //其他情況 { array[i]=MaxValue(array[i]+array[i-j],array[i]+array[i-j+1]); k++; //求當前點到頂點的最大值 continue; } if(k==j) //當前點為該行最后一個數字 { array[i]+=array[i-j]; j++; k=1; continue; } }}3.2顯示最大和路徑voidPath(int*array,intline,intsize,intmax) { int*path=newint[line]; //路徑存儲 path[0]=array[1]; for(inti=size;i>=(size-line+1);i--) if(array[i]==max) //找最大值的下標 break; for(intj=line;j!=1;j--) //找上一層的對應最大值 { if(i==(j+(j-1)*(j-2)/2)) { path[j-1]=array[i]-array[i-j+1]; i=i-j+1; continue; //當前點為某行第一列時，該層路徑點的值為：其與其上層第一列值之差 } elseif(i==(j+j*(j-1)/2)) { path[j-1]=array[i]-array[i-j]; i-=j; continue; //當前點為某行末列時，該層路徑點的值為：其與其上層末列值之差 } else { if(array[i-j+1]>array[i-j]) { path[j-1]=array[i]-array[i-j+1]; i=i-j+1; continue; } else { path[j-1]=array[i]-array[i-j]; i-=j; continue; } //當前點非上情況，該層路徑點的值為：其與其上層相鄰兩列最大值之差 } } for(intk=0;k<line;k++) //顯示路徑 cout<<path[k]<<"\t"; cout<<endl;}運行與調試圖1圖25.結果分析和小結（1）對結果的分析。分析結果可以采用圖或者表的形式給出。圖3圖4圖5圖6（2）本次上機實驗的收獲、心得體會。通過本次試驗，我復習了C++語言的有關知識，對于C++語言的認識更加深刻，鞏固了以往所學的內容。同時，對于動態規劃也有了更好的理解，尤其是對最優子結構的認識更加深刻，從中學到了許多新的編程思想。知道了如何更好地設計算法，很大地提高了編程效率。這次上機我的收獲很大，學到了許多知識，可謂是收獲良多。附錄（C/C++源代碼）#include<iostream>#include<fstream>usingnamespacestd;voidPath(int*array,intline,intsize,intmax) //顯示最大和路徑{ int*path=newint[line]; //路徑存儲 path[0]=array[1]; for(inti=size;i>=(size-line+1);i--) if(array[i]==max) //找最大值的下標 break; for(intj=line;j!=1;j--) //找上一層的對應最大值 { if(i==(j+(j-1)*(j-2)/2)) { path[j-1]=array[i]-array[i-j+1]; i=i-j+1; continue; //當前點為某行第一列時，該層路徑點的值為：其與其上層第一列值之差 } elseif(i==(j+j*(j-1)/2)) { path[j-1]=array[i]-array[i-j]; i-=j; continue; //當前點為某行末列時，該層路徑點的值為：其與其上層末列值之差 } else { if(array[i-j+1]>array[i-j]) { path[j-1]=array[i]-array[i-j+1]; i=i-j+1; continue; } else { path[j-1]=array[i]-array[i-j]; i-=j; continue; } //當前點非上情況，該層路徑點的值為：其與其上層相鄰兩列最大值之差 } } for(intk=0;k<line;k++) //顯示路徑 cout<<path[k]<<"\t"; cout<<endl;}intMaxAll(int*array,intline,intsize) //求路徑最大值{ inti=size-line+1; //最后一行的第一個數字下標 intmax=0; for(i;i<=size;i++) max=(max>array[i])?max:array[i]; returnmax;}intMaxValue(inta,intb) //求兩個值的最大值{ return(a>b)?a:b;}voidMaxPath(int*array,intline,intsize) //求三角形的最大路徑{ inti,j,k; for(i=2,j=2,k=1;i<=size&&j<=line;i++) //從第二行開始求三角形的每行每列到頂點的最大值 { if(k==1) //當前點為第一列 { array[i]+=array[i-j+1]; k++; continue; } if(k>1&&k<j) //其他情況 { array[i]=MaxValue(array[i]+array[i-j],array[i]+array[i-j+1]); k++; //求當前點到頂點的最大值 continue; } if(k==j) //當前點為該行最后一個數字 { array[i]+=array[i-j]; j++; k=1; continue; } }}voidShow(int*array,intline,intsize) //顯示三角形的內容{ inti,j,k; for(i=1,j=1,k=1;i<=size&&j<=line;i++) { cout<<array[i]<<'\t'; if(k==j) { k=1; j++; cout<<endl; } else k++; }}voidReadArray(char*fileName,int*array,intsize) //讀取三角形內容{ inttemp; ifstreaminput(fileName,ios::in); input>>temp; //表示行數的數據，拋棄 for(inti=1;i<=size;i++) input>>array[i]; input.close();}intReadLen(char*fileName) //讀取行數{ intline; ifstreaminput(fileName,ios::in); input>>line; input.close(); returnline;}voidmain(){ char*inFile="C:\\Users\\admin\\Desktop\\新建文件夾\\算法\\程序\\數字三角形\\input.txt"; //input文件的絕對路徑 char*outFile="C:\\Users\\admin\\Desktop\\新建文件夾\\算法\\程序\\數字三角形\\output.txt"; //output文件的絕對路徑 intline=ReadLen(inFile); //三角形的行數 intsize=line+(line*(line-1))/2; //三角形的數字總數 int*array=newint[size]; ReadArray(inFile,array,size); cout<<"從文件中讀