¿Método para encontrar algoritmos eficientes?

Question

TL;DR

¿Qué se puede recomendar para mejorar en la búsqueda de soluciones eficientes a los problemas de matemáticas?

De fondo

El primer reto en el Proyecto de Euler dice:

Encontrar la suma de todos los múltiplos de 3 o 5 por debajo de 1000.

La primera, y la única solución que yo podía pensar era en que la fuerza bruta manera:

target = 999
sum = 0
for i = 1 to target do
if (i mod 3 = 0) or (i mod 5 = 0) then sum := sum + i
output sum

Esto no me da el resultado correcto, pero se vuelve exponencialmente más lento cuanto más grande sea el objetivo. Entonces vi a esta solución:

target=999
Function SumDivisibleBy(n)
   p = target div n
   return n * (p * (p + 1)) div 2
EndFunction
Output SumDivisibleBy(3) + SumDivisibleBy(5) - SumDivisibleBy(15)

Yo no tengo problemas para la comprensión de cómo funciona la matemática, y al ver esto me siento como si pudiera se han dado cuenta de que a mí mismo. El problema es que nunca voy a hacer. Siempre termino con algunos exponencial, la fuerza bruta, como solución.

Obviamente hay una gran diferencia entre la comprensión de una solución, y de hecho darse cuenta de que la solución de ti mismo. Y no estoy preguntando cómo se Euler a sí mismo.

Lo que yo me pregunto tho es, ¿hay métodos y / o pasos, usted puede aplicar para resolver problemas de matemáticas para encontrar la mejor (o al menos una buena solución?

Si sí, pueden ustedes recomendar algunos libros/videos/conferencias para enseñar estos métodos? Y ¿qué haces a ti mismo al intentar encontrar soluciones?

Answer 1

No existe un método general para encontrar algoritmos eficientes, ya que no hay ningún método para resolver los problemas de matemáticas en general. Además de la práctica y la cultura.

En el problema en la mano, usted podría simplificar y preguntarse: "¿cuál es la suma de los múltiplos de $3$ por debajo de $1000$ ?". Obviamente, estas son las $3,6,9,\cdots999$, es decir, $3\cdot1,3\cdot2,3\cdot3,\cdots3\cdot333$, y la suma es tres veces la suma de números enteros de $1$ a $1000/3$, por lo que una fórmula es conocida (triangular números). Y este es un gran paso, como sustituir una larga suma por una escalera de fórmula.

Ahora bien, si se cambia el "más difícil" caso de los múltiplos de $3$ o $5$, puede repetir el anterior razonamiento para los múltiplos de $5$. Pero el pensamiento más profundo, usted puede darse cuenta de que quieres pasar a contar dos veces los números que son múltiples de $3$ e $5$, yo.e los múltiplos de $15$. Así, una correcta respuesta está dada por la suma de los múltiplos de $3$ más la suma de los múltiplos de $5$ menos la suma de los múltiplos de $15$.

Answer 2

TL;DR: "soluciones Eficientes a los problemas de matemáticas" no existen. Matemáticas los problemas tienen solución, y el diseño del algoritmo de los problemas que han eficiente y soluciones ineficientes. Reconocer cual es cual puede ser la mitad de la tarea.

---

Usted debe tener cuidado aquí para diferenciar entre lo que yo llamo, matemáticas y ciencias de la computación de problemas. Lo que ves arriba es un problema de matemáticas. Curiosamente, me utiliza para ejecutar una ciencia de la computación de la competencia que contó con una amplia gama de problemas en el diseño del algoritmo. Algunos de ellos eran la verdadera ciencia de la computación problemas; otros eran lo que se llama "matemáticas con un bucle for". Estos problemas suelen contó con una apenas disimulada problema de matemáticas, por lo que había que encontrar una exacta de la solución numérica que era generalmente en la forma de una suma única, la necesidad de escribir un programa con una sola de bucle para calcular esta suma. Por lo tanto, "las matemáticas con un bucle for."

La manera de ir sobre el aprendizaje de estos problemas es significativamente diferente. Para "matemáticas con un bucle for" problemas, el estudio de las matemáticas. Típico de un profundo entendimiento de álgebra y combinatoria (y, ocasionalmente, la teoría de los números) va a venir en muy útil aquí. Pero esto no es tan importante para la real de ciencias de la computación preguntas. El diseño del algoritmo es duro. Hay un par de técnicas estándar, pero muchos problemas difíciles no encajan fácilmente en cualquiera de estos. Aquí la solución es sólo para aprender tanto como pueda, y a la práctica.

Pero el problema anterior no es una ciencia de la computación problema. Se trata de un problema de matemáticas. Se puede muy fácilmente ser reescrito en

Deje $S$ ser el conjunto de todos los múltiplos de $3$ o $5$, y deje $f(n)$ la suma de los elementos de $S$ por debajo de $n$. Calcular $f(1000)$.

El problema de encontrar una forma cerrada para $f(n)$ es totalmente un problema de matemáticas - usted sólo necesita algunos combinatoria, y no de ciencias de la computación para resolver. Entonces es sólo una cuestión de conectar y el traqueteo de conseguir $f(1000)$, su respuesta final.