Skip to content

Coleccionando monedas

by en 20/01/2014

¡Hola a todos!

¡Ya está aquí el acertijo programable de la semana! Esta vez vamos a confesaros nuestra afición por coleccionar monedas de países extranjeros. Cuando viajamos, nos gusta volvernos a casa con monedas de todos los tipos posibles del país en el que hemos estado, de modo que siempre tratamos de conseguirlas todas.

Lo normal es que cuando se compra algo y te tienen que dar el cambio, lo hagan intentando darte el mínimo número de monedas posibles. ¡Eso es así en todos los países! Por ejemplo, pensando en las monedas que tenemos en la zona Euro, si nos tuvieran que devolver 3’88 euros, nos intentarían primero dar la moneda más grande posible, la de dos euros. Luego repetirían la misma operación con los 1’88 euros restantes, y nos darían una moneda de 1 euro, una de 50 céntimos… y así hasta darnos todo el dinero, siempre intentando usar la moneda más alta posible, sin pasarse, del cambio que aún no nos hayan devuelto. En el caso del ejemplo, nos devolverían las monedas:

2 € + 1 € + 50 ¢ + 20 ¢ + 10 ¢ + 5 ¢ + 2 ¢ + 1 ¢ = 3’88 euros

Monedas de la zona Euro

Con esto ¡¡conseguiríamos todos los tipos de moneda disponibles en la zona Euro!!

En nuestros viajes, nos hemos encontrado con sistemas monetarios de lo más extraño, con monedas con unos valores como mínimo, muy originales. ¡Eso las hace todavía más valiosas para los coleccionistas! En un remoto país nos encontramos que los valores de sus monedas eran de 1, 2, 4, 8, 16 y 32. Allí, también fuimos capaces de conseguir que nos dieran, tras una única compra, todos los tipos de moneda del país. En concreto, hicimos una compra en la que tuvieron que devolvernos 63 (¡nos costó mucho afinar tanto!) y así les obligamos a que nos dieran los 6 tipos de moneda existentes.

En otros casos no nos fue posible. En un determinado país oriental, tenían monedas con los valores 1, 3, 6, 8, 15 y 20. Después de mucho pensarlo, no fuimos capaces de encontrar ningún cambio en el que consiguiéramos que el tendero nos devolviera más de 4 tipos de monedas diferentes. Por ejemplo, en el afán universal de ahorrar monedas, si nos tuvieran que devolver 32 lo harían con 20 + 8 + 3 + 1; para devolvernos 39 usarían 20 + 15 + 3 + 1. Pero no parece haber ninguna forma de conseguir que nos den más de 4 tipos de monedas diferentes.

La pregunta que os hacemos hoy es ¿cuál es el máximo número de monedas distintas que podemos conseguir en un solo cambio en los países con las siguientes monedas? Recuerda que siempre nos dan el cambio intentando minimizar el número de monedas, y para eso nos dan siempre las más altas posibles:

  • 1, 2, 4, 8, 15
  • 1, 2, 3, 6, 12, 24, 48
  • 1, 5, 9, 17, 25, 33, 42, 100

No os preocupéis de decirnos qué cambio necesitamos conseguir… eso ya lo sacamos nosotros. Sólo queremos el máximo número de monedas de tipos distintos que podemos conseguir tras una sola compra.

Si das con la solución, la programas y quieres probarla, puedes hacerlo aquí.

¡Hasta el domingo!

Anuncios
6 comentarios
  1. David permalink

    4 monedas en el primer caso con 29u.m. (hay múltiples soluciones)
    6 monedas en el segundo con 95 u.m. (o 94)
    5 monedas para el último con 157 u.m. (en el caso de que haya entendido bien el enunciado..)

    salu2, voy a seguir con cisco… =/

  2. hola k ase permalink

    valor = 0
    total = 0
    monedes = [1, 5, 9,34,39,42, 100]
    num = len(monedes)
    for i in range(num):
    if i < num-1:
    if valor + monedes[i] < monedes[i+1]:
    valor += monedes[i]
    total += 1
    print(monedes[i])
    elif i == num-1:
    valor += monedes[i+1]
    total += 1
    print(monedes[i])
    else:
    valor += monedes[i]
    total += 1
    print(monedes[i])
    print(valor,total)

    • Gracias por tu respuesta!

      Por desgracia, el código ha perdido los espacios/tabuladores iniciales al copiarlo en el comentario y para probarlo hay que reconstruirlo. No sé si se debe a que lo he tabulado mal o a que tienes algún problema, pero me salta un error en la última moneda; sospecho que debería ser valor += monedas[i] (y no i+1) tras el primer elif. Además, el caso else realmente sobra, ¿no?

      Un truco. Para resolver más cómodamente este problema es útil añadir una última moneda “fantasma” con un valor muy alto, de manera que estemos seguros de que la suma de todas las monedas anteriores será siempre menor que la última falsa añadida a mano. Luego en el for recorres todas las monedas salvo la última falsa, y así la última de verdad no necesita el caso especial, sino que será incluida siempre. Con esto se puede resolver el problema con un único if (sin caso else) dentro del for.

      • hola k ase permalink

        si eso también lo había pensado pero lo que quería hacer es mostrar las monedas que te dará en el cambio de esta manera sabemos la cantidad de monedas y las monedas que no devuelve, por lo demás creo que el código va bien, pensaba que pegando el código se quedaría bien pero por lo que veo no XD, así que aquí te lo dejo :
        http://www.codeskulptor.org/#user28_CipmFS5nUu_1.py

      • Hola,

        Vale, viendo el código había asignado los else a los ifs que no eran; bien puesto sí funciona bien.

        En cualquier caso, poniendo la moneda fantasma puedes seguir mostrando el valor de las monedas que te devolverían. Básicamente es usar tu código y:

        • Añadir la moneda falsa de valor mayor que la suma de todas las de verdad.
        • Hacer que el for vaya hasta num-1 (para no procesar la moneda falsa).
        • Dejar únicamente el if valor + monedes[i] < monedes[i+1] y su caso “sí”. Todo lo demás no se necesita.

        O sea (usando tu mismo código):


        valor = 0
        total = 0
        monedes = [1, 5, 9,34,39,42, 100, 1000]
        num = len(monedes)
        for i in range(num-1):
          if valor + monedes[i] < monedes[i+1]:
            valor += monedes[i]
            total += 1
            print(monedes[i])

        print(valor,total)

  3. hola k ase permalink

    perdón: quería decir la cantidad de monedas y el valor de las monedas que nos devuelve

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: