Anuncio

Colapsar
No hay ningún anuncio todavía.

Monedas optimas

Colapsar
X
 
  • Filtro
  • Hora
  • Mostrar
Borrar todo
nuevos mensajes

  • Monedas optimas

    Hola a todos.

    Los que tenemos una cierta edad, recordaremos las pesetas. En particular las denominaciones de las monedas, que eran de una peseta, cinco pesetas (un duro), veinticinco pesetas, cincuenta pesetas, y más adelante la de 100 pesetas.

    Este sistema, era poco racional, en el sentido de que se necesitaban muchas monedas para formar una cantidad determinada. Por ejemplo, cuatro monedas para fijar cuatro pesetas, 6 monedas para tener 14 pesetas.

    Posteriormente, con el euro se puso un sistema más racional. Fijandonos solo en los céntimos, tenemos monedas de 1,2,5,10,20,50, .Con estas divisiones, es posible hacer combinaciones de cualquier cantidad con, relativamente, pocas monedas.

    A partir de esto, dejadme que os plasntee dos problemas: Uno más fácil y otro más dificil.

    El fácil: Con las denominaciones actuales (1,2,5,10,20,50), Dadas N (con N desde 1 hasta 6) monedas, de cualquier denominación (repetidas o no), cuál es la máxima cantidad M tal que podemos conseguir todas las cantidades desde 1 hasta M, usando un máximo de N monedas.

    Un ejemplo: Con N=1, M sale 2. Con N=2, M sale 7.

    El dificil: Como podemos modificar las denominaciones actuales (es decir, si por ejemplo cambiamos la moneda de 10 centimos por una de 17 centimos) , para conseguir que la cantidad M descrita anteriormente sea lo mayor posible, para cada N


    Un saludo

  • #2
    Re: Monedas optimas

    Bonito problema ,
    Contenido oculto


    Vamos por el fácil

    con denominaciones 1,2,5,10,20,50 tenemos la máxima suma para
    N maxima suma
    1 2
    2 7
    3 17
    4 37
    5 87
    6 137

    El dificil


    con N=1 monedas el máximo sería lograble es 6 con denominaciones 1,2,3,4,5,6, pero intuyo que el problema pasa por usar una única denominación y lograr lo que mas se puede en cada N

    esto se me hace que se encara por " investigación operativa, una serie de ecuaciones lineales, con una función objetivo a maximizar, aun no veo como...le seguire dando vueltas

    para N=2 intuí la serie de fibonacci, pero encontre una combinación que dio mejor

    mis intentos hasta ahora pero no desisto ... lo posteo para que sepas que demuestro interes en resolverlo, pero aun ni idea de como encontrar el maximo


    N denominaciones maxima suma no se forma
    1 1,2,3,4,5,6 6 7
    2 1,2,3,5,8,13 11 12
    2' 1,2,3,4,7,11 15 16
    2'' 1,2,3,7,11,15 18 19
    3 1,2,4,10,13,16 18 19
    4 1,5,9,13,17,21 24 25
    5 1,6,11,16,21,26 30 31
    6 1,7,13,19,25,31 36 37

    Comentario


    • #3
      Re: Monedas optimas

      Hola. R3, gracias por participar. Una pista para el problema difícil.
      Contenido oculto

      Yo lo enfoco de forma iterativa.

      - Si tenemos una moneda, de una denominación, es obvio que esa moneda debe ser de 1.

      - Si tenemos dos monedas, de dos denominaciones, la primera debe ser 1 por lo anterior.

      Con solo la moneda de 1, puedo conseguir hasta M=2 (1, 1+1), con lo que la siguiente denominación debe ser, como máximo 3. Esto me permite, con 2 monedas, tener hasta M=4 (1, 1+1, 3, 3+1).

      Sin embargo, también podría hacer que la segunda moneda fuera 2, y también llegaría hasta M=4 (1, 2, 1+2, 2+2).

      - Si tenemos tres monedas, parto de los casos anteriores, a partir de ellos llego a que la siguiente moneda, como máximo, debe ser 5. Con ello, veo los dos casos anteriores, y me quedo con el que llegue a un M más alto.

      A ver si tu solución, para 6 monedas, o para un numero arbitrario de ellas, te sale como a mí. Es una serie muy curiosa.

      Comentario


      • #4
        Re: Monedas optimas

        Hola carroza
        Contenido oculto


        mi solución para el problema difícil es que la denominación debe ser 1,2,5,13,34,89

        con ello el máximo alcanzable es


        N Denominaciones Máxima suma
        1 1,2,5,13,34,89 2
        2 1,2,5,13,34,89 7
        3 1,2,5,13,34,89 20
        4 1,2,5,13,34,89 54
        5 1,2,5,13,34,89 143
        6 1,2,5,13,34,89 232

        La regla para las máximas sumas para cada N con su denominación



        y la regla para las denominaciones




        una tabla con las siguientes denominaciones y las maximas sumas si se permiten mas denominaciones

        N Denom Max Suma
        1 1 2
        2 2 7
        3 5 20
        4 13 54
        5 34 143
        6 89 376(*)
        7 233 986
        8 610 2583
        9 1597 6764
        10 4181 17710
        11 10946 46367
        12 28657 121392
        13 75025 317810
        14 196418 832039
        15 514229 2178308
        16 1346269 5702886
        17 3524578 14930351
        18 9227465 39088168

        * ese valor se alcanza si se puede contar con la siguiente denominación de monedas N=7 y solo usar 6
        Última edición por Richard R Richard; 01/11/2018, 01:57:56.

        Comentario


        • #5
          Re: Monedas optimas

          Perfecto r3.

          A qué te suena la secuencia de valores de las monedas?

          Comentario


          • #6
            Re: Monedas optimas

            Se me hacia difícil reconocerla por la falta del 8, pero es

            Contenido oculto

            Es una serie de fibonacci, para todos los n impares es decir si es la serie de Fibonacci=1,1,2,3,5,8,13,21,34,55,89,etc

            la solucion es

            Saludos

            Comentario


            • #7
              Re: Monedas optimas

              Perfecto. Y, a qué te suena la serie de los valores de las máximas sumas obtenidas?

              Un saludo

              Comentario


              • #8
                Re: Monedas optimas

                Contenido oculto
                Las denominaciones responden a una serie de fibonacci, para todos los n impares


                Y la de las sumas es
                Vale la pena aclarar que los valores de la serie se alcanzan si se dispone siempre de una de una moneda con la denominación correspondiente al orden n+1.
                Eso hace que alcancemos 233 y no 376 para n=6
                Última edición por Richard R Richard; 02/11/2018, 11:12:28.

                Comentario

                Contenido relacionado

                Colapsar

                Trabajando...
                X