Proyecto Euler # 8: ¿Hay un algoritmo más eficiente que el cálculo de la fuerza bruta?

Question

Pregunta

¿Hay una mejor manera de encontrar la solución del problema del proyecto Euler 8, que es Find the greatest product of five consecutive digits in the 1000-digit number, que el método de fuerza bruta.

Calculé todos los productos posibles y seleccioné el mejor: algoritmo de fuerza bruta.

¿Hay un algoritmo más eficiente? O es el método de la fuerza bruta la única forma.

lateral señala

• Esta no es una pregunta tarea.
• No estoy pidiendo para que el resultado problema 8.

Answer 1

Dado que la pregunta se refiere dígitos consecutivos, 'fuerza bruta' significa O (n) en este caso, n ser el número de dígitos (1000). Siempre que no haya algún tipo de patrón en el número, necesitará n pasos para escanear el número, por lo que esta es la solución más rápida.

Puede almacenar en caché el producto de los últimos 4 dígitos o hacer trucos similares, pero definitivamente no obtendrá mejores que O (n).

Answer 2

Puede usar una ventana deslizante de tamaño 5 y solucionar esto en O(d), donde d es el número de dígitos en el número de entrada.

Representa la ventana por índice del número de inicio en la ventana y el valor de la ventana i es el producto de elementos con índice [i, i + 4]. Ahora, en cada iteración, desliza la ventana hacia la derecha, soltando efectivamente el elemento situado más a la izquierda y agregando un nuevo elemento a la derecha y el nuevo valor de la ventana es old_value/left_most_ele * new_right_ele. Siga haciendo esto para cada índice i en el rango [0,d-5] y encuentre el valor máximo de la ventana.

Tenga en cuenta que el método de fuerza bruta de tener bucles anidados donde el bucle interno se ejecuta cinco veces también es una solución O(d). Pero el método anterior es ligeramente mejor ya que no hacemos cinco multiplicaciones en cada paso, sino que hacemos una multiplicación y una división.

Answer 3

Sí y no. Tienes que mirar cada secuencia de cinco dígitos consecutivos, pero no tienes que multiplicar cada una de esas secuencias a lo largo del ciclo. Hay atajos que puede tomar para acelerar el procesamiento. Por ejemplo, si el siguiente dígito es un 0, puede saltear adelante. Además, si el siguiente dígito es más pequeño que el último que eliminó de la secuencia, sabrá que el resultado de multiplicar por los otros cuatro dígitos comunes será más pequeño, así que sáltese la multiplicación y vaya al siguiente dígito. Trucos como este no harán mucha diferencia cuando solo tengas 1000 dígitos, pero los problemas posteriores serán los mismos, solo que con una entrada más grande.

Answer 4

Una optimización es calcular el producto de los primeros cinco dígitos y en cada iteración multiplicar por el siguiente dígito y dividir por el anterior (ventana móvil).

Otra optimización es descartar inmediatamente todos los dígitos alrededor de 0.