Skip to content

Solución: Coleccionando monedas

by en 26/01/2014

¡Estamos de vuelta!

Para esta semana, os proponíamos un acertijo sobre monedas. En concreto, os preguntábamos cuál es el máximo número de monedas diferentes que nos pueden devolver como máximo en un país en el que tengan monedas con unos determinados valores. Para eso, se debe asumir que el cambio siempre nos lo dan minimizando el número de monedas dadas, es decir dándonos siempre las monedas de mayor valor posible con respecto al cambio que aún está por dar. Os poníamos el ejemplo de un país como el nuestro, en la zona Euro. Con nuestras monedas de 1 y 2 euros, y de 1, 2, 5, 20 y 50 céntimos, podemos conseguir que nos den una moneda de cada tipo si tienen que devolvernos 3’88 euros. Os poníamos algún otro ejemplo más, como un país con monedas de valor 1, 2, 4, 8, 16 y 32, en el que podemos también conseguir todas (con un cambio de 63), o un país con monedas de valor 1, 3, 6, 8, 15 y 20, donde como mucho conseguiremos cuatro monedas diferentes.

Tras esto os preguntábamos varios casos. Empecemos con el primero, monedas con los valores 1, 2, 4, 8, 15. ¿Cómo lo resolvemos?

Una alternativa es analizar cuántas monedas distintas nos darán si nos tienen que devolver 1, 2, 3, 4, 5,… “unidades monetarias” (céntimos, centavos, o lo que sea). Para eso, hay que recordar que el cambio nos lo dan minimizando el número de monedas de tal manera que si nos tienen que dar, por ejemplo, 10 u.m. usarán una moneda de 8 y una de 2. Si os entretenéis haciendo esto, llegaréis a la conclusión, como nos dijo David, de que como mucho podremos conseguir 4 monedas diferentes, por ejemplo si nos tienen que dar como cambio 22 o 29.

La pregunta que asalta usando esta solución es ¿cuándo paramos? Es decir, ¿Cuándo dejamos de mirar cuántas monedas nos tendrían que devolver? Porque, si no lo comprobamos, ¿podemos estar seguros de que, por ejemplo, para devolvernos 1.000.000 u.m. no necesitarán más de 4 monedas diferentes? La pregunta tiene una fácil respuesta: basta con dejar de mirar cuando el número supere la suma de los valores de todas las monedas. Al fin y al cabo, queremos que nos den monedas distintas; no nos sirve de nada conseguir dos monedas de 15 u.m.

Esta reflexión nos lleva a otra pregunta. ¿Hay alguna manera de obtener la respuesta sin mirar en todos esos valores? Es decir, ¿se os ocurre alguna forma de construir el cambio necesario que maximice el número de monedas? Pensad que para saber el número máximo de monedas distintas al fin y al cabo tenemos que haber llegado de alguna forma al cambio que lo consigue (el 22 o el 29 en la solución anterior). Y para eso podemos construir la solución en base a la selección de monedas. Sería algo así: en el cambio más pequeño que maximiza el número de monedas diferentes, ¿me devolverían una moneda de valor 1? ¿Y una moneda de valor 2? ¿Y una de valor 4? Es decir, como decíamos, en lugar de mirar cuántas monedas diferentes nos devolverían con diferentes cambios, construimos ese cambio añadiendo las monedas que nos interesan.

Para eso, usamos un algoritmo voraz, que es una familia de algoritmos que ya ha aparecido en acertijos anteriores (como en éste o éste). En lo que consiste es en ir construyendo la solución (el cambio que devuelve más tipos de monedas) por pasos, y en cada paso decidir si añadimos o no el siguiente tipo de moneda. En concreto, empezamos con la moneda más baja, que siempre es la 1. Si nos tuvieran que dar como cambio 1 u.m., tendrían que usar un nuevo tipo de moneda (pues no han usado ninguna hasta ahora), de modo que la añadimos a nuestra solución y decimos “ante el cambio de 1 u.m., nos devuelven 1 tipo de moneda”.

Ahora nos planteamos si añadir a nuestra solución la siguiente moneda, que tenía un valor de 2 u.m. Si queremos conseguir un cambio en el que nos devuelvan las monedas que ya llevamos y la nueva, tendrían que devolvernos 3 u.m. en total. Antes de añadir la moneda 2 a nuestra solución nos preguntamos si eso es posible. Comprobamos que, efectivamente, para devolvernos 3 u.m. nos tendrían que dar dos monedas diferentes, de manera que ampliamos nuestra solución y decimos “ante el cambio de 3 u.m., nos devuelven 2 tipos de monedas”.

¡Vamos con la siguiente! Su valor era 4 u.m. y nos planteamos añadirla. Eso significaría que nos devolverían 7 u.m. Antes de aceptarla, comprobamos que, efectivamente, para devolvernos 7 u.m. usarían exactamente esos tres tipos de monedas, y vemos que es así, de manera que ¡vamos bien!. “Ante el cambio de 7 u.m., nos devuelven 3 tipos de monedas”.

Nos planteamos añadir la siguiente, de valor 8. Eso significa que nos devolverían 15 u.m. Antes de añadir la moneda 8 a nuestra solución nos planteamos, como siempre, si es buena idea. Y ahora comprobamos que no. Si tuvieran que darnos un cambio de 15 u.m. nos darían la moneda con ese valor, en lugar de darnos las 4 monedas 1+2+4+8. Es decir, en nuestro cambio (de menor valor) que maximiza el número de monedas no puede estar la moneda que vale 8, y nos olvidamos de ella. Fijaos que lo importante aquí es que la suma acumulada (7) más la nueva moneda (8) resulta ser igual (o mayor) que la moneda siguiente (15), y eso es determinante para no añadir la nueva moneda en nuestra solución.

Terminamos añadiendo a nuestra solución “en construcción” la moneda 15 y llegamos a que si nos tienen que devolver 22 u.m. nos darían el máximo de monedas diferentes, 4 (1+2+4+15).

¿Veis la idea del algoritmo? Básicamente consiste en llevar la cuenta del cambio que nos devuelven hasta ahora, el número de monedas que necesitan, y cuál es la siguiente sobre la que tenemos que decidir. Si al sumar el cambio acumulado y la nueva moneda alcanzamos el valor de la moneda siguiente, entonces la nueva no la incluimos.

Veamos qué ocurre con las otras preguntas que os hacíamos. En un país con las monedas 1, 2, 3, 6, 12, 24, 48 incluiríamos en nuestra solución del mínimo cambio con el máximo número de monedas a las monedas 1, 2, 6, 12, 24 y 48 (cambio total 93). La única que hemos dejado fuera es la moneda 3, y por tanto nos han devuelto 6 tipos de monedas. En este caso, nuestro lector David acertó en el número de monedas diferentes, pero no del todo en el cambio necesario, pues dijo 94 o 95 u.m. Fijaos que para devolvernos 94 habrían usado 48 + 24 + 12 + 6 + 2 + 2, y eso son 5 monedas diferentes, no 6. Para devolvernos 95 sí se necesitaría una sexta moneda, la de valor 1 y sí es correcto (aunque la de valor 2 estuviera repetida). En cualquier caso, no es un fallo importante porque el acertijo no preguntaba por el cambio necesario 🙂

La última pregunta era para las monedas 1, 5, 9, 17, 25, 33, 42, 100. En este caso, la respuesta es de 5 monedas, y el menor cambio con el que se consiguen es 1+5+9+42+100=157. David, en este caso, nos lo dijo todo bien. ¡Enhorabuena!

¡Esperamos que os haya gustado! Como siempre, si sabéis programar y queréis practicar un poco, podéis probar vuestra solución aquí. Aunque la explicación sea larga y parezca complicada, ¡es un simple bucle con un condicional dentro!

¡Hasta el próximo!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: