Estoy haciendo una calculadora de cambios, una función que toma el costo de un artículo y la cantidad de dinero entregada al cajero, antes de devolver el número de cada tipo de moneda para devolver de manera óptima las monedas mínimas.

Lo hice de la manera simple y sencilla usando las funciones de división de piso y módulo, pero también tenía curiosidad por ampliar mi comprensión de la recursión y definir funciones dentro de las funciones al hacerlo con el siguiente método (imprimir declaraciones para la depuración):

def change_calc_2(cost, given): # input in full £xx.xx
    coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
    coins = [0] * len(coin_vals)

    cost = cost * 100 # pence
    given = given * 100
    left = given - cost

    def _calc(left):

        for i, c in enumerate(coin_vals):
            print("for loop level:", i)
            print("Amount left at start of kernel:", left)
            print("Coin val in question:", c)

            if left == 0:
                return coins # early exit routine

            elif c > left:
                continue

            else:
                coins[i] += 1
                print("coin added:", c)
                left -= c
                print("Amount left at end of kernel:", left)
                _calc(left)

        return coins

    #_calc(left)
    return _calc(left)       
    #return coins

print(change_calc_2(17, 20))

Ejecutar change_calc_2 (x, 20) para x = 18 yx = 19, funciona bien. Los resultados son [1 0 0 0 0 0 0 0] (una sola moneda de £ 2) y [0 1 0 0 0 0 0 0] (una sola moneda de £ 1).

Sin embargo, cuando intento x = 17, y espero [1 1 0 0 0 0 0 0], obtengo [1 2 0 0 0 0 0 0].

La depuración de impresión proporciona lo siguiente:

for loop level: 0
Amount left at start of kernel: 300
Coin val in question: 200
coin added: 200
Amount left at end of kernel: 100   ##### Completion of one round of for loop, as expected
for loop level: 0
Amount left at start of kernel: 100
Coin val in question: 200          ##### Rejects the 200p coin as too big for the amount left
for loop level: 1
Amount left at start of kernel: 100
Coin val in question: 100
coin added: 100                   #### Adds the last coin expected, so 100p + 200p in total
Amount left at end of kernel: 0 
for loop level: 0               
Amount left at start of kernel: 0 ############ <----- Running as expected until here
Coin val in question: 200         ************** <--- Should break just after this point?
for loop level: 2
Amount left at start of kernel: 0
Coin val in question: 50
for loop level: 1
Amount left at start of kernel: 100  ########### <--- Wtf? How has it added on money?
Coin val in question: 100
coin added: 100
Amount left at end of kernel: 0
for loop level: 0
Amount left at start of kernel: 0
Coin val in question: 200
for loop level: 2
Amount left at start of kernel: 0
Coin val in question: 50
[1 2 0 0 0 0 0 0]

Espero que, en los puntos marcados en los registros anteriores, el programa haya dejado = 0 (lo que hace), y luego presione el botón si queda == 0: devolver monedas, luego salga de la instancia de _calc (). Mis pensamientos son que cuando regresa a la instancia principal de _calc (), el padre también golpeará a la izquierda == 0, y volverá a _calc () arriba y así sucesivamente.

Obviamente mi pensamiento es incorrecto, ¡cualquier ayuda es muy apreciada! Tengo la sensación de que se debe a un malentendido de la función de retorno y / o un malentendido de la "localidad" frente a la "globalidad" de las variables

0
qubyt 11 oct. 2019 a las 11:33

3 respuestas

La mejor respuesta

Primero, le diré cómo puede arreglar su código arriba, luego le daré una forma ligeramente mejor de codificar esto, si eso es lo que está buscando.

Cómo solucionarlo

Su error está apareciendo porque su llamada recursiva a _calc editará coins, pero no left. Esto se debe a que dentro de la función _calc, left se ha reemplazado con una variable local.

Agregué algunas sangrías dinámicas "rápidas y sucias" para mostrar cómo funciona esto:

def change_calc_2(cost, given): # input in full £xx.xx
    coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
    coins = [0] * len(coin_vals)

    cost = cost * 100 # pence
    given = given * 100
    left = given - cost

    def _calc(left,recur_level):
        print("{}recursion level:".format(' '*4*recur_level), recur_level)
        for i, c in enumerate(coin_vals):
            print("    {}for loop level:".format(' '*4*recur_level), i)
            print("    {}Amount left at start of kernel:".format(' '*4*recur_level), left)
            print("    {}Coin val in question:".format(' '*4*recur_level), c)

            if left == 0:
                print("{}EXIT recursion level:".format(' '*4*recur_level), recur_level)
                return coins # early exit routine

            elif c > left:
                continue

            else:
                coins[i] += 1
                print("    {}coin added:".format(' '*4*recur_level), c)
                left -= c
                print("    {}Amount left at end of kernel:".format(' '*4*recur_level), left)
                _calc(left,recur_level+1)

        return coins

    #_calc(left)
    return _calc(left,0)       
    #return coins

Si ejecutamos esto rápidamente:

>>> change_calc_2(17,20)
recursion level: 0
    for loop level: 0
    Amount left at start of kernel: 300
    Coin val in question: 200
    coin added: 200
    Amount left at end of kernel: 100      #<----- These values are the same
    recursion level: 1
        for loop level: 0
        Amount left at start of kernel: 100
        Coin val in question: 200
        for loop level: 1
        Amount left at start of kernel: 100
        Coin val in question: 100
        coin added: 100
        Amount left at end of kernel: 0
        recursion level: 2
            for loop level: 0
            Amount left at start of kernel: 0
            Coin val in question: 200
        EXIT recursion level: 2
        for loop level: 2
        Amount left at start of kernel: 0
        Coin val in question: 50
    EXIT recursion level: 1
    for loop level: 1
    Amount left at start of kernel: 100   #<----- These values are the same
    Coin val in question: 100
    coin added: 100
    Amount left at end of kernel: 0
    recursion level: 1
        for loop level: 0
        Amount left at start of kernel: 0
        Coin val in question: 200
    EXIT recursion level: 1
    for loop level: 2
    Amount left at start of kernel: 0
    Coin val in question: 50
EXIT recursion level: 0

Su error impide que su left se actualice correctamente. Si desea utilizar la recursividad, asegúrese de anidar sus llamadas correctamente:

def change_calc_rec(cost, given): # input in full £xx.xx
    coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
    coins = [0] * len(coin_vals)

    cost = cost * 100 # pence
    given = given * 100
    left = given - cost

    def _calc(left,coin_index):
        i = coin_index
        c = coin_vals[i]
        print("{}coin_index:".format(' '*4*i), i)
        while True:
            if left == 0:
                print("{}EXIT recursion level:".format(' '*4*i), i)
                return coins # early exit routine
            elif c > left:
                break
            else:
                coins[i] += 1
                print("    {}coin added:".format(' '*4*i), c)
                left -= c
                print("    {}Amount left at end of kernel:".format(' '*4*i), left)

        if coin_index < len(coin_vals):
            return _calc(left,coin_index+1)
        else:
            return coins

    #_calc(left)
    return _calc(left,0)       
    #return coins

¿Cuál es su nivel de recursión debe ser el mismo que su índice de monedas? Anteriormente, llegaba al índice donde su moneda era más grande que el cambio requerido, luego comenzaba un nuevo bucle con el índice 0. Lo anterior debería solucionarlo.

Sin recursividad

No necesita recurrencia para este problema en absoluto. Puede codificarlo de una manera mucho más segura utilizando un bucle while:

def change_calc(cost, given): # input in full £xx.xx
coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
coins = [0] * len(coin_vals)

cost = cost * 100 # pence
given = given * 100
left = given - cost

for i, c in enumerate(coin_vals):
    while True:
        if left == 0:
            return coins # early exit routine
        elif c > left:
            break
        else:
            coins[i] += 1
            left -= c
raise ValueError('Bad given or cost!')

Esto seguirá ejecutando el bucle while hasta que c > left, luego se mueva a monedas más pequeñas. Regresa cuando left == 0. Eleva un ValueError si le das un valor incorrecto de dado o costo, de modo que left == 0 nunca suceda.

¡Disfrutar!

0
soyapencil 11 oct. 2019 a las 09:13

Está utilizando un bucle for dentro de una función recursiva y la misma condición se evalúa dos veces, es decir.

Este código

        coins[i] += 1
        print("coin added:", c)
        left -= c
        print("Amount left at end of kernel:", left)
        _calc(left)

Será evaluado dentro de la función interna y también dentro de la función externa

Con el mismo valor de índice i=1 en el bucle for for i, c in enumerate(coin_vals):.

En efecto, no necesita la recursión en primer lugar o necesita pasar el índice a la función interna.

0
Albin Paul 11 oct. 2019 a las 08:48
def change_calc_2(cost, given): # input in full £xx.xx
    coin_vals = [200, 100, 50, 20, 10, 5, 2, 1]
    coins = [0] * len(coin_vals)

    cost = cost * 100 # pence
    given = given * 100
    left = given - cost

    def _calc(left):

        for i, c in enumerate(coin_vals):
            print("for loop level:", i)
            print("Amount left at start of kernel:", left)
            print("Coin val in question:", c)

            if left == 0:
                return coins # early exit routine

            elif c > left:
                continue

            else:
                coins[i] += 1
                print("coin added:", c)
                left -= c
                print("Amount left at end of kernel:", left)
                return _calc(left)   #### <----- This was the bug

        return coins

    #_calc(left)
    return _calc(left)       
    #return coins

print(change_calc_2(17, 20))

Tu didn't put the return declaración.
Entonces, su loop continued for the further iterations después de regresar de la llamada de recursión secundaria.

0
Bhawan 11 oct. 2019 a las 08:53
58337270