El cálculo de pesado números en un intervalo dado?

Question

Yo tenía una pregunta de la entrevista hace un par de días que involucran el cálculo de la cantidad de pesada entre los números en un rango dado. Se me ocurrió una solución básica, que fue para iterar a través de toda la gama y de la prueba para la pesadez de cada número. Me di cuenta de inmediato que se trata de una terriblemente ineficiente método de resolución del problema. En el interés de educar a mí mismo me han abordar el problema de hoy para intentar aprender más acerca de este tipo de problema. Es difícil para mí, porque yo no tengo una super fuerte de matemáticas, pero estoy tratando de aprender.

Básicamente, el problema va como esto:

Tomar cualquiera de los 2 números de 0 a 200,000,000. En ese rango, calcular el número de "heavy números". Este se calcula sumando todos los componentes dígitos y luego dividiendo por el número de componentes. Si el promedio es mayor que 7, el número se considera pesado.

Ejemplo:

1234: 1+2+3+4/4 = 2.5 (not heavy)
8996: 8+9+9+6/4 = 8 (heavy)

Así que, dado que el rango de 1002 - 12089, mi enfoque ingenuo es iterar sobre cada número entre y calcular su peso. Este enfoque rápidamente se cae a pedazos cuando se trata con muy gran número de rangos.

He hecho un poco de búsqueda a través de Google y Bing y más allá de un par de puestos donde la gente tiene copia/pega literal de la pregunta, me parece que casi no hay información sobre este tipo de problema. Sospecho que este tipo de problema se llama algo distinto de la "pesada números" pero estoy en una pérdida en cuanto a lo que la terminología es.

Aquí hay un enlace a una de esas discusiones: http://groups.google.com/group/algogeeks/browse_thread/thread/a1b824107afe3801

Tengo la esperanza de que alguien que esté familiarizado con el tipo de escenario puede explicar formas alternativas para resolver el problema de una manera simple, y que yo podría hacer preguntas de seguimiento hasta que yo entiendo.

Gracias por la lectura.

Answer 1

Si se desea calcular la respuesta exactamente, una manera de ir es el uso de funciones de generación (que es la misma como la programación dinámica).

Vamos a limitarnos a longitud determinada, decir $5$. Vamos a calcular cuántos números con exactamente $5$ dígitos dígitos que suman más de $35$.

La generación de la función de la suma de los dígitos es $$ (x+\cdots+x^9)(1+\cdots+x^9)^4. $$ Quiere suma de los coeficientes de $x^k$ todos los $k \geq 36$.

Como se mencionó anteriormente, este enfoque reduce a un algoritmo de programación dinámica. El algoritmo calcula de forma inductiva cuántas número de longitud exactamente $l \leq 5$ tienen una cierta suma de dígitos. Te dejo los detalles.

En caso de que su rango es más complicado, se puede romper. En primer lugar, podemos manejar algo así como "todos los números de longitud 5, que empieza con 1,2,3" ajustando el primer factor. En segundo lugar, se puede romper un rango arbitrario $[0,n]$ en intervalos de la forma (plus extra "constante" dígitos que sólo afectan a la elección del umbral). Por último, el uso de $[l,h] = [0,h] - [0,l-1]$ a manejar un rango arbitrario.

Si sólo desea estimar el número, el camino a seguir es el Teorema Central del Límite, o más bien Gran Desviación de la Teoría. La suma de los dígitos de un $n$-número de dígitos es aproximar por una variable normal - pero no muy lejos de la media, que es lo que estás buscando. Aún así, se calcula que existen en el error de la aproximación normal que puede ser útil. Métodos de Gran Desviación de la Teoría puede dar resultados más precisos.

Answer 2

He investigado esta cuestión un poco más de profundidad y aplicado dos soluciones. Por favor consulte

http://cpluspluslearning-petert.blogspot.co.uk/2014/07/dynamic-programming-heavy-numbers.html

http://cpluspluslearning-petert.blogspot.co.uk/2014/07/dynamic-programming-heavy-numbers-part.html