动态规划之数字三角形问题实验报告.doc

PAGE PAGE 0 综合性、设计性实验报告 姓名________学号__ 专业 计算机科学与技术 班级2008级3班 实验课程名称 算法设计与分析 指导教师及职称 开课学期 2010 至 2011 学年 上 学期 上课时间 2010年 11 月 3 日 PAGE 一、实验设计方案 实验名称：动态规划法实例编程 实验时间： 2010-11-03 小组合作： 是○ 否○ 小组成员： 1、实验目的： 理解动态规划算法的概念 掌握动态规划算法的基本要素 掌握设计动态规划算法的步骤 针对具体问题，能应用动态规划法设计有效算法 用C++实现算法，并且分析算法的效率 2、实验设备及材料：（注意：请自行填写，按实际情况写，各位同学的实验报告应有所区别） 硬件设备：pc 机器配置：AMD Athlon(tm)II x2 240 2.80GHz 、2.0GB内存 操作系统：Windows xp 开发工具：vc++6.0 3、实验内容： ①问题描述 给定一个由n行数字组成的数字三角形，试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字总和最大。 ②编程任务 试设计一个算法，计算出从三角形的顶到底的一条路径，使该路径经过的数字总和最大。 ③样例 例如：如下所示图 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 得到最优解 30 4、实验方法步骤及注意事项：（注意：此部分为本实验的关键部分，请自行填写，不得雷同！） ①实验步骤（参考教材自行填写） 根据题意找出最优解的性质，并刻画其结构特征。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 ②解题思路（注意：以下部分仅为提示，请自行填写；若表格不够，可自行拉伸。）。 从倒数第二行 p[n-2][0]开始，将自己与下一行同列的数相加在和自己与下一行下一列的数相加的结果比较，将大的存放在自己中。 ③代码为 #includeiostream #includefstream using namespace std; void find(int **p,int n) { int sum=0; int i,j; for(i=n-2;i=0;i--){ for(j=0;ji+1;j++){ if((p[i+1][j]+p[i][j])(p[i][j]+p[i+1][j+1])) p[i][j]=p[i][j]+p[i+1][j+1]; else p[i][j]=p[i+1][j]+p[i][j]; } } printf(%d \n,p[0][0]); } void main(){ int n; FILE *fp; int i,j; if((fp=fopen(123.txt,r))==NULL) { coutERROR!; exit(0);} fscanf(fp,%d,n); coutnendl; int **p=new int *[n]; for(i=0;in;i++){ p[i] =new int[i+1]; } for(i=0;in;i++) for(j=i;j=0;j--) fscanf(fp,%d,p[i][j]); for(i=0;in;i++) {for(j=i;j=0;j--) printf(%d ,p[i][j]); printf(\n); } find(p,n); fclose(fp); } 5．实验数据处理方法： ①数据输入 由文件input.txt 提供输入数据。 文件的第1行是数字三角形的行数n，1=n=100。接下来n行是数字三角形各行中的数字。所有数字在0~99之间。 ②结果输出 程序运行结束时，将计算结果输出到文件output.txt 中。 文件的第1 行中的数是计算出的最大值。 6．参考文献： 《计算机算法设计与分析（第3版）》 王晓东著 电子工业出版社 《算法设计与实验题解》王晓东著 电子工业出版社 指导老师对实验设计方案的意见： 指导老师签名： 2010年 11 月 15 日 二、实验报告 1、实验目的、设备与材料、实验内容、实验方法步骤见实验设计方案 2、实验现象、数据及结果