1. 您所在位置：首页 > 水利工程 > 设计报告 > 重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码).doc

重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码).doc

  • 177.00 KB
  • 10页

重庆大学算法导论跳桩得珠宝问题项目报告(包含报告和源代码).doc

  • 10页
  • 当前文档由用户上传发布，收益归属用户
  1. 1、本文档共5页，可阅读全部内容。
  2. 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
  3. 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
  4. 文档侵权举报电话：19940600175。
'重庆大学项目报告项目题目：跳桩得珠宝问题学院：专业班级：计科年级：2011级姓名：学号：完成时间：2013年6月7日指导教师：陈波重庆大学教务处制 项目报告正文一.问题描述有m排n列的柱桩，每一排的柱桩从左向右标号为1,2,…,n，且在每个柱桩上预先放好价值不一样的宝石。现在有位杂技演员从第一排的第1号柱桩开始跳跃，每次都必须跳到下一排的柱桩上，且每次跳跃最多只能向左或向右移动一个桩子。也就是说如果现在杂技演员站在第j号桩上，那么他可跳到下一排的第j号桩上，也可跳到下一排的第j-1(ifj>1)或者j+1(ifj=0所以方程也可以这样写：opt[i,j]=max{opt[i-1,j],max（opt[i-1,j-1]，opt[i-1,j+1]）}+a[i,j]同理j=i时方程也可以写成上面那样，所以方程综合为：opt[i,j]=max{opt[i-1,j],max（opt[i-1,j-1]，opt[i-1,j+1]）}+a[i,j](1";j+=path[i][j];}六.计算复杂度分析此实验中，作为基本操作的原操作是max（）；即比较函数，在循环中，进行了N^2次，而比较函数其运行时间为常数O（1），故计算最大值部分T（n）=O（n^2）；同理，在路径输出部分，关键代码是j+=path[i][j];其T（n）=O(n);该算法总的时间复杂度T（n）=O（n^2）。9 七.测试结果:test.txt文件：柱桩20排20列：9 柱桩4排4列：9 全部代码：#include#include#includeusingnamespacestd;intconstMAX=20;intM,N,num=0;intmain(){intcount=0;fstreamfile1,file2;file1.open("test.txt",ios::in);if(!file1)cout<<"inputfilenotfounded"<>num;if(num==2){cout<<"请输入排与列（排与列均小于20）："<>M>>N;}else{if(num==1)9 M=N=MAX;elsecout<<"输入不符，重新启动！";}intdp[MAX][MAX]={0};intpath[MAX][MAX]={MAX};//描写路径的坐标while(!file1.eof())//是否到文件结尾{for(inti=0;i>dp[i][j];count++;}if(count==M*N)break;}file2.open("output.txt",ios::out);if(!file2)cout<<"outputfilenotfounded"<=0;i--){for(intj=0;j<=N-1;j++){9 if(j==0){dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];if(dp[i+1][j]>dp[i+1][j+1])//正下方大path[i][j]=0;//选择正下方else//右边大path[i][j]=1;//选择右边}else{dp[i][j]=max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1]))+dp[i][j];if((dp[i+1][j-1]>=dp[i+1][j])&&(dp[i+1][j-1]>=dp[i+1][j+1]))path[i][j]=-1;elseif((dp[i+1][j]>dp[i+1][j-1])&&(dp[i+1][j]>=dp[i+1][j+1]))//正下方大path[i][j]=0;//选择正下方else//右边大path[i][j]=1;//选择右边}}}file2<

您可能关注的文档

相关文档

最近下载