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:
- vaciar una jarra
- llenar una jarra
- 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)
- Llene la jarra de m litros y vacíela en la jarra de n litros.
- Siempre que la jarra de m litros se vacíe, llénela.
- Cada vez que la jarra de n litros se llene, vacíela.
- 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)
- Llene la jarra de n litros y vacíela en la jarra de m litros.
- Cada vez que se vacíe la jarra de n litros, llénela.
- Siempre que la jarra de m litros se llene, vacíela.
- 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