Ver Mensaje Individual
  #2 (permalink)  
Antiguo 22/11/2014, 21:53
Avatar de razpeitia
razpeitia
Moderador
 
Fecha de Ingreso: marzo-2005
Ubicación: Monterrey, México
Mensajes: 7.321
Antigüedad: 17 años, 1 mes
Puntos: 1360
Respuesta: Problema con restos(%)

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
  1. # Introducir datos a la variable.
  2. N = int(raw_input('Ingresar Capital: '))
  3.  
  4. # Variables Billetes.
  5. denominaciones = [500, 200, 100, 50, 20, 10, 5, 2, 1]
  6.  
  7. for denominacion in denominaciones:
  8.     print "%d Billetes de %d" % ((N / denominacion), denominacion)
  9.     N = N % denominacion

PD: Acabo de adaptar el código de arriba. A python 3 usando decimals.
Código Python:
Ver original
  1. from decimal import Decimal
  2. # Introducir datos a la variable.
  3. N = Decimal(input('Ingresar Capital: '))
  4.  
  5. # Variables Billetes.
  6. denominaciones = map(Decimal, [500, 200, 100, 50, 20, 10, 5, 2, 1, '.5', '.2', '.1'])
  7.  
  8. for denominacion in denominaciones:
  9.     print("%d Billetes o monedas de %.2f" % ((N // denominacion), denominacion))
  10.     N %= denominacion

Última edición por razpeitia; 22/11/2014 a las 22:21