租用游艇问题_第1页
租用游艇问题_第2页
租用游艇问题_第3页
租用游艇问题_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

租用游艇问题1. 问题描述长江游艇俱乐部在长江上设置了n个游艇出租站1，2，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r（i，j），1ijn。试设计一个算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。算法设计：对于给定的游艇出租站i对游艇出租站j之间的租金为r（i，j），1ijn，计算从游艇出租站1到游艇出租站n所需的最少租金。2. 算法流程分析设游艇出租站有N个，而且每两个站的租金都是不一样的，用f（i，j）表示每两个站之间的租金费用。当要租用游艇从一个站到另外一个站时，采取不同的停靠站策略就有不同的租金。例如输入3,5,15,7，,那么从第一个站到第三个站，租金是15元，但是第一个站到第二个站的租金只需5元，第二到第三个站的租金要7元，因此可采用先到第二个站，把游艇归还，然后再从第二个站租用游艇到第三个站，因此我们总共需要的费用就是5+7=12元，比直接从第一个站到第三个站要花15元更经济，也就是最少花费。这是一个优化问题，并且具有最优子结构，表示前n-1个站的最优解，那么前n个站的最优解一定包含前n-1个站的最优解，并且它们具有重叠性。3. 算法正确性证明通过几组实例证明合法的输入可以得到正确的输出。实例见附录第2部分。4. 算法复杂度分析O（n3）5.参考文献1 王晓东编著，计算机算法设计与分析（第4版）。北京：电子工业出版社，2012.26.附录（1）可执行代码如下：#includeusing namespace std;int w200,z200200,n;int solve(int h) if(wh0)return wh;if(h=n-1)return zhn;int minn=zhn;for(int k=h+1;kn;k+)int a=zhk+solve(k);if(aminn)minn=a;wh=minn;return minn;int main() int i,j;cout请输入游艇出租站的个数：n;for(i=1;in;i+)for(j=i+1;j=n;j+) cout请输入从i站到j站的租金：zij;cout从游艇出租站1到游艇出租站n所需的最少租金：endls
人人文库> 全部分类> 应用文书 > 事务文书

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论