算法分析与设计大型实验报告样本.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 3-gallon 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 integer

6、s: 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 whic

7、h 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 Afi

8、ll 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列开始输出，行末没有空格。【算法分析】本题是“Special

10、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虽然灌水的过程与样本输出不一样，但服务器端会有专门的程序进行正确的评判。【程序代码】程序名称：z

12、ju1006.cpp题目：Jugs提交语言：C+运行时间：10ms运行内存：836KB#include using namespace std;int main() int ca,cb,n; while (cincacbn) int bnow; int b = 0; while (b != n) /只要b水壶不溢出，就让a水壶灌个够for (int i=0; i=(cb-b)/ca; i+) coutfill Aendl; coutpour A Bendl; bnow = b+ca*(i+1);/b水壶现在的容量 if (bnow = n) break; if (bnow = n) break

13、;/退出while循环 coutempty Bendl; /最后一次灌满b水壶时，a水壶剩下的容量 int a;a = ca-(cb-b)%ca;coutpour A Bendl; /a水壶剩余的部分倒入b水壶中b = a; if (b=n) break; coutsuccessendl; return 0; 【分析提高】如果水壶的数量多于两个，倒起来肯定要麻烦得多。在百度中输入“灌水定理”，会搜索到相关的信息，例如：ZJUT1007-Do the Untwist浙江大学，Turing Cup 2001，Time limit: 1 Seconds Memory limit: 32768KCry

14、ptography deals with methods of secret communication that transform a message (the plaintext) into a disguised form (the ciphertext) so that no one seeing the ciphertext will be able to figure out the plaintext except the intended recipient. Transforming the plaintext to the ciphertext is encryption

15、; transforming the ciphertext to the plaintext is decryption. Twisting is a simple encryption method that requires that the sender and recipient both agree on a secret key k, which is a positive integer. The twisting method uses four arrays: plaintext and ciphertext are arrays of characters, and pla

16、incode and ciphercode are arrays of integers. All arrays are of length n, where n is the length of the message to be encrypted. Arrays are origin zero, so the elements are numbered from 0 to n - 1. For this problem all messages will contain only lowercase letters, the period, and the underscore (rep

17、resenting a space). The message to be encrypted is stored in plaintext. Given a key k, the encryption method works as follows. First convert the letters in plaintext to integer codes in plaincode according to the following rule: _ = 0, a = 1, b = 2, ., z = 26, and . = 27. Next, convert each code in

18、plaincode to an encrypted code in ciphercode according to the following formula: for all i from 0 to n - 1, ciphercodei = (plaincodeki mod n - i) mod 28.(Here x mod y is the positive remainder when x is divided by y. For example, 3 mod 7 = 3, 22 mod 8 = 6, and -1 mod 28 = 27. You can use the C % ope

19、rator or Pascal mod operator to compute this as long as you add y if the result is negative.) Finally, convert the codes in ciphercode back to letters in ciphertext according to the rule listed above. The final twisted message is in ciphertext. Twisting the message cat using the key 5 yields the fol

20、lowing: Array012plaintextcatplaincode3120ciphercode31927ciphertextcs.Your task is to write a program that can untwist messages, i.e., convert the ciphertext back to the original plaintext given the key k. For example, given the key 5 and ciphertext cs., your program must output the plaintext cat. Th

21、e input file contains one or more test cases, followed by a line containing only the number 0 that signals the end of the file. Each test case is on a line by itself and consists of the key k, a space, and then a twisted message containing at least one and at most 70 characters. The key k will be a

22、positive integer not greater than 300. For each test case, output the untwisted message on a line by itself. Note: you can assume that untwisting a message always yields a unique result. (For those of you with some knowledge of basic number theory or abstract algebra, this will be the case provided

23、that the greatest common divisor of the key k and length n is 1, which it will be for all test cases.) Example input: 5 cs.101 thqqxw.lui.qswer3 b_ylxmhzjsys.virpbkr0Example output: catthis_is_a_secretbeware._dogs_barking【全文翻译】加密技术是把消息（明文）变换成一种伪装的形式（密文）进行秘密通信的一种方法，除收件人之外，任何人看了密文也不能翻译成明文。把明文变换成密文称为加密

24、，把密文转换成明文称为解密。Twisting(扭曲)是一个简单的加密方法，它需要发送者和接受者都共同认可的加密关键字k，是一个正整数。Twisting方法使用4个数组：plaintext和ciphertext是字符数组，plaincode和ciphercode是整数数组。所有数组的长度为n，这是对信息加密的长度。所有数组初始时为空，下标从0到n-1。消息只包含小写字母，句号和下划线（代表空格）。消息存储在数组plaintext中。给定关键k，加密方法如下：首先把plaintext的字母转换成数字编码存放到数组plaincode中，转换规则：_ = 0，a =1，b =2，z = 26 ，. =

25、 27。然后将存放在数组plaincode中的数字编码按下列公式转换成加密代码存放到数组ciphercode中：i从0到n-1，ciphercodei = (plaincodeki mod n - i) mod 28.（这里mod是模运算，例如，3 mod 7 = 3，22 mod 8 = 6，-1 mod 28 = 27。C语言中使用%运算符，Pascal语言中使用mod运算符）。最后，把存放在ciphercode中的数字编码按上述方法转换成密文存放到数组ciphertext中。你的任务是编写程序，实现消息的untwist（解密），即给定关键字k，将密文恢复至原来的明文。例如，关键字是5，密

26、文是cs.，程序必须输出明文cat。输入文件包含一个或多个测试例，数字0表示输入结束。每个测试例一行：关键字k，空格，然后是密文，密文至少一个字符，最多70个字符。关键k是一个正整数，不超过300。对每个测试例，输出一行解密的明文。注意：你可以假定解密消息的结果是唯一的。【算法分析】本题是属于加密和解密类型的题目，当然加密和解密的方法是比较简单的。题目中给出了加密的过程，要求我们给出解密的结果。分为以下三步：(1) 根据原始密文，计算ciphercode原始密文ciphercodeazASCII值-96，其结果表明为：a1, b2, ., z26_0.27(2) 根据ciphercode，计算

27、plaincode题目中给出了由plaincode计算ciphercode的公式：ciphercodei = (plaincodek* i mod n - i) mod 28现在求plaincode，令t=k*i % n (运算符*比%高一个优先级)，t是密文的坐标转换成明文的坐标，则：plaincodet = (ciphercodei + i) % 28(3) 根据plaincode,计算解密后的明文plaincode解密后的明文值为126时az：1a，2b，26z0_27.以测试数据1为例：密文坐标012密文cs.ciphercode31927转换成明文的坐标t021plaincode32

28、01明文cta【程序代码】程序名称：zju1006.cpp题目：Do the Untwist提交语言：C+运行时间：10ms运行内存：836K#include #include using namespace std;int main() int k; /keychar a80;/原始密文char c80;/解密后的明文 int b100;/ciphercodewhile(cink & k) cina; int n = strlen(a); /根据原始密文,计算ciphercodefor(int i=0; i=a & ai=z) bi = ai-96; else if (ai=_) bi=0;

29、 else bi=27; int d100;/plaincode/根据ciphercode,计算plaincodefor(int i=0; in; i+) int t = k*i % n; dt = (bi+i) % 28;/根据plaincode,计算解密后的明文 for(int i=0; i0 & di27) ci = di+96; else if (di=0) ci=_; else ci=.; /输出解密后的明文for(int i=0; in; i+) coutci; coutendl; return 0; ZJU2109-FatMouse Trade浙江省大学生程序设计竞赛，Sunny

30、 Cup 2004，Time limit: 1 Seconds Memory limit: 32768K FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.The warehouse has N rooms. The i-th room contains Ji pounds of JavaBeans and requires Fi pounds of cat food. FatMous

31、e does not have to trade for all the JavaBeans in the room, instead, he may get Ji* a% pounds of JavaBeans if he pays Fi* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.InputThe input consists of multip

32、le test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers Ji and Fi respectively. The last test case is followed by two -1s. All integers are not greater than 1000.OutputFor each test case, print in a s

33、ingle line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.Sample Input5 37 24 35 220 325 1824 1515 10-1 -1Sample Output13.33331.500Author: CHEN, Yue【全文翻译】FatMouse准备了M磅的猫粮，打算与看守仓库的猫交换食品，仓库里存放着它喜爱的食物JavaBean。仓库有n个库房，库房i存放Ji磅JavaBean，需要F

34、i磅猫粮予以交换。FatMouse不需要交换库房里所有的JavaBean，可以按比例交换。如果它支付Fia%磅的猫粮，就可以换取Jia%磅的JavaBean，其中a是实数。现在明确编程任务：FatMouse最多能换取多少JavaBean。输入输入包含多组测试例！对每个测试例，第一行是两个非负整数M和N。接下来N行，每行两个非负整数Ji和Fi。最后一个测试例是两个1，不需要处理。所有的整数都不超过1000.输出对每个测试例，输出一行：是一个实数，精确到小数点后3位，表示FatMouse最多能换取的JavaBean数量。输入样例5 37 24 35 220 325 1824 1515 10-1 -

35、1输出样例13.33331.500Author: CHEN, Yue【题目分析】FatMouse用M磅猫食与猫换取它喜爱的食物JavaBean。JavaBean存储在一个仓库的N个库房中，而且每个库房的JavaBean所需要的猫食代价是不一样的。以第一组数据为例，如下表所示：库房号123存储的JavaBean745所需要的猫食代价232当FatMouse剩余的猫食不够换取整个库房的JavaBean时，可以按比例换取。题目要求猫能够换取尽可能多的JavaBean。【算法分析】本题采用贪心算法。(1) 为了使猫能够换取尽可能多的猫食，就要计算出每个库房的性价比，并按降序排序。定义数据结构：stru

36、ct Fat int bean;/存放该库房中JavaBeanint food;/存放换取该库房中的JavaBean所需要的猫食代价double good;/用猫食换取JavaBean时的性价比;对第一组数据：存储的JavaBean745所需要的猫食代价232性价比3.50001.33332.5000(2) 按性价比排序。显然，我们应该从性价比最好的库房换取，这就需要按性价比进行降序排序。为了简单起见，这里采用了冒泡排序（仍然没有超时）。希望读者能够采用其它的快速排序方法。(3) 用猫食换取JavaBean。当猫食足够多时，按库房的性价比由高到底换取；当猫食的量不足以换取整个库房的JavaBe

37、an时，则按比例换取。【程序代码】程序名称：zju2109.cpp题目：FatMouse Trade提交语言：C+运行时间：790ms运行内存：848KB#include #include #include using namespace std;struct Fat int bean;/存放该库房中JavaBeanint food;/存放换取该库房中的JavaBean所需要的猫食代价double good;/用猫食换取JavaBean时的性价比;int main() /ifstream cin(ch05-04.in);int m, n;Fat iMouse1001;while(cinmn &

38、 n+1 & m+1)for(int i = 0; i iMousei.beaniMousei.food;iMousei.good = double (iMousei.bean) / iMousei.food;/按性价比进行降序排序（冒泡排序）for(int i = 0; i n - 1; i+)for(int j = i + 1; j n; j+)if (iMousei.good iMousej.good) swap(iMousei, iMousej);/交换两个单元double sum = 0;for (int i=0; i= iMousei.food)sum += iMousei.bean; m -= iMousei.food;else /所剩猫食不多换取一个库房的JavaBean，按比例换取JavaBeansum += iMousei.bean * double(m) / iMousei.food;break;cout.precision(3);coutfixedsumendl;return 0;附录：设计说明书格式(请删除)全部为5号字，单倍行距！中文：宋体；英文：Times New Roman；首行缩进：2字符