本文共 2351 字，大约阅读时间需要 7 分钟。

水壶分水问题

问题描述： 给你两壶容量的X和Y升。有无限量的水供应。你需要确定它是否可以准确的使用这两个水壶测量出Z升水。

输入样例: x = 3, y = 5, z = 4

输入样例: x = 2, y = 6, z = 5

算法设计：

package com.bean.algorithmbasic;public class WaterAndJugProblem {
       /*     * 给你两壶容量的X和Y升。有无限量的水供应。你需要确定它是否可以准确的使用这两个水壶测量出Z升水。     * 如果z升的水是可测量的，你必须在一个或两个桶内含有z升的水。     * 允许操作：     * 给任意一个水壶装满水     * 清空任何一个水壶的水     * 把水从一个水壶倒到另一个水壶里，直到另一个水壶完全装满，或者第一个水壶本身是空的。     *      * 输入样例: x = 3, y = 5, z = 4     * 输出结果: True     *      * 输入样例: x = 2, y = 6, z = 5     * 输出结果: False     * */    /*     * 算法设计一:     * *///  public static boolean canMeasureWater(int x, int y, int z) {
   //        if(x + y < z) return false;//        if( x == z || y == z || x + y == z ) return true; //        return z%gcd(x, y) == 0;//      } //      //  public static int gcd(int a, int b){
   //        if(b == 0) return a;//        return gcd(b, a % b);//      }    public static void swap(int x, int y) {        int temp=x;        x=y;        y=temp;    }    /*     * 算法设计二:     * 1、如果水壶X的容量等于Z，或者水壶Y的容量等于Z，或者水壶X+水壶Y的容量等于Z，则返回true；     * 2、如果水壶Y中当前水的容量等于Z，或者水壶X中当前水的容量+水壶Y中当前水的容量等于Z，则返回true；     *   （因为假设水壶Y的容量大，使用尝试用水壶Y尽可能多装水。）     * 3、     *      *      * */    public static boolean canMeasureWater(int x, int y, int z) {        //假设水壶Y的容量大于水壶X        if (x > y) swap(x, y);        if (x == z || y == z || x + y == z) return true;   //specific cases        int currX = x;   //current water amount in smaller jug        int currY = x;   //current water amount in larger jug        if (x != 0 && y != 0) {            while (true) {                //如果当前水壶Y的水量等于Z或者 当前水壶X和Y的水量之和等于Z，则返回true                if (currY == z || currX + currY == z) return true;                if (y - currY == currX) break;                else if (y - currY > currX) {                    currY = currY + currX;                    currX = x;                }                else {                    currX = currX - (y - currY);                    currY = 0;                }            }        }        return false;    }    public static void main(String[] args) {        // TODO Auto-generated method stub        boolean flag=canMeasureWater(3,5,4);        //boolean flag=canMeasureWater(2,6,5);        System.out.println(flag);    }}

（完）

转载地址：http://bgvdi.baihongyu.com/