本文主要是介绍uva571 - Jugs(水壶)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
贴出以为大神的分析。。。。简明易懂
本题只要求给出一个解，不要求最优。所给的两个罐子容量一定互质，因此必然可以倒出从0到大罐容量间的任何整数值。原理是若A，B互质，则最小公倍数为A×B，即不存在一个1 < n < B，使得nA能被B整除。令r = nA mod B(mod为取模操作)，那么当n从0到B-1变化时，r可以取到0到B-1之间的任何值。这个是很容易证明的，但我的证明过程非常不专业，还请各位数学老师给予指教！
现在的问题就是用AB两个罐子相互倒水来模拟这个数学过程。设小罐容量为A，大罐容量为B。每次将A装满后倒入B中。若第m次后B已装满，A剩下的水量为r1，则有：
- r1 = mA mod B
然后将B倒空，把A中剩余的r1装入B。又经过n次从把A装满倒入B的操作后B被装满，此时A剩下的水量为r2，则有：
- r2 = (r1 + nA) mod B
- = (mA mod B + nA) mod B
- = (m+n)A mod B
由此可知，倒的方法就是每次将A中的水倒进B，但每次在做这一步之间要先检查A、B中的水量，如果A为空，就将A装满；如果B已倒满，就将B清空。最后一定可以在某个时候在B罐中得到需要的水量。
代码如下：#include <cstdio>
int ca, cb, c, a, b;
int main ()
{while(~scanf("%d%d%d",&ca,&cb,&c)){a = b = 0;while(b!=c){if(a==0)//a为空，则加满{a = ca;puts("fill A");}if(b==cb)//b若满，则清空{b = 0;puts("empty B");}puts("pour A B");//a倒向bb+=a; a = 0;if(b>cb)//若移除，则收回{a += b-cb;b = cb;}}puts("success");}return 0;
}
这篇关于uva571 - Jugs(水壶)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
