![点击分享此内容可以赚币 分享](/master/images/share_but.png)
算法分析与设计-大型实验报告样本.doc
《算法分析与设计-大型实验报告样本.doc》由会员分享,可在线阅读,更多相关《算法分析与设计-大型实验报告样本.doc(12页珍藏版)》请在咨信网上搜索。
1、算法分析大型实验报告编号标题算法题目一1005Jugs模拟题目二1007Do the Untwist字符串班 级:姓 名:学 号:指导老师:2011年8月ZJUT-1005 Jugs浙江大学,Turing Cup 2001,Special JudgeTime limit: 1 Seconds Memory limit: 32768KIn the movie Die Hard 3”, Bruce Willis and Samuel L。 Jackson were confronted with the following puzzle. They were given a 3gallon jug
2、 and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle. You have two jugs, A and B, and an infinite supply of water. There are three types of actions that you can use: (1) you can fill a jug, (2) you can empty a jug, and (3) you can p
3、our from one jug to the other. Pouring from one jug to the other stops when the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A. A problem is given
4、by a triple (Ca,Cb,N), where Ca and Cb are the capacities of the jugs A and B, respectively, and N is the goal. A solution is a sequence of steps that leaves exactly N gallons in jug B. The possible steps are fill A fill B empty A empty B pour A B pour B A success where pour A B means pour the conte
5、nts of jug A into jug B”, and success means that the goal has been accomplished。 You may assume that the input you are given does have a solution。 Input Input to your program consists of a series of input lines each defining one puzzle。 Input for each puzzle is a single line of three positive intege
6、rs: Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the goal。 You can assume 0 Ca = Cb and N = Cb =1000 and that A and B are relatively prime to one another. Output Output from your program will consist of a series of instructions from the list of the potential output lines whi
7、ch will result in either of the jugs containing exactly N gallons of water。 The last line of output for each puzzle should be the line success”。 Output lines start in column 1 and there should be no empty lines nor any trailing spaces. Sample Input3 5 45 7 3Sample Outputfill Bpour B Aempty Apour B A
8、fill Bpour B Asuccessfill Apour A Bfill Apour A Bempty Bpour A Bsuccess【全文翻译】在电影“虎胆龙威3-纽约大劫案”中,布鲁斯威利斯和杰里米艾恩斯遇到这样一个难题:给他们一个3加仑水壶和一个5加仑水壶,要求在5加仑水壶里准确装入4加仑的水。真是个难题呢。假定两个水壶A和B,供水量不限。可以使用三种方法装水:(1) 给一个水壶装水;(2) 把一个水壶倒空;(3) 从一个水壶倒进另一个水壶.当从一个水壶倒进另一个水壶时,如果第一个水壶倒空,或者第二个水壶装满就不能再倒了。例如,一个水壶A是5加仑和另一个水壶B是6加仑,水量是8加
9、仑,则从水壶A倒进水壶B时,让水壶B充满水而水壶A剩3加仑水。问题由3个参数:Ca,Cb和N,分别表示水壶A和B的容量,目标水量N。解决问题的目标是,给出一系列倒水的步骤,使水壶B中的水量恰好是N.“pour A B”,表示将水从水壶A倒进水壶B;“success”表示目标已经完成。 我们假定每个输入都有一个解决方案。输入输入有多行,每行都是一个难题。每个难题有三个正整数:Ca,Cb和N。假设0CaCb和NCb1000,且A和B互质。输出输出是由一系列倒水操作构成的,其目标是实现水壶B中有N加仑的水。最后一行是“success”;从第1列开始输出,行末没有空格。【算法分析】本题是“Specia
10、l Judge”,即答案不是唯一的,在服务器端有专门的程序负责判题.本题属于著名的“倒水问题”。在题目中已经介绍了“倒水”的规则:水是取之不尽的,可以把一个水壶全部灌满(原先是完全空的),或者把一个水壶全部倒空,或者从一个水壶倒进另一个水壶(当然不能溢出).题目中给出了三项假定:(1) 只有两个水壶。实现起来是方便的:我们可以从水壶A或者水壶B开始灌满水,将水壶A的水倒进水壶B,反之亦然。这会导致很多方案,因为题目是“Special Judge”,所以只要是正确的方案应该都是可行的。(2) 对每个输入,都有一个确定的输出。是不是有不可行的情况呢?如果两只水壶的容积分别是2和6,而要倒出容积为3
11、的水量是不可行的。显然2和6不符合题意“relatively prime to one another”。(3) 0 Ca = Cb 和 N = Cb =1000。也就是水壶A肯定比水壶B小,水壶B肯定能装下目标水量N。本算法采用一种非常简化的方法:仅仅将水壶A灌满水,也只从水壶A向水壶B倒水,当水壶B灌满水时就倒空。最后的答案是水壶B中的水量。对样例数据1,本算法的输出如下:fill Apour A Bfill Apour A Bempty Bpour A Bfill Apour A Bsuccess虽然灌水的过程与样本输出不一样,但服务器端会有专门的程序进行正确的评判。【程序代码】程序名称
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 大型 实验 报告 样本
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。