Головоломка с двумя кувшинами для воды

Опубликовано: 20 Января, 2022

Вы на берегу реки. Вам дается m- литровый кувшин и n- литровый кувшин, где 0 <m <n . Оба кувшина изначально пусты. На кувшинах нет маркировки, позволяющей отмерять меньшее количество. Вы должны использовать кувшины для измерения d литров воды, где d <n. Определите минимальное количество операций, которые необходимо выполнить для получения d литров воды в одной из кувшинов.
Вы можете выполнять следующие операции:

  1. Опустошить кувшин
  2. Наполнить кувшин
  3. Налейте воду из одного кувшина в другой, пока один из кувшинов не станет пустым или полным.
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Есть несколько способов решения этой проблемы, включая BFS и DP. В этой статье обсуждается арифметический подход к решению задачи. Задачу можно смоделировать с помощью диофантова уравнения вида mx + ny = d, которое разрешимо тогда и только тогда, когда gcd (m, n) делит d. Кроме того, решение x, y, для которого выполняется уравнение, может быть получено с использованием расширенного алгоритма Евклида для GCD.
Например, если у нас есть кувшин J1 на 5 литров (n = 5) и другой кувшин J2 на 3 литра (m = 3), и мы должны отмерить 1 литр воды, используя их. Соответствующее уравнение будет 5n + 3m = 1. Прежде всего, эта проблема может быть решена, так как gcd (3,5) = 1, который делит 1 (см. Это для подробного объяснения). Используя расширенный алгоритм Евклида, мы получаем значения n и m, для которых выполняется уравнение: n = 2 и m = -3. Эти значения n, m также имеют некоторое значение, например, здесь n = 2 и m = -3 означает, что мы должны заполнить J1 дважды и пустить J2 трижды.
Теперь, чтобы найти минимальное количество операций, которые необходимо выполнить, нам нужно решить, какой кувшин следует наполнить в первую очередь. В зависимости от того, какой кувшин выбран для наполнения, а какой - опорожниться, у нас есть два разных решения, и наш ответ будет минимальным из них.

Раствор 1 (всегда переливайте из m-литрового кувшина в n-литровый кувшин)

  1. Наполните m-литровый кувшин и вылейте его в n-литровый кувшин.
  2. Когда кувшин станет пустым, наполните его.
  3. Когда n-литровый кувшин становится полным, он опустошается.
  4. Повторите шаги 1,2,3 до тех пор, пока в кувшине объемом n литров или кувшине m литров не будет d литров воды.

Каждый из шагов 1, 2 и 3 считается как одна выполняемая нами операция. Допустим, алгоритм 1 решает задачу за количество операций C1.

Раствор 2 (всегда переливайте из n-литрового кувшина в m-литровый кувшин)

  1. Наполните кувшин емкостью n литров и вылейте его в кувшин емкостью m литров.
  2. Когда кувшин объемом n литров станет пустым, наполните его.
  3. Когда кувшин объемом m литров становится полным, он опустошается.
  4. Повторяйте шаги 1, 2 и 3 до тех пор, пока в кувшине объемом n литров или кувшине m литров не будет d литров воды.

Допустим, решение 2 решает задачу в C2, количество операций.
Теперь наше окончательное решение будет состоять минимум из C1 и C2.
Теперь проиллюстрируем, как работают оба решения. Предположим, что есть кувшин на 3 литра и кувшин на 5 литров для измерения 4 литров воды, поэтому m = 3, n = 5 и d = 4 . Соответствующее диофантово уравнение будет 3m + 5n = 4. Мы используем пары (x, y) для представления количества воды внутри 3-литрового и 5-литрового кувшина соответственно на каждом этапе разлива.

При использовании Решения 1 последовательные этапы заливки:

 (0,0) -> (3,0) -> (0,3) -> (3,3) -> (1,5) -> (1,0) -> (0,1) -> ( 3,1) -> (0,4)

Следовательно, вам нужно выполнить 8 операций.

При использовании Решения 2 последовательные этапы заливки:

 (0,0) -> (0,5) -> (3,2) -> (0,2) -> (2,0) -> (2,5) -> (3,4)

Следовательно, вам нужно выполнить 6 операций.
Следовательно, мы использовали бы раствор 2, чтобы отмерить 4 литра воды за 6 операций или ходов.

Based on the explanation here is the implementation. 

C++

// C++ program to count minimum number of steps
// required to measure d litres water using jugs
// of m liters and n liters capacity.
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to return GCD of "a"
// and "b".
int gcd(int a, int b)
{
    if (b==0)
       return a;
    return gcd(b, a%b);
}
 
/* fromCap -- Capacity of jug from which
              water is poured
   toCap   -- Capacity of jug to which
              water is poured
   d       -- Amount to be measured */
int pour(int fromCap, int toCap, int d)
{
    // Initialize current amount of water
    // in source and destination jugs
    int from = fromCap;
    int to = 0;
 
    // Initialize count of steps required
    int step = 1; // Needed to fill "from" Jug
 
    // Break the loop when either of the two
    // jugs has d litre water
    while (from != d && to != d)
    {
        // Find the maximum amount that can be
        // poured
        int temp = min(from, toCap - to);
 
        // Pour "temp" liters from "from" to "to"
        to   += temp;
        from -= temp;
 
        // Increment count of steps
        step++;
 
        if (from == d || to == d)
            break;
 
        // If first jug becomes empty, fill it
        if (from == 0)
        {
            from = fromCap;
            step++;
        }
 
        // If second jug becomes full, empty it
        if (to == toCap)
        {
            to = 0;
            step++;
        }
    }
    return step;
}
 
// Returns count of minimum steps needed to
// measure d liter
int minSteps(int m, int n, int d)
{
    // To make sure that m is smaller than n
    if (m > n)
        swap(m, n);
 
    // For d > n we cant measure the water
    // using the jugs
    if (d > n)
        return -1;
 
    // If gcd of n and m does not divide d
    // then solution is not possible
    if ((d % gcd(n,m)) != 0)
        return -1;
 
    // Return minimum two cases:
    // a) Water of n liter jug is poured into
    //    m liter jug
    // b) Vice versa of "a"
    return min(pour(n,m,d),   // n to m
               pour(m,n,d));  // m to n
}
 
// Driver code to test above
int main()
{
    int n = 3, m = 5, d = 4;
 
    printf("Minimum number of steps required is %d",
           minSteps(m, n, d));
 
    return 0;
}

Java

// Java program to count minimum number of
// steps required to measure d litres water
// using jugs of m liters and n liters capacity.
import java.io.*;
 
class GFG{
 
// Utility function to return GCD of "a"
// and "b".
public static int gcd(int a, int b)
{
    if (b == 0)
        return a;
         
    return gcd(b, a % b);
}
 
/* fromCap -- Capacity of jug from which
              water is poured
   toCap   -- Capacity of jug to which
              water is poured
   d       -- Amount to be measured */
public static int pour(int fromCap, int toCap,
                       int d)
{
     
    // Initialize current amount of water
    // in source and destination jugs
    int from = fromCap;
    int to = 0;
 
    // Initialize count of steps required
    int step = 1; // Needed to fill "from" Jug
 
    // Break the loop when either of the two
    // jugs has d litre water
    while (from != d && to != d)
    {
         
        // Find the maximum amount that can be
        // poured
        int temp = Math.min(from, toCap - to);
 
        // Pour "temp" liters from "from" to "to"
        to += temp;
        from -= temp;
 
        // Increment count of steps
        step++;
 
        if (from == d || to == d)
            break;
 
        // If first jug becomes empty, fill it
        if (from == 0)
        {
            from = fromCap;
            step++;
        }
 
        // If second jug becomes full, empty it
        if (to == toCap)
        {
            to = 0;
            step++;
        }
    }
    return step;
}
 
// Returns count of minimum steps needed to
// measure d liter
public static int minSteps(int m, int n, int d)
{
     
    // To make sure that m is smaller than n
    if (m > n)
    {
        int t = m;
        m = n;
        n = t;
    }
 
    // For d > n we cant measure the water
    // using the jugs
    if (d > n)
        return -1;
 
    // If gcd of n and m does not divide d
    // then solution is not possible
    if ((d % gcd(n, m)) != 0)
        return -1;
 
    // Return minimum two cases:
    // a) Water of n liter jug is poured into
    //    m liter jug
    // b) Vice versa of "a"
    return Math.min(pour(n, m, d), // n to m
                    pour(m, n, d)); // m to n
}
 
// Driver code
public static void main(String[] args)
{
    int n = 3, m = 5, d = 4;
 
    System.out.println("Minimum number of " +
                       "steps required is " +
                       minSteps(m, n, d));
}
}
 
// This code is contributed by RohitOberoi

Python3

# Python3 implementation of program to count
# minimum number of steps required to measure
# d litre water using jugs of m liters and n
# liters capacity.
def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)
 
 
""" fromCap -- Capacity of jug from which
              water is poured
   toCap   -- Capacity of jug to which
              water is poured
   d       -- Amount to be measured """
def Pour(toJugCap, fromJugCap, d):
 
 
    # Initialize current amount of water
    # in source and destination jugs
    fromJug = fromJugCap
    toJug  = 0
 
    # Initialize steps required
    step = 1
    while ((fromJug  is not d) and (toJug is not d)):
 
         
        # Find the maximum amount that can be
        # poured
        temp = min(fromJug, toJugCap-toJug)
 
        # Pour "temp" liter from "fromJug" to "toJug"
        toJug = toJug + temp
        fromJug = fromJug - temp
 
        step =  step + 1
        if ((fromJug == d) or (toJug == d)):
            break
 
        # If first jug becomes empty, fill it
        if fromJug == 0:
            fromJug = fromJugCap
            step =  step + 1
 
        # If second jug becomes full, empty it
        if toJug == toJugCap:
            toJug = 0
            step =  step + 1
             
    return step
 
# Returns count of minimum steps needed to
# measure d liter
def minSteps(n, m, d):
    if m> n:
        temp = m
        m = n
        n = temp
         
    if (d%(gcd(n,m)) is not 0):
        return -1
     
    # Return minimum two cases:
    # a) Water of n liter jug is poured into
    #    m liter jug
    return(min(Pour(n,m,d), Pour(m,n,d)))
 
# Driver code
if __name__ == "__main__":
 
    n = 3
    m = 5
    d = 4
 
    print("Minimum number of steps required is",
                              minSteps(n, m, d))
     
# This code is contributed by Sanket Badhe

Javascript

<script>
 
// Javascript program to count minimum number of
// steps required to measure d litres water
// using jugs of m liters and n liters capacity.
 
    // Utility function to return GCD of "a"
    // and "b".
    function gcd(a , b) {
        if (b == 0)
            return a;
 
        return gcd(b, a % b);
    }
 
    /*
     fromCap -- Capacity of jug from which
     water is poured toCap -- Capacity of
      jug to which water is poured
      d -- Amount to be measured
     */
    function pour(fromCap , toCap , d)
    {
 
        // Initialize current amount of water
        // in source and destination jugs
        var from = fromCap;
        var to = 0;
 
        // Initialize count of steps required
        var step = 1; // Needed to fill "from" Jug
 
        // Break the loop when either of the two
        // jugs has d litre water
        while (from != d && to != d) {
 
            // Find the maximum amount that can be
            // poured
            var temp = Math.min(from, toCap - to);
 
            // Pour "temp" liters from "from" to "to"
            to += temp;
            from -= temp;
 
            // Increment count of steps
            step++;
 
            if (from == d || to == d)
                break;
 
            // If first jug becomes empty, fill it
            if (from == 0) {
                from = fromCap;
                step++;
            }
 
            // If second jug becomes full, empty it
            if (to == toCap) {
                to = 0;
                step++;
            }
        }
        return step;
    }
 
    // Returns count of minimum steps needed to
    // measure d liter
    function minSteps(m , n , d) {
 
&
Алгоритмы

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Наихудший, средний и лучший анализ алгоритмов
4 Января, 2023
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Что такое логарифмическая временная сложность? Полное руководство
12 Декабря, 2022
Amazon SDE Sheet: вопросы и ответы на собеседовании
12 Декабря, 2022