Dados dos garrafones con capacidad máxima de m y n litros respectivamente. Las jarras no tienen marcas que puedan ayudarnos a medir cantidades más pequeñas. La tarea es medir d litros de agua usando estos dos cántaros. Por lo tanto, nuestro objetivo es llegar desde el estado inicial (m, n) al estado final (0, d) o (d, 0).
Ejemplos:
Entrada: 4 3 2
Salida: (0, 0) –> (4, 0) –> (4, 3) –> (0, 3) –> (3, 0) –> (3, 3) –> ( 4, 2) –> (0, 2)Entrada: 5 2 4
Salida: (0, 0) –> (5, 0) –> (5, 2) –> (0, 2) –> (2, 0) –> (2, 2) –> ( 4, 0)
Enfoque: un enfoque que usa BFS se ha discutido en la publicación anterior . En esta publicación se ha discutido un enfoque que utiliza la memorización y la recursividad . En cualquier momento, puede haber un total de seis posibilidades:
- Vaciar completamente la primera jarra
- Vacíe completamente la segunda jarra.
- Llena la primera jarra
- Llena la segunda jarra
- Llene el agua de la segunda jarra en la primera jarra hasta que la primera jarra esté llena o la segunda jarra no tenga agua.
- Llene el agua de la primera jarra en la segunda jarra hasta que la segunda jarra esté llena o la primera jarra no tenga agua.
Enfoque : utilizando Recursion , visite los seis movimientos posibles uno por uno hasta que uno de ellos devuelva True. Dado que puede haber repeticiones de las mismas llamadas recursivas, por lo tanto, cada valor de retorno se almacena utilizando la memorización para evitar llamar a la función recursiva nuevamente y devolver el valor almacenado.
A continuación se muestra la implementación del enfoque anterior:
# This function is used to initialize the
# dictionary elements with a default value.
from collections import defaultdict
# jug1 and jug2 contain the value
# for max capacity in respective jugs
# and aim is the amount of water to be measured.
jug1, jug2, aim = 4, 3, 2
# Initialize dictionary with
# default value as false.
visited = defaultdict(lambda: False)
# Recursive function which prints the
# intermediate steps to reach the final
# solution and return boolean value
# (True if solution is possible, otherwise False).
# amt1 and amt2 are the amount of water present
# in both jugs at a certain point of time.
def waterJugSolver(amt1, amt2):
# Checks for our goal and
# returns true if achieved.
if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0):
print(amt1, amt2)
return True
# Checks if we have already visited the
# combination or not. If not, then it proceeds further.
if visited[(amt1, amt2)] == False:
print(amt1, amt2)
# Changes the boolean value of
# the combination as it is visited.
visited[(amt1, amt2)] = True
# Check for all the 6 possibilities and
# see if a solution is found in any one of them.
return (waterJugSolver(0, amt2) or
waterJugSolver(amt1, 0) or
waterJugSolver(jug1, amt2) or
waterJugSolver(amt1, jug2) or
waterJugSolver(amt1 + min(amt2, (jug1-amt1)),
amt2 - min(amt2, (jug1-amt1))) or
waterJugSolver(amt1 - min(amt1, (jug2-amt2)),
amt2 + min(amt1, (jug2-amt2))))
# Return False if the combination is
# already visited to avoid repetition otherwise
# recursion will enter an infinite loop.
else:
return False
print("Steps: ")
# Call the function and pass the
# initial amount of water present in both jugs.
waterJugSolver(0, 0)
Steps: 0 0 4 0 4 3 0 3 3 0 3 3 4 2 0 2
Complejidad temporal : O(M * N)
Espacio auxiliar : O(M * N)
Publicación traducida automáticamente
Artículo escrito por rituraj_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA