[算法]两个量杯倒水问题

soloforce

一个很大家熟悉的题目：
有两个量杯，一个容量5升，另一个容量3升; 还有无穷多的自来水（不过，请节约用水，这是美德）。问题是：现在仅依靠两个量杯通过倒水的方式量出4升水来（量杯里头的水可以自由倒进倒出）。

脑筋快的点人不到30秒就可以想到答案。其实我还发现，5升、3升的量杯可以量出 1~5 间的任意整数升水（1升，2升，...，5升）。另外，我还发现如果把量杯换成8升和5升，其它条件保持不变，也能量出1~8整数升的水。

推广到一般情况：换成 M 升 和 N 升（ M>N ，且M、N同时为自然数）的两个量杯呢？ :ask
显然未必能量出1~M升的水。不过其中的规律如何，大家说说看

soloforce

记得还有另外一个版本：引进第三个量杯，容量与前两者又不同; 增加的题设条件是水只能在量杯之间倒来倒去，不允许倒到外面去。

Iambitious

具体的问题，可以参考zoj1005或poj1606(the same)。
http://acm.zju.edu.cn/show_problem.php?pid=1005
http://acm.pku.edu.cn/JudgeOnline/problem?id=1606
这个问题有很强的规律性。

Iambitious

命题：对于所有最大公因数为1 的A,B，都能产生任意的1～max(A,B)之间的容量，反之则不成立。
证明如下：
先证明一个需要用到的数论中的定理
如果a,b为任意整数，但不全为0，那么a,b的最大公约数为满足s = ax+by （x,y 为任意整数）的最小的正整数s。
证明如下：令s = ax + by (x,y为任意整数)的最小正整数，令q=floor(a/s),那么有如下等式：

2. a mod s = a - qs
3.          = a - q(ax + by)
4.          = a(1 - px) + b(-qy)

复制代码

可见a mod s的值也是a与b的线性组合，但a mod s < s所以a mod s只能为0,　同理b mod s也为0,所以s为a,b的公约数,所以有gcd(a,b) >= s;但是，因为s = ax + by并且有(ax + by)能被gcd(a,b)整除:

2. 因为a,b的最大公约数为gcd(a,b),所以有
3. a = p*gcd(a,b);
4. b = q*gcd(a,b);
5. ax+by = x*p*gcd(a,b)+y*q*gcd(a,b)
6.        = (x*p+y*q)*gcd(a, b)
7. 也就是gcd(a,b)|(ax+by)

复制代码

所以有gcd(a,b) <= s所以s = gcd(a,b),此命题得证。
下面证明初始命题：
因为A,B互素（也就是最大公约数为1)所以gcd(A,B) = 1,那么根据上面的定理，有存在整数x,y使得gcd(A,B) = Ax + By ,且最小，也就是说gcd(A,B)是满足整数个A,与整数个B的和的最小正整数值，这里我们很清楚的看到，整数个A,整数个B的和肯定是一个为正一个为负（对于本题来说），设A为正，B为负，那么也就是说通过把x桶A，放到y桶B中，就可以得到gcd(A,B)的容量，而这正是通过操作可以达到的最小容量，如果此容量不为1，那么１是无论如何都不可能出现的，而只要产生了1，那么自然可以产生任意的容量。所以原命题的证。
（至于具体操作的办法，不难了吧,如果想明白了，那么就做做zoj1005吧）

Iambitious

最近又做了一道与此结论相关的题目，比较不错，贴出来大家看看。

2. PROBLEM STATEMENT
3. We want to be able to express a fraction as a sum of two fractions that have
4. small denominators.
5. Specifically, given a fraction a/b, we want to find fractions c/d and e/f such
6. that
7.     a/b = c/d + e/f,  where d and f are positive   
8.     max(d,f) is as small as possible
9.    
10. Create a class FracSum that contains a method decompose that is given a and b
11. and that returns
12. the smallest value for max(d,f).
15. DEFINITION
16. Class:FracSum
17. Method:decompose
18. Parameters:int, int
19. Returns:int
20. Method signature:int decompose(int a, int b)
23. CONSTRAINTS
24. -a and b will each be between 1 and 2,000,000,000, inclusive.
27. EXAMPLES
29. 0)
30. 14
31. 10
33. Returns: 5
37.       14/10 = 0/1 + 7/5  is one way to keep the denominators less than or
38. equal to 5.
42. 1)
43. 1
44. 60
46. Returns: 12
50.        1/60 = -2/5 + 5/12
52. 2)
53. 8
54. 90
56. Returns: 9
60.       8/90 = -4/5 + 8/9

复制代码

topcoder tccc06 algorithm online elimination round 2b 500

wcm130267

我先想想!!!!!

i18n

不知道把两个杯倾斜，倒出一半算不算答案，呵呵

谋杀太阳

Post by Lolita
记得还有另外一个版本：引进第三个量杯，容量与前两者又不同; 增加的题设条件是水只能在量杯之间倒来倒去，不允许倒到外面去。

......觉得只需另另外一个成为容器就好了啊

allenjobs

呵呵，这个板块改为算法与ACM／ICPC板块好了，我是西电的ACMer，过来看到这些好亲切，嘿嘿，我现在使用很有争议的suse，学习中。。。。。。