El rompecabezas de las dos jarras de agua

Estás al lado del río. Te dan una jarra de m litros y una jarra de n litros donde 0 < m < n . Ambas jarras están inicialmente vacías. Las jarras no tienen marcas para permitir medir cantidades más pequeñas. Tienes que usar las jarras para medir d litros de agua donde d < n. Determinar el número mínimo de operaciones a realizar para obtener d litros de agua en una de garrafa. 
Las operaciones que puede realizar son: 

  1. vaciar una jarra
  2. llenar una jarra
  3. Vierta agua de una jarra a la otra hasta que una de las jarras esté vacía o llena.

Hay varias formas de resolver este problema, incluidos BFS y DP. En este artículo, se discute un enfoque aritmético para resolver el problema. El problema se puede modelar por medio de la ecuación diofántica de la forma mx + ny = d que es resoluble si y sólo si mcd(m, n) divide a d. Además, la solución x,y para la cual se satisface la ecuación se puede dar usando el algoritmo de Euclides extendido para MCD
Por ejemplo, si tenemos una jarra J1 de 5 litros (n = 5) y otra jarra J2 de 3 litros (m = 3) y con ellas tenemos que medir 1 litro de agua. La ecuación asociada será 5n + 3m = 1. En primer lugar este problema se puede resolver ya que mcd(3,5) = 1 que divide a 1 (Ver estopara una explicación detallada). Usando el algoritmo de Euclid extendido, obtenemos valores de n y m para los cuales se cumple la ecuación, que son n = 2 y m = -3. Estos valores de n, m también tienen algún significado como aquí n = 2 y m = -3 significa que tenemos que llenar J1 dos veces y vaciar J2 tres veces. 
Ahora, para encontrar el número mínimo de operaciones a realizar, tenemos que decidir qué jarra se debe llenar primero. Dependiendo de qué jarra se elija para llenar y cuál para vaciar tenemos dos soluciones diferentes y la mínima entre ellas sería nuestra respuesta.

Solución 1 (Vierta siempre de una jarra de m litros a una jarra de n litros) 

  1. Llene la jarra de m litros y vacíela en la jarra de n litros.
  2. Siempre que la jarra de m litros se vacíe, llénela.
  3. Cada vez que la jarra de n litros se llene, vacíela.
  4. Repita los pasos 1,2,3 hasta que la jarra de n litros o la jarra de m litros contenga d litros de agua.

Cada uno de los pasos 1, 2 y 3 se cuentan como una operación que realizamos. Digamos que el algoritmo 1 logra la tarea en C1 no de operaciones.

Solución 2 (Vierta siempre de una jarra de n litros a una jarra de m litros)  

  1. Llene la jarra de n litros y vacíela en la jarra de m litros.
  2. Cada vez que se vacíe la jarra de n litros, llénela.
  3. Siempre que la jarra de m litros se llene, vacíela.
  4. Repita los pasos 1, 2 y 3 hasta que la jarra de n litros o la jarra de m litros contengan d litros de agua.

Digamos que la solución 2 logra la tarea en C2 no de operaciones.
Ahora nuestra solución final será un mínimo de C1 y C2.
Ahora ilustramos cómo funcionan ambas soluciones. Supongamos que hay una jarra de 3 litros y una jarra de 5 litros para medir 4 litros de agua, por lo que m = 3, n = 5 y d = 4 . La ecuación diofántica asociada será 3m + 5n = 4. Usamos el par (x, y) para representar las cantidades de agua dentro de la jarra de 3 litros y la jarra de 5 litros respectivamente en cada paso de vertido.

Usando la Solución 1, los pasos de vertido sucesivos son: 

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

Por lo tanto, el número de operaciones que debe realizar es 8.

Usando la Solución 2, los pasos de vertido sucesivos son:  

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

Por lo tanto, el número de operaciones que debe realizar es 6.
Por lo tanto, usaríamos la solución 2 para medir 4 litros de agua en 6 operaciones o movimientos. 

Basado en la explicación aquí está la implementación. 

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

C#

// C# program to implement
// the above approach
using System;
 
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()
{
    int n = 3, m = 5, d = 4;
  
    Console.Write("Minimum number of " +
                       "steps required is " +
                       minSteps(m, n, d));
}
}
 
// This code is contributed by code_hunt.

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) {
 
        // To make sure that m is smaller than n
        if (m > n) {
            var 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
     
        var n = 3, m = 5, d = 4;
 
        document.write("Minimum number of "
        + "steps required is " + minSteps(m, n, d));
 
// This code contributed by Rajput-Ji
 
</script>

Producción:

Minimum number of steps required is 6

Complejidad de tiempo: O(N + M)
Espacio auxiliar: O(1)  Otra explicación detallada : http://web.mit.edu/neboat/Public/6.042/numbertheory1.pdf  

Este artículo es una contribución de Madhur Modi. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *