viernes, 22 de julio de 2016

Histogaritmos

Primero, la definición de histogaritmo (medio rebuscada pero luego de un rato se hace natural).

Supongamos que tenemos una lista no vacía de números. Por ejemplo:

L = [1, 1, 1, 2, 2, 3, 3, 3, 4] (ordenar la lista no es necesario, pero es práctico)

Calculamos su histograma H(L), que consiste en las cantidades de cada grupo de números iguales:

H(L) = [1, 2, 3, 3] (porque en L hay 1 cuatro, 2 dos, 3 unos y 3 treses)

y luego hacemos el histograma del resultado:

H^2(L) = [1, 1, 2]

y así siguiendo hasta que llegamos a un resultado con un solo elemento (en este caso, tras tres pasos más):

H^3(L) = [1, 2]

H^4(L) = [1, 1]

H^5(L) = [2]

Como iteramos 5 pasos para llegar a una lista unitaria, decimos que 5 es el histogaritmo de L.

Ahora, el problema:

Dado un natural N, ¿Cómo construir una lista de N elementos que tenga el mayor histogaritmo posible?