¿Por qué al agregar una nota en un problema de recursividad se obtiene un resultado incorrecto, mientras que al eliminar la nota se obtiene la respuesta correcta?
Pregunta. Escribe una función “canSum(target_sum, numbers)” que tome como argumentos un objetivo de suma y una matriz de números. La función debe devolver un booleano que indique si es posible generar el objetivo de suma utilizando los números de la matriz.
- Puedes usar un elemento de la matriz tantas veces como sea necesario. Puedes asumir que todos los números son no negativos.
- Ej: canSum(7, [1, 2, 5, 3, 7]) –> true
- Ej: canSum(7, [2, 4, 9, 6]) –> false
Aquí está mi solución, pero solo funciona cuando elimino la memorización.
def canSum(target_sum, numbers, memo={}):
if target_sum in memo:
return memo[target_sum]
if target_sum == 0:
return True
if target_sum < 0:
return False
for num in numbers:
if canSum(target_sum - num, numbers, memo) == True:
memo[target_sum] = True # eliminar esto da la salida esperada.
return True
memo[target_sum] = False # eliminar esto da la salida esperada.
return False
if __name__ == "__main__":
print(canSum(7, [2, 5, 7])) # Salida: True
print(canSum(7, [2, 4])) # Salida: True (aunque debería ser falso).
Después de eliminar la memorización, ahora funciona correctamente. Por favor ayuda, no puedo encontrar por qué está pasando esto.
for num in numbers:
if canSum(target_sum - num, numbers, memo) == True:
return True
return False
# Ahora funciona bien.
davy.ai
Parece que el problema radica en el uso del diccionario de memorización. Como estás utilizando un objeto mutable (un diccionario), estás creando una única instancia de él en la firma de la función, que reutilizas para todas las llamadas a la función. Esto significa que cuando llamas a la función con un conjunto de números diferente, sigues utilizando el mismo diccionario de memorización, lo cual entra en conflicto con los valores guardados previamente en otras llamadas.
Para solucionar este problema, deberías hacer que el diccionario de memorización sea un parámetro interno de la función, en lugar de un parámetro predeterminado en la firma de la función. Esto creará una nueva instancia del diccionario para cada llamada a la función, lo cual evitará conflictos con los valores guardados previamente. Aquí tienes el código modificado:
Con esta modificación, la función debería funcionar como se espera, aprovechando la memorización.