算法分析與設(shè)計(jì)-大型實(shí)驗(yàn)報(bào)告樣本

算法分析大型實(shí)驗(yàn)報(bào)告編號(hào)標(biāo)題算法題目一1005Jugs模擬題目二1007DotheUntwist字符串班級(jí):姓名:學(xué)號(hào):指導(dǎo)老師：2011年8月ZJUT-1005JugsSpecialJudgeTimelimit: 1SecondsMemorylimit:32768KInthemovie"DieHard3”BruceWillisandSamuelL。Jacksonwereconfrontedwiththefollowingpuzzle.Theyweregivena3 —gallonjuganda5-gallonjugandwereaskedtofillthe5-gallonjugwithexactly4gallons.Thisproblemgeneralizesthatpuzzle.Youhavetwojugs,AandB,andaninfinitesupplyofwater.Therearethreetypesofactionsthatyoucanuse:(1)youcanfillajug,(2)youcanemptyajug,and(3)youcanpourfromonejugtotheother.Pouringfromonejugtotheotherstopswhenthefirstjugisemptyorthesecondjugisfull,whichevercomesfirst.Forexample,ifAhas5gallonsandBhas6gallonsandacapacityof8,thenpouringfromAtoBleavesBfulland3gallonsinA.Aproblemisgivenbyatriple(Ca,Cb,N),whereCaandCbarethecapacitiesofthejugsAandB,respectively,andNisthegoal.AsolutionisasequeneeofstepsthatleavesexactlyNgallonsinjugB.ThepossiblestepsarefillAfillBemptyAemptyBpourABpourBAsuccesswhere"pourAB"means"pourthecontentsofjugAintojugB,and"success浙江大學(xué)，TuringCup2001浙江大學(xué)，TuringCup2001,Youmayassumethattheinputyouaregivendoeshaveasolution。InputInputtoyourprogramconsistsofaseriesofinputlineseachdefiningonepuzzle。Inputforeachpuzzleisasinglelineofthreepositiveintegers:Ca,Cb,andN.CaandCbarethecapacitiesofjugsAandB,andNisthegoal。Youcanassume0<Ca<=CbandN<=Cb<=1000andthatAandBarerelativelyprimetooneanother.OutputOutputfromyourprogramwillconsistofaseriesofinstructionsfromthelistofthepotentialoutputlineswhichwillresultineitherofthejugscontainingexactlyNgallonsofwater。Thelastlineofoutputforeachpuzzleshouldbetheline"success。Outputlinesstartincolumn1andthereshouldbenoemptylinesnoranytrailingspaces.SampleInput354573SampleOutputfillBpourBAemptyApourBAfillBpourBAsuccessfillApourABfillApourABemptyBpourABsuccess【全文翻譯】在電影“虎膽龍威3-紐約大劫案”中，布魯斯?威利斯和杰里米?艾恩斯遇到這樣一個(gè)難題：給他們一個(gè)3加侖水壺和一個(gè)5加侖水壺，要求在5加侖水壺里準(zhǔn)確裝入4加侖的水。真是個(gè)難題呢。假定兩個(gè)水壺A和B,供水量不限。可以使用三種方法裝水：（1）給一個(gè)水壺裝水;（2）把一個(gè)水壺倒空；（3）從一個(gè)水壺倒進(jìn)另一個(gè)水壺.當(dāng)從一個(gè)水壺倒進(jìn)另一個(gè)水壺時(shí)，如果第一個(gè)水壺倒空，或者第二個(gè)水壺裝滿(mǎn)就不能再倒了。例如，一個(gè)水壺A是5加侖和另一個(gè)水壺B是6加侖,水量是8加侖，則從水壺A倒進(jìn)水壺B時(shí)，讓水壺B充滿(mǎn)水而水壺A剩3加侖水。問(wèn)題由3個(gè)參數(shù)：Ca,Cb和N，分別表示水壺A和B的容量，目標(biāo)水量N。解決問(wèn)題的目標(biāo)是，給出一系列倒水的步驟，使水壺B中的水量恰好是N.“pourAB”，表示將水從水壺A倒進(jìn)水壺B;“success"表示目標(biāo)已經(jīng)完成。我們假定每個(gè)輸入都有一個(gè)解決方案。輸入輸入有多行，每行都是一個(gè)難題。每個(gè)難題有三個(gè)正整數(shù)： Ca,Cb和N。假設(shè)0<Ca<Cb和N<Cbw1000，且A和B互質(zhì)。輸出輸出是由一系列倒水操作構(gòu)成的,其目標(biāo)是實(shí)現(xiàn)水壺B中有N加侖的水。最后一行是“success”；從第1列開(kāi)始輸出，行末沒(méi)有空格?！舅惴ǚ治觥勘绢}是“SpecialJudge",即答案不是唯一的，在服務(wù)器端有專(zhuān)門(mén)的程序負(fù)責(zé)判題 ?本題屬于著名的“倒水問(wèn)題”。在題目中已經(jīng)介紹了“倒水”的規(guī)則：水是取之不盡的,可以把一個(gè)水壺全部灌滿(mǎn)（原先是完全空的）,或者把一個(gè)水壺全部倒空,或者從一個(gè)水壺倒進(jìn)另一個(gè)水壺（當(dāng)然不能溢出）.題目中給出了三項(xiàng)假定：（1） 只有兩個(gè)水壺。實(shí)現(xiàn)起來(lái)是方便的：我們可以從水壺A或者水壺B開(kāi)始灌滿(mǎn)水,將水壺A的水倒進(jìn)水壺B,反之亦然。這會(huì)導(dǎo)致很多方案 ，因?yàn)轭}目是“SpecialJudge”，所以只要是正確的方案應(yīng)該都是可行的。對(duì)每個(gè)輸入，都有一個(gè)確定的輸出。是不是有不可行的情況呢？如果兩只水壺的容積分別是 2和6，而要倒出容積為3的水量是不可行的。顯然2和6不符合題意“relativelyprimetooneanothe”。0 〈Ca<=Cb和N〈=Cb<=1000。也就是水壺A肯定比水壺B小，水壺B肯定能裝下目標(biāo)水量N。本算法采用一種非常簡(jiǎn)化的方法：僅僅將水壺A灌滿(mǎn)水，也只從水壺A向水壺B倒水,當(dāng)水壺B灌滿(mǎn)水時(shí)就倒空。最后的答案是水壺B中的水量。對(duì)樣例數(shù)據(jù)1,本算法的輸出如下：fillApourABfillApourABemptyBpourABfillApourABsuccess雖然灌水的過(guò)程與樣本輸出不一樣，但服務(wù)器端會(huì)有專(zhuān)門(mén)的程序進(jìn)行正確的評(píng)判?！境绦虼a】程序名稱(chēng)：zju1006。cpp題目：Jugs提交語(yǔ)言：C++運(yùn)行時(shí)間：10ms運(yùn)行內(nèi)存：836KB#include<iostream>usingnamespacestd;intmain(){intca,cb,n;TOC\o"1-5"\h\zwhile(cin>>ca>>cb>>n) {intbnow;intb=0;while(b!=n) {〃只要b水壺不溢出，就讓a水壺灌個(gè)夠for(inti=0;i〈=(cb-b)/ca;i++) {cout〈<”fillA”<<endlcout<〈”pourAB"〈〈endl;bnow=b+ca*(i+1); //b水壺現(xiàn)在的容量if(bnow==n) break；}if(bnow==n)break； //退出while循環(huán)cout<〈"emptyB"〈〈endl;//最后一次灌滿(mǎn)b水壺時(shí)，a水壺剩下的容量inta;a=ca-(cb-b)%ca;cout<<”pourAB"<<endl//a水壺剩余的部分倒入 b水壺中b=a；if(b==n) break;}cout<〈”success<endl;}return0;}【分析提高】如果水壺的數(shù)量多于兩個(gè)，倒起來(lái)肯定要麻煩得多。在百度中輸入“灌水定理 ",會(huì)搜索到相關(guān)的信息，例如： http：///read—self_study—65528-0—2。html.ZJUT1007-DOtheUntwist浙江大學(xué)，TuringCup2001,浙江大學(xué)，TuringCup2001,Timelimit: 1Seconds Memorylimit:32768KCryptographydealswithmethodsofsecretcommunicationthattransformamessage(theplaintext)intoadisguisedform(theciphertext)sothatnooneseeingtheciphertextwillbeabletofigureouttheplaintextexcepttheintendedrecipient。Transformingtheplaintexttotheciphertextisencryption;transformingtheciphertexttotheplaintextisdecryption.Twistingisasimpleencryptionmethodthatrequiresthatthesenderandrecipientbothagreeonasecretkeyk,whichisapositiveinteger.個(gè)人收集整理，勿做商業(yè)用途Thetwistingmethodusesfourarrays:plaintextandciphertextarearraysofcharacters,andplaincodeandciphercodearearraysofintegers。Allarraysareoflengthn,wherenisthelengthofthemessagetobeencrypted.Arraysareoriginzero,sotheelementsarenumberedfrom0ton—1.Forthisproblemallmessageswillcontainonlylowercaseletters,theperiod,andtheunderscore(representingaspace)。Themessagetobeencryptedisstoredinplaintext.Givenakeyk,theencryptionmethodworksasfollows.Firstconvertthelettersinplaintexttointegercodesinplaincodeaccordingtothefollowingrule:'_'=0,'a' =1,'b。.,=z2,.' =26,and=2。Next,converteachcodeinplaincodetoanencryptedcodeinciphercodeaccordingtothefollowingformula:forallifrom0ton-1,ciphercode[i] =(plaincode[kimodn] -i)mod28.(Herexmodyisthepositiveremainderwhenxisdividedbyy.Forexample, 3mod7=3,22mod8=6,and—1mod28=27.YoucanusetheC'%'operatororPascal'mod'operatortocomputethisaslongasyouaddyiftheresultisnegative.)Finally,convertthecodesin

ciphercodebacktolettersinciphertextaccordingtotherulelistedabove。 Thefinaltwistedmessageisinciphertext.Twistingthemessagecatusingthekey5yieldsthefollowing:Array012plaintext'c''a''t'plaincode3120ciphercode31927ciphertext'c''s',yourYourtaskistowriteaprogramthatcanuntwistmessages,i。e。，converttheciphertextbacktotheoriginalplaintextgiventhekey k.Forexample,giventhekey5andciphertext ',yourprogrammustoutputtheplaintext'cat '.Theinputfilecontainsoneormoretestcases,followedbyalinecontainingonlythenumber0thatsignalstheendofthefile.Eachtestcaseisonalinebyitselfandconsistsofthekeyk,aspace,andthenatwistedmessagecontainingatleastoneandatmost70characters.Thekeykwillbeapositiveintegernotgreaterthan300。Foreachtestcase,outputtheuntwistedmessageonalinebyitself.Note:youcanassumethatuntwistingamessagealwaysyieldsauniqueresult。（Forthoseofyouwithsomeknowledgeofbasicnumbertheoryorabstractalgebra,thiswillbethecaseprovidedthatthegreatestcommondivisorofthekeykandlengthnis1,whichitwillbeforalltestcases.）Exampleinput:5cs.101thqqxw.lui。qswerb_ylxmhzjsys。virpbkr0Exampleoutput:catthis_is_a_secretbeware._dogs_barking【全文翻譯】加密技術(shù)是把消息（明文）變換成一種偽裝的形式（密文）進(jìn)行秘密通信的一種方法，除收件人之外，任何人看了密文也不能翻譯成明文。 把明文變換成密文稱(chēng)為加密， 把密文轉(zhuǎn)換成明文稱(chēng)為解密。Twisting（扭曲）是一個(gè)簡(jiǎn)單的加密方法，它需要發(fā)送者和接受者都共同認(rèn)可的加密關(guān)鍵字k，是一個(gè)正整數(shù)。Twisting方法使用4個(gè)數(shù)組：plaintext和ciphertext是字符數(shù)組，plaincode和ciphercode是整數(shù)數(shù)組.所有數(shù)組的長(zhǎng)度為n，這是對(duì)信息加密的長(zhǎng)度。所有數(shù)組初始時(shí)為空，下標(biāo)從0到n—1。消息只包含小寫(xiě)字母，句號(hào)和下劃線(xiàn)（代表空格） 。消息存儲(chǔ)在數(shù)組plaintext中。給定關(guān)鍵k，加密方法如下：首先把 plaintext的字母轉(zhuǎn)換成數(shù)字編碼存放到數(shù)組 plaincode中，轉(zhuǎn)換規(guī)則：'_' =' =1，‘b'=2, ' z' = 26,'。'=27。然后將存放在數(shù)組 plaincode中的數(shù)字編碼按下列公式轉(zhuǎn)換成加密代碼存放到數(shù)組ciphercode中：i從0到n-1,ciphercode[i] =(plaincode[kximodn]-i)mod28。(這里mod是模運(yùn)算，例如，3mod7=3,22mod8=6,-1mod28=27°C語(yǔ)言中使用’％'運(yùn)算符，Pascal語(yǔ)言中使用’mod'運(yùn)算符)。最后，把存放在ciphercode中的數(shù)字編碼按上述方法轉(zhuǎn)換成密文存放到數(shù)組 ciphertext中.你的任務(wù)是編寫(xiě)程序，實(shí)現(xiàn)消息的 untwist(解密)，即給定關(guān)鍵字k，將密文恢復(fù)至原來(lái)的明文。例如，關(guān)鍵字是 5，密文是’cs?！?，程序必須輸出明文’ cat'。輸入文件包含一個(gè)或多個(gè)測(cè)試?yán)?，數(shù)字0表示輸入結(jié)束。每個(gè)測(cè)試?yán)恍校宏P(guān)鍵字k,空格，然后是密文，密文至少一個(gè)字符，最多 70個(gè)字符.關(guān)鍵k是一個(gè)正整數(shù)，不超過(guò)300。對(duì)每個(gè)測(cè)試?yán)?，輸出一行解密的明文。注意：你可以假定解密消息的結(jié)果是唯一的?！舅惴ǚ治觥勘绢}是屬于加密和解密類(lèi)型的題目， 當(dāng)然加密和解密的方法是比較簡(jiǎn)單的。 題目中給出了加密的過(guò)程，要求我們給出解密的結(jié)果 .分為以下三步：根據(jù)原始密文，計(jì)算ciphercode原始密文ciphercodea~zASCII值一96,其結(jié)果表明為：'言1,'b—2,。..,'z-^26027根據(jù)ciphercode,計(jì)算plaincode題目中給出了由plaincode計(jì)算ciphercode的公式：ciphercode[i] =(plaincode[k*imodn]—i)mod28現(xiàn)在求plaincode,令t=k*i%n (運(yùn)算符*比%高一個(gè)優(yōu)先級(jí)),t是密文的坐標(biāo)轉(zhuǎn)換成明文的坐標(biāo)貝U：plaincode:t]=(ciphercode[i]+i) %28根據(jù)plaincode,計(jì)算解密后的明文plaincode解密后的明文值為1?26時(shí)a~z：1—'a',2—'b',…,26—'z'027。以測(cè)試數(shù)據(jù)1為例:密文坐標(biāo)012密文csciphercode31927轉(zhuǎn)換成明文的坐標(biāo)t021plaincode3201明文cta【程序代碼】程序名稱(chēng)：zju1006.cpp題目：DotheUntwist

提交語(yǔ)言：C++運(yùn)行時(shí)間：10ms運(yùn)行內(nèi)存：836K#inelude〈iostream>#inelude〈string>usingnamespaeestd;intmain(){//key〃原始密文//key〃原始密文〃解密后的明文//ciphercode&&k){chara[80];charc[80];intb:100];while(cin?kcin〉>a;intn=strlen(a);II根據(jù)原始密文，計(jì)算ciphercodefor(inti=0;i〈n;i++){if(a[i]>= '&&a:i:<='z')b:i: =a:i]-96;elseif(a[i]=='_')b:i]=0;elseb[i]=27;}intd[100]; //plaincode//根據(jù)ciphercode,計(jì)算plaincodefor(inti=0;i<n; i++) {intt=k衣i%n;d:t]= (b:i]+i)%28;}//根據(jù)plaincode，計(jì)算解密后的明文for(inti=0;i〈n;i++){if(d:i:>0&&d:i:〈27)c[i]=d[i]+96;elseif(d[i]==0)c[i]='_':elsec[i]='。';}//輸出解密后的明文for(inti=0;i〈n;i++)cout<<c[i];cout〈〈endl;}return0;ZJU2109—FatMouse'Trade浙江省大學(xué)生程序設(shè)計(jì)競(jìng)賽， SunnyCup2004,浙江省大學(xué)生程序設(shè)計(jì)競(jìng)賽， SunnyCup2004,Timelimit: 1SecondsMemorylimit:32768KFatMousepreparedMpoundsofcatfood,readytotradewiththecatsguardingthewarehousecontaininghisfavoritefood,JavaBean。ThewarehousehasNrooms。Thei-throomcontainsJ[i]poundsofJavaBeansandrequiresF[i]poundsofcatfood。FatMousedoesnothavetotradeforalltheJavaBeansintheroom,instead,hemaygetJ[i]*a%poundsofJavaBeansifhepaysF[i]*a%poundsofcatfood。Hereaisarealnumber。Nowheisassigningthishomeworktoyou:tellhimthemaximumamountofJavaBeanshecanobtain.InputTheinputconsistsofmultipletestcases.Eachtestcasebeginswithalinecontainingtwonon—negativeintegersMandN。ThenNlinesfollow,eachcontainstwonon-negativeintegersJ[i]andF[i]respectively.Thelasttestcaseisfollowedbytwo-1's。Allintegersarenotgreaterthan1000。OutputForeachtestcase,printinasinglelinearealnumberaccurateupto3decimalplaces,whichisthemaximumamountofJavaBeansthatFatMousecanobtain。SampleInput537232203251824151510-1—1SampleOutput13.33331。500Author:CHEN,Yue【全文翻譯】FatMouse準(zhǔn)備了M磅的貓糧，打算與看守倉(cāng)庫(kù)的貓交換食品，倉(cāng)庫(kù)里存放著它喜愛(ài)的食物JavaBean。倉(cāng)庫(kù)有n個(gè)庫(kù)房，庫(kù)房i存放J[i]磅JavaBean,需要F[i:磅貓糧予以交換。 FatMouse不需要交換庫(kù)房里所有的 JavaBean,可以按比例交換。如果它支付 F[i]xa%磅的貓糧，就可以換取J[i]xa%磅的JavaBean,其中a是實(shí)數(shù)?，F(xiàn)在明確編程任務(wù)：FatMouse最多能換取多少JavaBean.輸入輸入包含多組測(cè)試?yán)?！?duì)每個(gè)測(cè)試?yán)谝恍惺莾蓚€(gè)非負(fù)整數(shù) M和N。接下來(lái)N行，每行兩個(gè)非負(fù)整數(shù) J:i]和F[i]。最后一個(gè)測(cè)試?yán)莾蓚€(gè)一 1不需要處理.所有的整數(shù)都不超過(guò)1000。輸出對(duì)每個(gè)測(cè)試?yán)敵鲆恍校菏且粋€(gè)實(shí)數(shù)，精確到小數(shù)點(diǎn)后 3位，表示FatMouse最多能換取的JavaBean數(shù)量。輸入樣例537232203251824151510——輸出樣例13.33331。500Author:CHEN,Yue【題目分析】FatMouse用M磅貓食與貓換取它喜愛(ài)的食物 JavaBean。JavaBean存儲(chǔ)在一個(gè)倉(cāng)庫(kù)的 N個(gè)庫(kù)房中，而且每個(gè)庫(kù)房的JavaBean所需要的貓食代價(jià)是不一樣的。以第一組數(shù)據(jù)為例，如下表所示：庫(kù)房號(hào) 1 2 3存儲(chǔ)的JavaBean745所需要的貓食代價(jià)232當(dāng)FatMouse剩余的貓食不夠換取整個(gè)庫(kù)房的 JavaBean時(shí)，可以按比例換取。題目要求貓能夠換取盡可能多的 JavaBean?！舅惴ǚ治觥勘绢}采用貪心算法。(1)為了使貓能夠換取盡可能多的貓食， 就要計(jì)算出每個(gè)庫(kù)房的性?xún)r(jià)比， 并按降序排序。定義數(shù)據(jù)結(jié)構(gòu)：structFat{intbean; //存放該庫(kù)房中JavaBeanintfood; //存放換取該庫(kù)房中的JavaBean所需要的貓食代價(jià)doublegood; 〃用貓食換取JavaBean時(shí)的性?xún)r(jià)比}；對(duì)第一組數(shù)