Java 中的水壶问题

17 Mar 2025 | 5 分钟阅读

水壶问题是 Java 中一个非常重要的问题。水壶问题是指我们有两个水壶，分别是“i”升水壶和“j”升水壶（0 < i < j）。两个水壶最初都是空的，并且没有刻度可以测量小容量。现在，我们需要使用这两个水壶测量出 d 升水，其中 d < j。我们使用以下三个操作来测量小容量的水：

倒空一个水壶。
装满一个水壶
我们从一个水壶向另一个水壶倒水，直到其中一个水壶装满或倒空为止。

在 Java 中，我们实现逻辑以获得测量 d 升水所需的最小操作次数。

解决 Java 中的水壶问题有多种方法，包括 GCD、BFS 和 DP。在本节中，我们将实现使用 GCD 解决水壶问题的逻辑。

WaterJugProblemExample.java

// import required classes and packages if any
import java.io.*;
import java.util.Scanner;
// create class WaterJugProblemExample to solve water jug problem in Java
class WaterJugProblemExample {

	//create function getGCD() that returns GCD of 'x' and 'y'.
	public static int getGCD(int x, int y) {
		if (y == 0) {
			return x;
		}
		
		return getGCD(y, x % y);
	}

	/* create method pourWater() that accept three parameters, i.e., fromCapacity, toCapacity and d*/
	/*fromCapacity is the capacity of the jug from which water is poured, toCapacity is the capacity of the jug to which water is poured, and ltr is the amount of water to be measured */
	public static int pourWater(int fromCapacity, int toCapacity, int d) {
	
		// declare and initialize variables which indicate the current amount of water in source and destination jugs
		int fromCap = fromCapacity;
		int toCap = 0;

		// declare and initialize variable 'reqStep' that will help us to fill from jug
		int reqStep = 1;

		// use while loop to fill d ltr amount and break it when one of the two jugs has d liter amount
		while (fromCap != d && toCap != d) {
		
			// find maximum amount of water which we can pour
			int maxPaur = Math.min(fromCap, toCapacity - toCap);

			// we pour "maxPaur" liters water from "fromCap" to "toCap"
			toCap = toCap + maxPaur;
			fromCap = fromCap - maxPaur;

			// increment the value of reqStep
			reqStep++;
			
			// check whether "fromCap" or "toCap" has d liters of water
			if (fromCap == d || toCap == d)
				break;

			// We fill the first jug when it becomes empty
			if (fromCap == 0) {
				fromCap = fromCapacity;
				reqStep++;
			}

			// we empty the second jug when it becomes full
			if (toCap == toCapacity) {
				toCap = 0;
				reqStep++;
			}
		}
		// return total number of required steps
		return reqStep;
	}

	// create findMisSteps() method that will returns minimum steps needed for messuring d liter
	public static int findMinSteps(int i, int j, int d) {
	
		if (i > j) {	
			int temp = i;
			i = j;
			j = i;
		}

		// we can't messure the water using the jugs if d > n
		if (d > j) {
			return -1;	// we return -1 in this case
		}
		// We cannot solve the water jug problem when gcd of j and i is not possible to divide by d
		if ((d % getGCD(j, i)) != 0)
			return -1;	// we return -1 in this case

		// if the above two conditions are not matched, it return following two cases:
		// x) Water of j liter jug is poured into i liter jug
		// y) Vice versa of "x"
		return Math.min(pourWater(j, i, d), // j to i
				pourWater(i, j, d)); // i to j
	}

	// main() method
	public static void main(String[] args) {
		
		// initialize variables for the size of jugs and amount of water which we want to measure
		int i, j, d;
		
		// create Scanner class object to take input from user
		Scanner sc = new Scanner(System.in);
		
		System.out.println("Enter the size of Jug1 in liters");
		i = sc.nextInt();
		
		System.out.println("Enter the size of Jug2 in liters");
		j = sc.nextInt();
		
		System.out.println("Enter the amount of water which you want to messure:");
		d = sc.nextInt();
		
		// close Scanner class object
		sc.close();
		
		System.out.println("Minimum number of steps required to messure water is " + findMinSteps(i, j, d));
	}
}

输出

我们还可以使用另一种方法来解决水壶问题，其代码实现如下：

WaterJugProblemExample1.java

// import required classes and packages if any
import java.util.*;
// create class WaterJugProblemExample1 to solve Water Jug problem
class WaterJugProblemExample1{
	// main() method start
    public static void main(String sap[]){
    	// create Scanner class object to take input from user
    	Scanner scan = new Scanner(System.in);

    	// tank1 is the capacity of the small tank
    	System.out.print("Enter value for Tank1, i.e., odd capacity of small tank: ");
    	int tank1 = scan.nextInt();

    	// tank2 is the capacity of the large tank
    	System.out.print("\nEnter value for Tank2, i.e., odd capacity of large tank: ");
    	int tank2 = scan.nextInt();
    	
    	scan.close();

    	// initialize variable count that defines number of iterations
    	int count = tank1 + tank2;

    	/* jug1 and jug2 are the arrays that would hold the values for smaller larger tank */
    	int jug1[] = new int[count];
    	int jug2[] = new int[count];

    	int j = 0;

    	// initialize jug1[0] and jug2[0] with tank1 and 0 respectively
    	jug1[j] = tank1;
    	jug2[j] = 0;
    	j++;

    	// initialize jug1[1] and jug2[1] with 0 and tank1
    	jug1[j] = 0;
    	jug2[j] = tank1;
    	j++;

	    while(j < count){
	          if(jug1[ j - 1 ] > 0){
	               // jug1 is not empty when it has any amount of water
	               jug1[j] = jug1[ j - 1 ];
	               jug2[j] = 0;
	          } else{
	               // when jug1 is empty
	               jug1[j] = tank1;
	               jug2[j] = jug2[ j - 1 ];
	          }
	          j++;
	
	          if(jug2[ j - 1 ] > 0){
	               // jug2 is not empty when it has any amount of water
	               if(jug1[ j - 1 ] + jug2[ j - 1 ] < tank2){
	                     // final result
	                     jug2[j] = jug1[ j - 1 ] + jug2[ j - 1 ];
	                     jug1[j] = 0;
	               } else{
	            	   int temp = jug2[ j - 1 ];
	            	   temp = tank2 - temp;
	            	   jug2[j] = temp + jug2[ j - 1 ];
	 
	            	   jug1[j] = jug1[ j - 1 ] - temp;
	               }
	          }
	          else{
	               // when jug2 is empty
	               jug2[j] = jug1[ j - 1 ];
	               jug1[j] = 0; 
	         }
	         j++;
	    }
	    // show final result
	    for(j = 0; j<count; j++){
	    	System.out.print("\nJug1: " + jug1[j] + "\tJug2: " + jug2[j]);
	    }
	    System.out.println();
    }
}

输出

下一主题Java 中的电费账单程序

Java 中的水壶问题

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的水壶问题

相关帖子

Java 中的注解如何工作

Java 中 IntSummaryStatistics getMin() 方法及示例

Java StrictMath Class

Java Program to Determine Whether a Given String of Parentheses (Single Type) is Properly Nested

Java 中的 F

Singleton Class in Java

Java 中的方法嵌套

Java 中的直线数

Java 中的质因数分解程序

Java 并发数组

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器