Wow es increíble como mas o menos cada 2 años respondo esta misma pregunta.
La primera vez (2010):
http://www.forosdelweb.com/f130/calc...lletes-847438/
La segunda vez (2012):
http://www.forosdelweb.com/f130/ejer...exacta-975293/
Y ahora 2014.
Lo único es que mi solución solo funciona para denominaciones enteras, indistintamente si son billetes o monedas.
Para el problema de los centavos. Se me ocurren 2 soluciones.
Solución 1:
Divide el problema en 2 uno para la parte entera y otro para la parte flotante (los centavos). Si lo haces bien, puedes reutilizar la parte de entera para los centavos.
Solución 2:
Convierte tu cantidad a entero multiplicando por 10 y haciendo los cambios correspondientes en las denominaciones.
Algunas observaciones:
1. Originalmente este problema lo resolví intentando simular un cajero. Así que por eso no manejo el concepto de monedas o billetes. Solo denominaciones.
2. La solución que usas es greedy y no optima en caso de querer el mínimo numero de billetes y monedas para hacer un monto dado sobre un conjunto de denominaciones arbitrarias. Aun así para este tipo de denominación parece que todo el tiempo obtienes resultados óptimos. Más información aquí
http://en.wikipedia.org/wiki/Change-making_problem
3. Retomando el punto uno, intente simular ese comportamiento porque estaba resolviendo problemas en uva judge online y project euler, cuando era estudiante. *spoiler* si los pude resolver.
http://uva.onlinejudge.org/index.php...em&problem=615 http://uva.onlinejudge.org/index.php...em&problem=102 https://projecteuler.net/index.php?s...problems&id=31
4. Existen divisas en las que las cantidades son siempre enteras, como el Yen de Japón (JPY). O incluso existen divisas donde tu algoritmo no arrojara una solución no es optima.
TL;DR
Adapta este código.
Código Python:
Ver original# Introducir datos a la variable.
N = int(raw_input('Ingresar Capital: '))
# Variables Billetes.
denominaciones = [500, 200, 100, 50, 20, 10, 5, 2, 1]
for denominacion in denominaciones:
print "%d Billetes de %d" % ((N / denominacion), denominacion)
N = N % denominacion
PD: Acabo de adaptar el código de arriba. A python 3 usando decimals.
Código Python:
Ver originalfrom decimal import Decimal
# Introducir datos a la variable.
N = Decimal(input('Ingresar Capital: '))
# Variables Billetes.
denominaciones = map(Decimal, [500, 200, 100, 50, 20, 10, 5, 2, 1, '.5', '.2', '.1'])
for denominacion in denominaciones:
print("%d Billetes o monedas de %.2f" % ((N // denominacion), denominacion))
N %= denominacion