Convertir monedas y billetes en Python

Reto: Conversión de monedas y billetes

Dada una cantidad de dinero indicar cuantos billetes y monedas de cada tipo son necesarios como mínmo.

• Método 1
• Método 2

Dado un cierto importe en euros deseamos conocer el mínimo número de monedas y billetes necesarios para alcanzar esa cifra. Disponemos de una lista con los tipos de billetes y monedas existentes, desde el billete de 500 € hasta la moneda de un céntimo (0,01 €). Son quince tipos de elementos entre billetes y monedas los que tenemos en la zona euro.

El procedimiento utilizado se basa en calcular un cociente entre la cifra inicial disponible en euros  y 500 que es el billete más grande. La parte entera nos dará el número de billetes de 500 € necesarios, y el resto se usará como denominador en la siguiente división. La segunda división se realiza dividiendo entre 200 que es el siguiente billete. La parte entera nos dará el número de billetes de 200 € necesarios y el resto se convertirá en el numerador de la siguiente división. Este proceso se sigue reiteradamente hasta llegar a la moneda más pequeña que es la de un céntimo.

Método 1

Definimos la lista T que contiene los quince tipos de billetes y monedas existentes en la zona euro. Inicializamos la lista S con quince ceros. Esta lista contendrá la salida obtenida indicando en cada uno de sus elementos el número de billetes y monedas necesarios de cada tipo para llegar a cubrir la cifra dada en euros y conseguir que sean mínimas las monedas y billetes utilizados. La lista S es la solución al caso práctico planteado.
Generamos aleatoriamente x que es la cifra en euros que vamos a descomponer. Utilizamos random.randint que únicamente nos permite generar números aleatorios enteros entre un par de ellos dados como argumentos. Si bien nosotros precisamos que la cifra en euros tenga dos decimales. Para ello, usamos un pequeño truco que consiste en dividir entre 100 el valor obtenido. De esta forma, lo que obtendremos para x son valores entre 1.000,00 € y 3.000,00 €.
En el algoritmo el primer paso usa x como numerador del cociente que iremos realizando reiteradamente, pero luego el numerador será el resto obtenido en el paso previo. Esto hace que tengamos que definir el primer resto como resto=x.

Nos metemos en un bucle for que recorre quince valores entre 0 y 14. Dentro del bucle usamos la función divmod que utiliza como argumentos el numerador y el denominador, y que devuelve dos valores que son la parte entera y el resto. Se podría haber obtenido el mismo resultado usando la división entera en Python (//) y el cálculo del módulo(%). Imprimimos S[i] que contiene el número de monedas y billetes necesarios del tipo T[i]. Al recorrer el bucle los quince elementos de estas listas lo que obtendremos por pantalla es un listado con todos los billetes y monedas necesarios de cada tipo para alcanzar la cifra inicial de x euros.

Finalmente lo que hacemos es comprobar que todos esos billetes y monedas multiplicados por el valor en euros de cada uno de los tipos resulte igual a la cifra x inicial. El último elemento a imprimir (total==x) es una condición que nos indicará con True si coinciden el total obtenido multiplicando y sumando los diferentes valores con el importe x inicial.

import random
T=[500,200,100,50,20,10,5,2,1,.5,.2,.1,.05,.02,.01]
S=[0]*15 #salida por tipo de billete y moneda
x=random.randint(100000,300000)/100
resto=x
print('Disponemos de',x,'euros.')
print('Se pueden descomponer en:')
for i in range(len(T)):
  S[i], resto = divmod(round(resto,6), T[i])
  print(int(round(S[i],4)),'de',T[i],'€')
print('Comprobación')
total=0
for i in range(len(T)):
  total+=S[i]*T[i]
total=round(total,6)
print(total,total==x)

Método 2

En este caso disponemos de la lista C de quince posiciones que contendrán el número de billetes y monedas disponibles inicialmente de cada tipo, que se generan de forma aleatoria. Esta composición de billetes y monedas, a priori no será óptima y lo que pretendemos es encontrar la composición dada por la lista de salida S que nos proporcione el número mínimo de monedas y billetes necesarios.

Dada la lista C vamos a calcular que importe total en euros supone este dinero. Para ello vamos a emplear dos procedimientos que luego podremos ver que coinciden.

• El primer procedimiento requiere definir la variable suma que inicializamos con el valor cero. Nos metemos en un bucle for que recorrerá los quince elementos de la lista. Vamos calculando cada elemento C[i] de forma aleatoria y vamos obteniendo la suma acumulada multiplicando cada elemento i-ésimo de las listas T y C. De esta forma hemos obtenido el dinero inicialmente disponible que queda recogido en la variable suma.
• El segundo procedimiento es mucho más sintético y no necesita definir la variable suma y no necesita hacer uso del bucle for anterior. Directamente podemos calcular x de forma condensada en una sola línea con la expresión sum([a * b for a, b in zip(T,C)]) que equivale a la función sumaproducto de Excel.

Una vez conocido el importe de los x euros lo primero que hacemos es usar un bucle for para mostrar en pantalla su composición según las diferentes monedas y billetes disponibles inicialmente, imprimiendo C[i] y T[i].

Luego imprimimos por pantalla la frase que indica nuestra intención es cambiar esas monedas y billetes por otra composición que sea mínima. Siguiendo la imagen, se puede ver la frase que dice 'Los 2692.38 € se pueden descomponer en:'. En esta frase el importe que se cita coincide con el que se muestra inicialmente, e ilustran los dos procedimientos vistos anteriormente. La primera cifra es x y la segunda es la variable suma.

El resto del algoritmo es igual que el del método anterior, salvo que al final no hacemos la comprobación que se hizo en el método 1, y que en este caso lo que hacemos es ver de cuántos billetes y monedas iniciales hemos partido y a cuantos hemos llegado. En general, se podrá apreciar una significativa reducción.

import random
T=[500,200,100,50,20,10,5,2,1,.5,.2,.1,.05,.02,.01]
C=[0]*15 #caja disponible
S=[0]*15 #salida por tipo de billete y moneda
suma=0
for i in range(15):
  C[i]=random.randint(0,5)
  suma+=T[i]*C[i]
x=sum([a * b for a, b in zip(T,C)]) #sumaproducto
print('Disponemos de',round(x,6),'euros.')
print('Están compuestos por:')
for i in range(len(T)):
  print(C[i],'de',T[i],'€')
print('Queremos cambiarlos por los mínimos billetes y monedas posibles.')
print('Los',round(suma,6),'€ se pueden descomponer en:')
resto=x
for i in range(len(T)):
  S[i], resto = divmod(round(resto,6), T[i])
  print(int(round(S[i],4)),'de',T[i],'€')
print('Teníamos',sum(C),'billestes y monedas','y los hemos reducido a',int(sum(S)))