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