Algoritmia básica (AB) » monedas

Un par de anotaciones sobre el problema del cambio en monedas

Javier Campos — Tue, 14 Feb 2017 14:57:28 +0000

Sobre la corrección del algoritmo voraz para el problema del cambio en monedas

Javier Campos — Thu, 11 Feb 2016 12:18:20 +0000

Como vimos ayer en clase, el algoritmo voraz para devolver una cantidad de dinero con el menor número posible de monedas es correcto (es decir, calcula el número mínimo de monedas) para los sistemas de monedas “habituales”, como el del Euro o el Dólar, que suelen denominarse sistemas canónicos de monedas.

Sin embargo, en general, el voraz no es un algoritmo correcto, no calcula el valor mínimo (ejemplo de monedas marcianas).

Aquí podéis acceder (sólo desde la red de Unizar, o desde vuestra casa usando https://vpn.unizar.es) a un artículo reciente que estudia el sistema de monedas que se requiere para que el algoritmo voraz sea correcto (ojo, no es fácil de leer porque, como ocurre con la mayoría de trabajos de investigación, requiere cierta experiencia en el tema):

Xuan Cai: “Canonical Coin Systems for CHANGE-MAKING Problems“. Proceedings of the Ninth International Conference on Hybrid Intelligent Systems, pp. 499–504. Shenyang, China, August 12-14, 2009.

El problema de las monedas marcianas

Javier Campos — Thu, 20 Dec 2012 12:07:16 +0000

Los sistemas monetarios terrícolas suelen ser de tipo canónico. Eso significa que dada una cantidad de dinero a devolver, el algoritmo voraz que consiste en elegir primero la moneda de mayor valor posible que sea menor o igual que la cantidad a devolver, y aplicar el mismo algoritmo a la cantidad restante, iterativamente, nos da el mínimo número de monedas con el que podemos devolver la cantidad.

Contrariamente a lo que la mayoría de la gente piensa, en Marte hay vida inteligente. Tienen una sociedad altamente desarrollada, pero un curioso sistema monetario. Tienen monedas y billetes, como nosotros. El billete más pequeño es el papelín. Y sus monedas tienen cinco denominaciones. La más pequeña es la china, y un papelín vale 100 chinas. El resto de monedas son:

1 guijarro = 3 chinas
1 piedra = 11 chinas
1 pedrusco = 22 chinas
1 menhir = 47 chinas

Monedero marciano con chinas, guijarros y piedras

Por ejemplo, el mínimo número de monedas con valor igual a un papelín es cuatro: dos menhires y dos guijarros.

La entrada del problema consiste en una o más líneas. Cada línea contiene el precio de un artículo en chinas, comprendido entre 1 y 100, ambos incluidos. Para cada artículo el programa debe escribir una línea que describa el mínimo número de monedas necesarias para devolver el cambio, si se paga el artículo con un papelín.

Ejemplo de entrada:

77
34
99
57
13

Ejemplo de salida:

0 menhires, 1 pedrusco, 0 piedras, 0 guijarros, 1 china
0 menhires, 3 pedruscos, 0 piedras, 0 guijarros, 0 chinas
0 menhires, 0 pedruscos, 0 piedras, 0 guijarros, 1 china
0 menhires, 1 pedrusco, 1 piedra, 3 guijarros, 1 china
1 menhir, 1 pedrusco, 1 piedra, 2 guijarros, 1 china

Marciano arruinado

Fuente: aquí (fuente “desaparecida”; accesible en la waybackmachine)