Proyecto Euler # 163 comprensión

Question

Pasé bastante tiempo buscando una solución a this problem. Dibujé toneladas de triángulos sombreados, conté los triángulos en casos simples y busqué algún tipo de patrón. Lamentablemente, golpeé la pared. Estoy bastante seguro de que mis habilidades de programación/matemáticas no cumplieron con el prerrequisito para este problema.

Encontré una solución en línea para acceder a los foros. No entendía la mayoría de los métodos, y algunos parecían demasiado complicados.

¿Alguien me puede dar una comprensión de este problema? Uno de los métodos, que se encuentra aquí: http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (Problema C) , permite el uso de una sola función.

¿Cómo se les ocurrió esa solución? En este punto, realmente me gustaría entender algunos de los conceptos detrás de este interesante problema. Sé que buscar la solución no era parte del espíritu de Euler, pero estoy bastante seguro de que no habría resuelto este problema de todos modos.

Answer 1

Esto es esencialmente un problema en la combinatoria enumerativa, que es el arte de contar combinaciones de cosas. Es un tema hermoso, pero probablemente te tome un poco de calentamiento antes de que puedas apreciar los trucos ninja en la referencia que le diste.

Por otra parte, los comentarios en el hilo de soluciones para el problema indican que muchos han resuelto el problema utilizando un método de fuerza bruta. Uno de los trucos más comunes consiste en tomar todas las combinaciones posibles de tres líneas en el diagrama, y ​​ver si producen un triángulo que se encuentra dentro del triángulo más grande.

Puede reducir considerablemente el espacio de búsqueda al observar que las líneas están en una de las seis direcciones. Como una combinación de líneas que incluye dos líneas que son paralelas no producirá un triángulo, puede iterar sobre tripletas de línea para que cada línea en el triple tenga una dirección diferente.

Dadas tres líneas, calcule sus puntos de intersección. Usted tendrá tres posibilidades 1) de las líneas son coincidentes - todos ellos se cruzan en un punto común 2) dos de las líneas se cruzan en un punto fuera del triángulo 3) todos los tres puntos de intersección son distintos, y todos ellos se encuentran dentro de el triángulo exterior

Simplemente cuente los combos que cumplen la condición (3) y listo. El número de combinaciones de línea que ha de probar es O (n), que no es prohibitivo.

EDIT1: volviendo a leer su pregunta, me da la impresión de que podría estar más interesado en obtener una explicación de la solución/fórmula combinatoria que un bosquejo de un enfoque de fuerza bruta. Si ese es el caso, dígalo y borraré esta respuesta.Pero también diría que la pregunta en ese caso no sería adecuada para este sitio.

EDIT2: Ver también a combinatorics solution by Bill Daly and others. Es matemáticamente un poco más suave que el otro.

Answer 2

No he resuelto este problema para project euler y me estoy saliendo de la cuestión y la solución que proporcionó. En el caso de la función única, la metodología presentada fue, en última instancia, simple búsqueda de patrones. El solucionador dividió la pregunta presentada en tres partes, en función de los tipos de triángulos que estaban presentes en las intersecciones. Es un enfoque bastante estándar para este tipo de problema, dividir el patrón más amplio en otros más pequeños para facilitar la resolución. Las funciones utilizadas para expresar las diversas formas de triángulos que solo puedo suponer se generaron con una mente de búsqueda de patrones muy aguda o con alguna teoría de números/geometría. También está más allá del alcance de esta explicación y mi conocimiento. Este problema no tiene nada que ver con la programación. Básicamente es completamente matemática. Si lees el sitio que te gustó, puedes ver la lógica que se sigue para llegar a las preguntas.