Aquí está una manera eficiente: encontrar qué fracción de la forma $k/l$ (para valores enteros y $l <= n$) es el armario a su destino. Todos los promedios de puede conseguir va a ser de este formato. A continuación, observe que para un determinado $l$, usted puede obtener todos los valores consecutivos de $k/l$ en un rango.
Ejemplo: Mediante la selección de $\{1,2,3,4\}$ puede llegar:
$l=1: 1,2,3,4$
$l=2: 1.5, 2, 2.5, 3, 3.5$
$l=3: 2, 2.33, 2.66, 3 $
El rango que puede alcanzar para $k/l$ es a partir de la media de la primera $l$ enteros a la media de los últimos$l$.
La enumeración de la gama está en el orden de $n$ operaciones, encontrar el más cercano es el tiempo constante, con lo que consigue un algoritmo eficiente para la razonable $n$ (millones o menos).
He implementado un áspero prototipo (C++, alguien probablemente puede traducir a Mathematica). Ver
http://pastebin.com/91kXULTQ
Ejemplo de salida:
target is 3.14159
Average of
-100, -99, -98, -97, -96, -95, -94, -93, -92, -91, -90, -89, -88, -87, -86, -85, -84, -83, -82, -81, -80, -79, -78, -77, -76, -75, -74, -73, -72, -71, -70, -69, -68, -67, -66, -65, -64, -63, -62, -61, -60, -59, -58, -57, -56, -55, -54, -53, -52, -51, -50, -29, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
is 3.14159
Muy interesante la pregunta.
P. S.: El prototipo tiene la precisión de problemas, pero el algoritmo es no.
