倒 水

题目：

有两个容器，容积分别为A升和B升，有无限多的水，现在需要C升水。

我们还有一个足够大的水缸，足够容纳C升水。起初它是空的，我们只能往水缸里倒入水，而不能倒出。

可以进行的操作是：

1. 把一个容器灌满；
2. 把一个容器清空（容器里剩余的水全部倒掉，或者倒入水缸）；
3. 用一个容器的水倒入另外一个容器，直到倒出水的容器空或者倒入水的容器满。

输入：三个整数A, B, C，其中 0 < A , B, C <= 1000000000

输出：0或1，表示能否达到要求。

思考：

    开始看到这个问题的时候，没有想到欧几里德算法，之前只是稍微听说过这个算法，故而开始没用这个算法。

两个容器的水倒蹬，最终凑够C升水。于是就考虑一下几种情况：

1. 当容器1或容器2有一个的水量等于C,则程序运行结束，得到结果--true。

2. 当容器1的水量等于容器2的水量且不等于C，则没有得到结果-false。

3. 当容器1的水量，容器2的水量，C，三者互不相等的时候：

• 如果容器1和容器2能够得到1升的水，则不论C是多少，都能得到C升水。
  
• 如果容器1，2的余数，如果C能整除这个余数，则为true，否则是false。

测试了几组数据（3， 4， 5；  3， 5， 6；  3， 5， 7），提交之后，错误。

于是接着思考。

突然看到如果是3， 5， 7这组测试数据的话，3， 5的余数是2，7不能整除2，于是得到false。但是仔细分析一下，

发现如果把容器2的5升水导入容器1（原来是空的），则容器2剩下2升水，然后把容器1倒掉，把容器2的2升水倒入容器1，

再把容器1灌满导入容器1中1升水，然后把容器1倒掉，在从容器2把容器1灌满，则此时容器2剩下1升水。

此时又得到了”神奇的1升水”，则不管C是多少都能得到，返回true。

接着想我的思考错在哪里。想了几分钟，得到一个结论；虽然求得了容器1和容器2的余数，但是没有得到“最小的那个值”，

也就是二者的最大公约数。

于是伟大的欧几里德粉墨登场！（突然发现欧洲的这些数学家真牛逼！）

欧几里德算法在百度百科里讲的很详细，不再赘述。求两个数的最大公约数就是一个递归调用。

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

最后的思路就是：

求出容器1(a)和容器2(b)的最大公约数，然后用c对这个公约数取模，如果是0的返回true，否则返回false。

代码：

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static boolean can(int a,int b,int c) {
		int res = mod(a, b);
		if(c%res == 0){
			return true;
		}else{
			return false;
		}
	
    }
	
	public static int mod(int a, int b){
		if(a % b == 0){
			return b;
		}else{
			return mod(b, a%b);
		}
	}
    
     //start 提示：自动阅卷起始唯一标识，请勿删除或增加。 
     public static void main(String args[]) 
    { 
		System.out.println(can(3, 5, 7));

    } 
    //end //提示：自动阅卷结束唯一标识，请勿删除或增加。
}

英雄会-----倒水-----欧几里德算法

原文：http://blog.csdn.net/crazy1235/article/details/18964001