数字三角形.doc

算法竞赛入门课程实验报告 实验项目： 数字三角形 专业班级： 学生姓名： 学 号： 课程教师： 指导教师： 实验时间： 2016 年 5 月 25 日 计算机科学系实验题目：数字三角形试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字总和最大。例如，上述数字三角形的最优解 30，自顶向下的路径为 7-3-8-7-5。数据输入：由文件 input.txt 提供输入数据。文件的第 1 行是数字三角形的行数，该数 字在 1 到 100 之间。接下来 n 行是数字三角形各行中的数字。所有数字在0至 99 之间。结果输出：程序运行结束时，将计算结果输出到文件 output.txt 中。文件第 1 行中的数 是计算出的最大值。输入文件实例输出文件实例input.txtoutput.txt530738810274445265实验目的：（1）理解动态规划算法的概念；（2）掌握动态规划算法的基本要素；（3）掌握设计动态规划算法的步骤；（4）针对具体问题，能应用动态规划法设计有效算法；（5）用 c+实现算法，并且分析算法的效率。实验要求：（1）认真阅读实验指导书,设计相应的算法； （2）根据设计的算法写出程序；（3）设计好相应的测试用例。实验内容：实验分析采用分治法自底向上递推即可。二维数组 a 存放输入的三角形序列， 对该二维数组做递推，公式为： if(ai+1j=ai+1j+1) aij+=ai+1j; else aij+=ai+1j+1;递推结束后，a00即为所求最大值。变化后的 a 可自顶向下递推路径，一维数组 b 记录路径（确切地讲，是记录每行路径数据的列），公式为： if(ai+1j=ai+1j+1) bi+1=j; else bi+1=j+1; j=bi+1;cibi即为路径各个数据。程序代码#includeint i,j,b20,c100100,max=0;void summax(int a100,int n)for(i=0;in;i+)for(j=0;j=0;i-)for(j=0;j=ai+1j+1) aij+=ai+1j; else aij+=ai+1j+1;max=a00; for(i=0,j=0;i=ai+1j+1) bi+1=j; else bi+1=j+1; j=bi+1; b0=0;int main()file *in,*out;int data100100,m;in=fopen(e:intput.txt,r); if(in=null) printf(open error!n); return -1;fscanf(in,%d,&m);for(i=1;i=m;i+)for(j=0;ji;j+)fscanf(in,%d ,&datai-1j);fclose(in);summax(data,m);out=fopen(e:output.txt,w); if(out=null) printf(open error!n); return -1;fprintf(out,%dn,max);for(i=0;im;i+)fprintf(out,%d ,cibi);fclose(out);return 0;实验结果与记录： 收获与体会：本次实验中，在实验指导书及教师的指导下，比较成功的完成了实验，不过还是遇到了一些问题。如在对文件的操作方面不够娴熟。不过，在老师的帮助下，这一问题还是得到了很好的解决，比较完满的完成了任务。虽然感觉到代码不怎么长，但是还是感觉能力不足，尤其对算法思想的理解不够透彻，还是觉得