大学学算法设计数字三角形问题实验报告

《算法设计与分析》上机实验报告专业软件工程班级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<<"从文件中读