大學(xué)學(xué)算法設(shè)計(jì)數(shù)字三角形問(wèn)題實(shí)驗(yàn)報(bào)告

《算法設(shè)計(jì)與分析》上機(jī)實(shí)驗(yàn)報(bào)告專業(yè)軟件工程班級(jí)1101學(xué)號(hào)學(xué)生姓名完成日期2013-11-03

上機(jī)題目及實(shí)驗(yàn)環(huán)境1.1上機(jī)題目：數(shù)字三角形1.2實(shí)驗(yàn)環(huán)境：CPU：3.20GHz內(nèi)存：3.21GB操作系統(tǒng)：MicrosoftWindowsXP軟件平臺(tái)：MicrosoftVisualC++2.算法設(shè)計(jì)與分析算法設(shè)計(jì)：按三角形的行劃分階段，若行數(shù)為n，則可把問(wèn)題看做一個(gè)n-1個(gè)階段的決策問(wèn)題。從始點(diǎn)出發(fā)，依順向求出第一階段、第二階段……第n-1階段中各決策點(diǎn)至始點(diǎn)的最佳路徑，最終求出始點(diǎn)到終點(diǎn)的最佳路徑。算法分析：假設(shè)用a[i，j]表示三角形第i行的第j個(gè)數(shù)字，用p[i，j]表示從最頂層到a[i,j]這個(gè)數(shù)字的最佳路徑(路徑經(jīng)過(guò)的數(shù)字總和最大)的數(shù)字和，易得問(wèn)題的動(dòng)態(tài)轉(zhuǎn)移方程為：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為總行數(shù)),則max{p[n,j]}1≤j≤n為問(wèn)題解。3.核心代碼3.1求三角形的最大路徑voidMaxPath(int*array,intline,intsize) { inti,j,k; for(i=2,j=2,k=1;i<=size&&j<=line;i++) //從第二行開(kāi)始求三角形的每行每列到頂點(diǎn)的最大值 { if(k==1) //當(dāng)前點(diǎn)為第一列 { 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++; //求當(dāng)前點(diǎn)到頂點(diǎn)的最大值 continue; } if(k==j) //當(dāng)前點(diǎn)為該行最后一個(gè)數(shù)字 { array[i]+=array[i-j]; j++; k=1; continue; } }}3.2顯示最大和路徑voidPath(int*array,intline,intsize,intmax) { int*path=newint[line]; //路徑存儲(chǔ) path[0]=array[1]; for(inti=size;i>=(size-line+1);i--) if(array[i]==max) //找最大值的下標(biāo) break; for(intj=line;j!=1;j--) //找上一層的對(duì)應(yīng)最大值 { if(i==(j+(j-1)*(j-2)/2)) { path[j-1]=array[i]-array[i-j+1]; i=i-j+1; continue; //當(dāng)前點(diǎn)為某行第一列時(shí)，該層路徑點(diǎn)的值為：其與其上層第一列值之差 } elseif(i==(j+j*(j-1)/2)) { path[j-1]=array[i]-array[i-j]; i-=j; continue; //當(dāng)前點(diǎn)為某行末列時(shí)，該層路徑點(diǎn)的值為：其與其上層末列值之差 } 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; } //當(dāng)前點(diǎn)非上情況，該層路徑點(diǎn)的值為：其與其上層相鄰兩列最大值之差 } } for(intk=0;k<line;k++) //顯示路徑 cout<<path[k]<<"\t"; cout<<endl;}運(yùn)行與調(diào)試圖1圖25.結(jié)果分析和小結(jié)（1）對(duì)結(jié)果的分析。分析結(jié)果可以采用圖或者表的形式給出。圖3圖4圖5圖6（2）本次上機(jī)實(shí)驗(yàn)的收獲、心得體會(huì)。通過(guò)本次試驗(yàn)，我復(fù)習(xí)了C++語(yǔ)言的有關(guān)知識(shí)，對(duì)于C++語(yǔ)言的認(rèn)識(shí)更加深刻，鞏固了以往所學(xué)的內(nèi)容。同時(shí)，對(duì)于動(dòng)態(tài)規(guī)劃也有了更好的理解，尤其是對(duì)最優(yōu)子結(jié)構(gòu)的認(rèn)識(shí)更加深刻，從中學(xué)到了許多新的編程思想。知道了如何更好地設(shè)計(jì)算法，很大地提高了編程效率。這次上機(jī)我的收獲很大，學(xué)到了許多知識(shí)，可謂是收獲良多。附錄（C/C++源代碼）#include<iostream>#include<fstream>usingnamespacestd;voidPath(int*array,intline,intsize,intmax) //顯示最大和路徑{ int*path=newint[line]; //路徑存儲(chǔ) path[0]=array[1]; for(inti=size;i>=(size-line+1);i--) if(array[i]==max) //找最大值的下標(biāo) break; for(intj=line;j!=1;j--) //找上一層的對(duì)應(yīng)最大值 { if(i==(j+(j-1)*(j-2)/2)) { path[j-1]=array[i]-array[i-j+1]; i=i-j+1; continue; //當(dāng)前點(diǎn)為某行第一列時(shí)，該層路徑點(diǎn)的值為：其與其上層第一列值之差 } elseif(i==(j+j*(j-1)/2)) { path[j-1]=array[i]-array[i-j]; i-=j; continue; //當(dāng)前點(diǎn)為某行末列時(shí)，該層路徑點(diǎn)的值為：其與其上層末列值之差 } 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; } //當(dāng)前點(diǎn)非上情況，該層路徑點(diǎn)的值為：其與其上層相鄰兩列最大值之差 } } for(intk=0;k<line;k++) //顯示路徑 cout<<path[k]<<"\t"; cout<<endl;}intMaxAll(int*array,intline,intsize) //求路徑最大值{ inti=size-line+1; //最后一行的第一個(gè)數(shù)字下標(biāo) intmax=0; for(i;i<=size;i++) max=(max>array[i])?max:array[i]; returnmax;}intMaxValue(inta,intb) //求兩個(gè)值的最大值{ 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++) //從第二行開(kāi)始求三角形的每行每列到頂點(diǎn)的最大值 { if(k==1) //當(dāng)前點(diǎn)為第一列 { 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++; //求當(dāng)前點(diǎn)到頂點(diǎn)的最大值 continue; } if(k==j) //當(dāng)前點(diǎn)為該行最后一個(gè)數(shù)字 { array[i]+=array[i-j]; j++; k=1; continue; } }}voidShow(int*array,intline,intsize) //顯示三角形的內(nèi)容{ 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) //讀取三角形內(nèi)容{ inttemp; ifstreaminput(fileName,ios::in); input>>temp; //表示行數(shù)的數(shù)據(jù)，拋棄 for(inti=1;i<=size;i++) input>>array[i]; input.close();}intReadLen(char*fileName) //讀取行數(shù){ intline; ifstreaminput(fileName,ios::in); input>>line; input.close(); returnline;}voidmain(){ char*inFile="C:\\Users\\admin\\Desktop\\新建文件夾\\算法\\程序\\數(shù)字三角形\\input.txt"; //input文件的絕對(duì)路徑 char*outFile="C:\\Users\\admin\\Desktop\\新建文件夾\\算法\\程序\\數(shù)字三角形\\output.txt"; //output文件的絕對(duì)路徑 intline=ReadLen(inFile); //三角形的行數(shù) intsize=line+(line*(line-1))/2; //三角形的數(shù)字總數(shù) int*array=newint[size]; ReadArray(inFile,array,size); cout<<"從文件中讀