算法分析动态规划实验报告(共9页).doc

《算法分析动态规划实验报告(共9页).doc》由会员分享，可在线阅读，更多相关《算法分析动态规划实验报告(共9页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、j号桩上，那么他可跳到下一排的第j号桩上，也可跳到下一排的第j-1 (if j1)或者 j+1 (if jn) 号桩上，并得到桩上的宝石。计算出一条最佳的跳跃顺序，使杂技演员获得的宝石的总价值最大。（输入）4 4 （4排4列的柱桩，空格隔开）1,1, 1, 1 （放在第1排各桩上的宝石价值，逗号隔开）1, 5, 1, 1 。2 ,1, 10, 1 。20 ,1, 1, 1 （放在第4排各桩上的宝石价值） （输出）28 （最大价值）1 (开始位置，固定)2 (在第二排的位置)1 (在第三排的位置)1 (在第四排的位置)p 设计要求：a.单人独立完成；b.提交名为 学号_姓名_PJ.rar 的压缩

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

4、Eva Tardos, Cornell University任务下达日期 2013 年 5月 26 日完成日期2013年 6 月 1 日说明：学院、专业、年级均填全称，如：计算机学院、计算机科学与技术、2011。专心-专注-专业实验报告正文主要内容包括：1 算法思想 (a), 使用动态规划自下而上方法，定义数组gemij表示第i排第j列木桩上的宝石数，数组maxbij表示从第i排第j列木桩到最后一排木桩所获得的最大宝石数。公式为： maxbij=maxgemij+maxbi+1j-1,gemij+maxbi+1j, gemij+maxbi+1j+1 其中i从n取到1求maxb的伪代码如下：Dy

5、namic-Bottom-To-Up(maxb,gem,row,line)for(int i=1;i1;i-)for(int j=row;j=1;j-) maxbij=maxgemij+maxbi+1j-1,gemij+maxbi+1j, gemij+maxbi+1j+1 由上述代码可知，最多两个for循环，所以，时间复杂度为O(n2).(b), 用数组path记录获得最大价值的路径，思想是自上而下比较每排的maxb最大值，将位置赋给数组path，然后再判断该最大值的下排与之相邻的三个maxb值，而后重复上面的操作，直到最后一排。求path的伪代码如下：path1=1 /因为每次都是从第一排的

6、第一桩开始，所以，path1=1n=1;for(int i=2;i=line;i+)max maxbin-1, maxbin, maxbin+1 pathi=n; /如果maxbin最大，则 n=n-1;由该代码可知，求path的时间复杂度为O(n)。2 关键代码描述#include#includeusing namespace std;void main()ofstream outfile; /实验结果读入outfile文件中ifstream infile; /实验数据从infile文件中读入outfile.open (output.txt,ios:trunc);infile.open (t

7、est.txt,ios:in);if(infile=NULL)coutline;infilerow;int *gem;int *maxb; /数组gem表示柱桩的宝石，数组maxb表示第i行第j列到最后一行所获得的最大宝石数；int num=abs(line-row);gem=(int*) new int*line+num+1;maxb=(int*) new int*line+num+1;/动态为数组gem和maxb分配空间for(int i=0;i=line;i+)gemi=new introw+num+1;maxbi=new introw+num+1;for(int i=1;i=line;

8、i+)for(int j=1;jgemij; /输入柱桩的宝石for(int i=1;i1;i-)for(int j=row;j=1;j-)int n=i-1; if(gemnj+maxbij-1)=(gemnj+maxbij)&(gemnj+maxbij-1)=(gemnj+maxbij+1)maxbnj=gemnj+maxbij-1;continue; if(gemnj+maxbij)=(gemnj+maxbij-1)&(gemnj+maxbij)=(gemnj+maxbij+1)maxbnj=gemnj+maxbij;continue; if(gemnj+maxbij+1)=(gemnj

9、+maxbij-1)&(gemnj+maxbij+1)=(gemnj+maxbij)maxbnj=gemnj+maxbij+1;continue;outfilemaxb11 (最大价值)n;int *path,n=1;/数组path用来记录获得最多宝石数时，经过每排的位置path=new intline+num+1;path1=1; /因为每次都是从第一排的第一桩开始，所以，path【1】=1/*从上往下找出每排p取得最大值得位置，存入数组s中*/for(int i=1;i=maxbmn)&(maxbmn-1=maxbmn+1)pathm=n-1;n=n-1;continue;if(maxbm

10、n=maxbmn-1)&(maxbmn=maxbmn+1)pathm=n;n=n;continue;if(maxbmn+1=maxbmn)&(maxbmn+1=maxbmn-1)pathm=n+1;n=n+1;continue;cout打开output文件查看结果！endl;for(int i=1;i=line;i+)outfilepathi (第i排位置)n;for(int i=0;i=line;i+)delete gemi;delete gem;for(int i=0;i=line;i+)delete maxbi;delete maxb;delete path;outfile.close

11、();infile.close();3 运行效果/*test.txt内的内容*/24 201 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 5 1 1 2 3 1 4 5 3 2 1 22 12 2 1 1 1 1 12 1 30 1 32 1 1 2 4 3 5 4 12 2 22 1 1 1 1 2620 1 1 1 11 3 4 55 4 3 2 1 11 23 1 2 3 112 2 31 2 3 4 5 6 7 8 9 0 7 5 3 3 1 4 5 3 4 20 9 7 6 5 4 3 2 1 6 4 3 87 3 2 5 6 4 8 96 8 9

12、44 6 6 3 5 7 4 3 3 3 4 5 7 8 4 5 114 6 3 6 2 6 3 8 4 5 3 2 3 4 5 6 7 8 9 126 34 6 8 4 2 8 7 64 5 2 5 2 3 4 5 6 7 81 116 3 2 2 5 2 5 1 1 1 1 1 5 5 5 5 5 5 5 51 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 4 4 41 1 1 1 1 1 1 1 1 1 1 1 7 7 7 7 7 7 7 72 2 2 2 2 2 21 1 1 1 1 1 8 8 8 8 8 8 8 83 3 3 3 32 2 2 2 2 2 1 1

13、3 22 4 4 2 4 2 56 34 6 8 4 2 8 7 64 5 2 5 2 3 4 5 6 7 81 116 3 2 2 5 2 5 1 1 1 1 1 5 5 5 5 5 5 5 51 1 1 1 1 1 1 1 1 1 1 1 4 4 4 4 4 4 4 41 1 1 1 1 1 1 1 1 1 1 1 7 7 7 7 7 7 7 72 2 2 2 2 2 21 1 1 1 1 1 8 8 8 8 8 8 8 83 3 3 3 32 2 2 2 2 2 1 1 3 22 4 4 2 4 2 50 9 7 6 5 4 3 2 1 6 4 3 87 3 2 5 6 4 8 96 8

14、 9 44 6 6 3 5 7 4 3 3 3 4 5 7 8 4 5 114 6 3 6 2 6 3 8 4 5 3 2 3 4 5 6 7 8 9 126 34 6 8 4 2 8 7 64 5 2 5 2 3 4 5 6 7 81 11/*output.txt内的内容*/345 (最大价值)1 (第1排位置)2 (第2排位置)3 (第3排位置)4 (第4排位置)5 (第5排位置)6 (第6排位置)7 (第7排位置)8 (第8排位置)9 (第9排位置)8 (第10排位置)7 (第11排位置)6 (第12排位置)7 (第13排位置)8 (第14排位置)9 (第15排位置)10 (第16排位置

15、)11 (第17排位置)12 (第18排位置)13 (第19排位置)14 (第20排位置)13 (第21排位置)14 (第22排位置)15 (第23排位置)16 (第24排位置)4 总结(注明每个人的分工和工作量百分比)本组由2011*组成。2011*负责项目的所有部分，所作贡献占工作量的100%。格式要求纸张大小：A4页边距：上下左右各留20mm行距：采用固定值20磅标题：章节标题使用三号黑体、居中（大标题使用四号黑体，小标题使用小四号黑体）正文：小四号宋体页眉：“学生姓名：课程设计题目”，五号宋体，居中页脚：阿拉伯数字编页码，小五号宋体，居中参考文献：五号宋体附录：五号宋体备注：1、 学生：提交的实验报告电子文档命名为：“组号（2位数字）年级（两位数字不要“级”字）专业（缩写：计算机科学与技术专业（计科）、网络工程专业（网络）、信息安全专业（信息）、物联网工程（物联网）项目组成员（学号（八位数字）姓名）doc。如第1组，专业为“计算机科学与技术”专业，项目组成员有：张三（学号），李四（学号），王五（学号），完成的课程设计报告命名为：01_10计科_张三_李四_王五。2、 教师：报告批阅完成后将评价后的实验报告转换为PDF格式文件刻光盘，连同实验成绩单一起放入试卷袋存档。