Tres bucles anidados para ralentizar el rendimiento

Question

Me preguntaba si hay otra forma de resolver esta pregunta sin usar 3 anidados para bucles como lo hice aquí. Soy consciente de que los bucles de anidamiento de esta manera probablemente causarán muchos problemas si el método se prueba en una lista lo suficientemente grande.

Esta es la pregunta:

from typing import List

def can_pay_with_three_coins(denoms: List[int], amount: int) -> bool:
    """Return True if and only if it is possible to form amount, which is a
    number of cents, using exactly three coins, which can be of any of the
    denominations in denoms.

    >>> can_pay_with_three_coins([1, 5, 10, 25], 36)
    True
    >>> can_pay_with_three_coins([1, 5, 10, 25], 37)
    False

    """

Esta es mi solución:

for i in range(len(denoms)):
    one_coin = denoms[i]
    for j in range(len(denoms)):
        another_coin = denoms[j]
        for k in range(len(denoms)):
            last_coin = denoms[k]
            if one_coin + another_coin + last_coin == amount:
                return True
return False

Estoy seguro de que hay otra forma de abordar este problema, es que realmente no puedo pensar en ello.
¡Gracias por cualquier ayuda!

python performance

2

Flavio Esposito 13 dic. 2019 a las 22:54

Answer 1

Ok, hagamos trampa con itertools :)

import itertools
from typing import List


def can_pay_with_three_coins(denoms: List[int], amount: int) -> bool:
    """Return True if and only if it is possible to form amount, which is a
    number of cents, using exactly three coins, which can be of any of the
    denominations in denoms.

    >>> can_pay_with_three_coins([1, 5, 10, 25], 36)
    True
    >>> can_pay_with_three_coins([1, 5, 10, 25], 37)
    False

    """

    for variant in itertools.permutations(denoms, len(denoms)):
        if sum(variant[:3]) == amount:
            return True

    return False


print(can_pay_with_three_coins([1, 5, 10, 25], 36))
print(can_pay_with_three_coins([1, 5, 10, 25], 37))
print(can_pay_with_three_coins([1, 1, 5, 10, 25], 37))
print(can_pay_with_three_coins([1, 3, 5, 10, 25], 37))
print(can_pay_with_three_coins([20, 20, 20, 50], 60))

Salida

True
False
False
False
True

1

Alexandr Shurigin 13 dic. 2019 a las 20:43

Answer 2

Esta es una famosa pregunta llamada 3 sum.

La complejidad temporal de esta solución es O (n ^ 3), puede implementar un algoritmo de O (n ^ 2) que se explica e implementa en varios idiomas en el siguiente enlace:

Encuentra un triplete que sume a un valor dado

4

MohammadMahdi Eilbeigi 13 dic. 2019 a las 20:14

Tres bucles anidados para ralentizar el rendimiento

2 respuestas

Preguntas relacionadas

Nuevas preguntas

python