(void *) blog

Posted on by fortytwo_de


En este problema hay dos casos: los que tienen una solución exacta y los que necesitan una aproximación. Primero explicaré cómo resolver los casos con una solución exacta.

Medias inversas con una cantidad fija de elementos

En este tipo de problemas, lo primero que se necesita es calcular la cantidad de elementos que va a producir la media.

Después de experimentar un poco con medias decimales, se pueden extraer unas reglas generales que se pueden aplicar a estos problemas.

Por ejemplo: la media inversa de 0.25 es [1, 0, 0, 0]. Al convertir 0.25 a forma fraccional, se tiene ¼. Curiosamente, 4 es el número de elementos en esta media inversa.

Para convertir a forma fraccional se busca un número k tal que al multiplicarlo por la parte decimal de un número se obtenga un número entero. En el caso de 0.25, k es 4. Y el resultado de multiplicar 0.25 por 4 es 1. Este resultado será importante en el siguiente paso.

Otro ejemplo: la media inversa de 4.25 es [5, 4, 4, 4]. 4.25 también se puede expresar como 4 + ¼. Curiosamente, se observa que hay un 5 (la parte entera del número + 1) y el resto de elementos son 4, es decir, la parte entera del número.

De momento, las reglas observadas son:

  • El número de elementos en la media inversa es k tal que la parte decimal multiplicada por k es un número entero.
  • x = parte decimal * k
  • Los x primeros elementos de la media inversa son parte entera del número + 1
  • Los k-x siguientes números de la media inversa son parte entera del número.

Muy bien, son unas reglas relativamente sencillas. Aquí mi implementación del programa que genera las medias inversas para casos exactos:

from math import floor, ceil, modf

target = 4.25
max_k = 10.0

def compute_avg(list):
    if len(list) == 0:
        return 0
    sum = reduce(lambda i, j: i + j, list)
    return round(float(sum) / len(list), 2)

def generate_list(target, n, m):
    result = [target + 1 for i in range(0, n)]
    map(lambda x: result.append(target), range(0, m))

    return result

def inverse_avg(target, n, m):
    res = generate_list(target, n, m)
    avg = compute_avg(res)

    return (avg, res)

(decimal, integer) = modf(target)
decimal = round(decimal, 2)
k = 1

while k < max_k:
    x = decimal * k
    if x == int(x):
        break
    k += 1

(n, m) = (int(x), int(ceil(k-x)))
print inverse_avg(int(target), n, m)

Y efectivamente, calcula perfectamente las medias inversas exactas de números con estas características.

$ python inverseavg.py 
(4.25, [5, 4, 4, 4])

Pero tiene problemas para calcular las medias inversas de números cuya k es mayor que 10. En este caso, directamente intenta resolverlo con k = 10.

$ python partial.py 
(9.7, [10, 10, 10, 10, 10, 10, 10, 9, 9, 9])

Medias inversas aproximadas

El problema de las medias inversas con una lista de elementos mayor de 10 es que, bueno, se sale fuera de los límites del problema. Por lo tanto, hay que escalar los límites.

En este caso, como el enunciado dice que los números cuyas medias inversas tienen una precisión decimal máxima de 2, el mayor número que va a convertir en entero a la parte decimal de cualquier número dentro de los límites del problema es 100.

El problema es que en estos casos, se va a obtener un k > 10, y por lo tanto, los valores de n y m también van a ser superiores a 10. Para solucionar esto, se utiliza una regla de tres que va escalando los valores de n y m originales hasta que encuentra el que más se aproxima al número objetivo.

Como la cantidad de números en un caso de aproximación no se puede saber con exactitud, o al menos no he conseguido encontrar el patrón, pruebo con todos los números del 1 al 10, los guardo en una lista y finalmente los comparo para obtener el que más se acerca a la solución final.

Se puede descargar el resultado final abajo.

Un problema muy interesante!


Posted on by fortytwo_de | Posted in Algoritmos, Matemáticas, Python


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>