algorithm - problems - Proyecto Euler#163 entendiendo
project euler 1 (2)
No he resuelto este problema para el proyecto euler y me estoy desviando de la pregunta y de la solución que proporcionó. En el caso de la función única, la metodología presentada fue, en última instancia, la búsqueda de patrones simples. 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 grande 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 asumir 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. Se trata básicamente de matemáticas en su totalidad. Si lees el sitio que te gustó, puedes ver la lógica que se ha seguido para llegar a las preguntas.
Pasé bastante tiempo buscando una solución a este problema . Dibujé toneladas de triángulos rayados, conté los triángulos en casos simples y busqué algún tipo de patrón. Lamentablemente, me golpeó la pared. Estoy bastante seguro de que mis habilidades de programación / matemáticas no cumplieron con el requisito previo para este problema.
Así que encontré una solución en línea para poder 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) permitió 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 problema interesante. 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.
Este es esencialmente un problema en la combinatoria enumerativa, que es el arte de contar combinaciones de cosas. Es un tema hermoso, pero probablemente necesite un poco de calentamiento antes de que pueda apreciar los trucos de ninja en la referencia que dio.
Por otro lado, los comentarios en el hilo de soluciones para el problema indican que muchos han resuelto el problema utilizando un enfoque 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 esté dentro del triángulo más grande.
Puede reducir considerablemente el espacio de búsqueda observando 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 las líneas triples para que cada línea en el triple tenga una dirección diferente.
Dadas las tres líneas, calcule sus puntos de intersección. Tendrá tres posibilidades 1) las líneas coinciden; todas se intersecan en un punto común 2) dos de las líneas se intersecan en un punto fuera del triángulo 3) los tres puntos de intersección son distintos y todos se encuentran dentro del triángulo externo
Solo cuenta las combinaciones que satisfacen la condición (3) y listo. El número de combinaciones de líneas que tienes que probar es O (n 3 ), que no es prohibitivo.
EDIT1: al releer su pregunta, tengo 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 esquema de un enfoque de fuerza bruta. Si ese es el caso, dilo y eliminaré esta respuesta. Pero también diría que la pregunta en ese caso no sería adecuada para este sitio.
EDIT2: Vea también una solución combinatoria por Bill Daly y otros . Es matemáticamente un poco más suave que el otro.