算法分析大型实验报告
题目一 题目二
编号 1005 1007 Jugs 标题 算法 模拟 字符串 Do the Untwist
班 级： 姓 名： 学 号： 指导老师：
2011年8月
ZJUT-1005 Jugs1
Special Judge
Time limit: 1 Seconds Memory limit: 32768K
In the movie \Hard 3\Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug 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 pour 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 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 \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 integers: 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 which 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 \should be no empty lines nor any trailing spaces.
Sample Input
3 5 4 5 7 3
Sample Output
1
浙江大学，Turing Cup 2001，http://acm.zju.edu.cn/show_problem.php?pid=1005
fill B pour B A empty A pour B A fill B pour B A success fill A pour A B fill A pour A B empty B pour A B success 【全文翻译】
在电影“虎胆龙威3-纽约大劫案”中，布鲁斯·威利斯和杰里米·艾恩斯遇到这样一个难题：给他们一个3加仑水壶和一个5加仑水壶，要求在5加仑水壶里准确装入4加仑的水。真是个难题呢。
假定两个水壶A和B，供水量不限。可以使用三种方法装水： （1） 给一个水壶装水； （2） 把一个水壶倒空；
（3） 从一个水壶倒进另一个水壶。 当从一个水壶倒进另一个水壶时，如果第一个水壶倒空，或者第二个水壶装满就不能再倒了。例如，一个水壶A是5加仑和另一个水壶B是6加仑，水量是8加仑，则从水壶A倒进水壶B时，让水壶B充满水而水壶A剩3加仑水。
问题由3个参数：Ca，Cb和N，分别表示水壶A和B的容量，目标水量N。解决问题的目标是，给出一系列倒水的步骤，使水壶B中的水量恰好是N。
“pour A B”，表示将水从水壶A倒进水壶B；“success”表示目标已经完成。 我们假定每个输入都有一个解决方案。 输入
输入有多行，每行都是一个难题。每个难题有三个正整数：Ca，Cb和N。假设0 输出 输出是由一系列倒水操作构成的，其目标是实现水壶B中有N加仑的水。最后一行是“success”；从第1列开始输出，行末没有空格。 【算法分析】 本题是“Special Judge”，即答案不是唯一的，在服务器端有专门的程序负责判题。 本题属于著名的“倒水问题”。在题目中已经介绍了“倒水”的规则：水是取之不尽的，可以把一个水壶全部灌满（原先是完全空的），或者把一个水壶全部倒空，或者从一个水壶倒进另一个水壶（当然不能溢出）。 题目中给出了三项假定： (1) 只有两个水壶。 实现起来是方便的：我们可以从水壶A或者水壶B开始灌满水，将水壶A的水倒进水 壶B，反之亦然。这会导致很多方案，因为题目是“Special Judge”，所以只要是正确的方案应该都是可行的。 (2) 对每个输入，都有一个确定的输出。 是不是有不可行的情况呢？如果两只水壶的容积分别是2和6，而要倒出容积为3的水量是不可行的。显然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 A pour A B fill A pour A B empty B pour A B fill A pour A B success 虽然灌水的过程与样本输出不一样，但服务器端会有专门的程序进行正确的评判。 【程序代码】 程序名称： 题目： 提交语言： 运行时间： 运行内存： zju1006.cpp Jugs C++ 10ms 836KB #include int main() { int ca,cb,n; while (cin>>ca>>cb>>n) { int bnow; int b = 0; while (b != n) { //只要b水壶不溢出，就让a水壶灌个够 for (int i=0; i<=(cb-b)/ca; i++) { cout<<\ cout<<\ bnow = b+ca*(i+1); //b水壶现在的容量 if (bnow == n) break; } if (bnow == n) break; //退出while循环 cout<<\ } //最后一次灌满b水壶时，a水壶剩下的容量 int a; a = ca-(cb-b)ê; cout<<\ //a水壶剩余的部分倒入b水壶中 b = a; if (b==n) break; } cout<<\ } return 0; 【分析提高】 如果水壶的数量多于两个，倒起来肯定要麻烦得多。在百度中输入“灌水定理”，会搜索到相关的信息，例如：http://club.learning.sohu.com/read-self_study-65528-0-2.html。 ZJUT1007-Do the Untwist2 Time limit: 1 Seconds Memory limit: 32768K Cryptography 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; 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 plaincode 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 (representing 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 plaincode to an encrypted code in ciphercode according to the following formula: for all i from 0 to n - 1, ciphercode[i] = (plaincode[ki 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 '%' operator 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 following: 2 浙江大学，Turing Cup 2001，http://acm.zju.edu.cn/show_problem.php?pid=1006