算法分析动态规划实验报告

《算法分析动态规划实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、-重庆大学实验报告实验题目：动态规划的应用学院：计算机学院专业班级：信息安全1班年级：2011级姓名：******学号：2011****完成时间：2013年6月1日指导教师：陈波重庆大学教务处制.---重庆大学本科学生实验项目任务书实验题目动态规划的应用学院计算机学院专业信息安全1班年级2011任务描述：有m排n列的柱桩，每一排的柱桩从左向右标号为1,2,…,n，且在每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃，每次都必须跳到下一排的柱桩上，且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第

2、j号桩上，那么他可跳到下一排的第j号桩上，也可跳到下一排的第j-1(ifj>1)或者j+1(ifj

3、容：1).完整的源码2).不依赖于IDE环境的可执行文件及测试数据3).电子版本项目报告，报告中至少包括对算法思想、递推方程式及该问题的最优子结构性质、程序结构的描述以及计算复杂度分析,以及测试结果c.第15周周五之前交，请直接提交至SAKAI。说明：1.不依赖于IDE环境的可执行文件指exe及其支持dll，测试数据均在同一目录中，在任意一台WinXP机器上直接双击exe即可运行。2.测试数据不少于20排20列，按照前述的格式放在test.txt文件里，执行结果存入output.txt文件里.---参考资料：AlgorithmDesign,JonK

4、leiberg.EvaTardos,CornellUniversity任务下达日期2013年5月26日完成日期2013年6月1日说明：学院、专业、年级均填全称，如：计算机学院、计算机科学与技术、2011。.---实验报告正文主要内容包括：1算法思想(a),使用动态规划自下而上方法，定义数组gem[i][j]表示第i排第j列木桩上的宝石数，数组maxb[i][j]表示从第i排第j列木桩到最后一排木桩所获得的最大宝石数。公式为：maxb[i][j]=max{gem[i][j]+maxb[i+1][j-1],gem[i][j]+maxb[i+1][j],

5、gem[i][j]+maxb[i+1][j+1]}其中i从n取到1求maxb的伪代码如下：Dynamic-Bottom-To-Up(maxb,gem,row,line)for(inti=1;i<=row;i++)maxb[line][i]=gem[line][i];//初始化maxbfor(inti=line-1;i=>1;i--)for(intj=row;j>=1;j--)maxb[i][j]=max{gem[i][j]+maxb[i+1][j-1],gem[i][j]+maxb[i+1][j],gem[i][j]+maxb[i+1][j+1]}

6、由上述代码可知，最多两个for循环，所以，时间复杂度为O(n2).(b),用数组path[]记录获得最大价值的路径，思想是自上而下比较每排的maxb最大值，将位置赋给数组path[]，然后再判断该最大值的下排与之相邻的三个maxb值，而后重复上面的操作，直到最后一排。求path的伪代码如下：path[1]=1//因为每次都是从第一排的第一桩开始，所以，path[1]=1n=1;for(inti=2;i<=line;i++)max{maxb[i][n-1],maxb[i][n],maxb[i][n+1]}path[i]=n;//如果maxb[i][n

7、]最大，则n=n-1;由该代码可知，求path的时间复杂度为O(n)。2关键代码描述#include#include.---usingnamespacestd;voidmain(){ofstreamoutfile;//实验结果读入outfile文件中ifstreaminfile;//实验数据从infile文件中读入outfile.open("output.txt",ios::trunc);infile.open("test.txt",ios::in);if(infile==NULL)cout<<"文件内没有内容

8、！";intline,row;infile>>line;infile>>row;int**gem;int**maxb;//