Ayúdame a encontrar el problema con mi solución al Proyecto Euler # 12 en Haskell

Soy un novato total de Haskell, y la programación en general, pero estoy tratando de resolver algunos problemas del Proyecto Euler porque me gusta resolver problemas . Sin embargo, tengo un problema con problem #12.Ayúdame a encontrar el problema con mi solución al Proyecto Euler # 12 en Haskell

Inventé una solución que pensé que funcionaría, pero, por desgracia, no es así.

¿Puede ayudarme abriendo los ojos al problema con mi código, y tal vez me empuje en la dirección correcta para solucionarlo? Gracias.

Aquí está el código:

triangleNumber = scanl1 (+) [1..] 

factors n = [x | x <- [1..n], n `mod` x == 0] 

numFactors = length . factors 

eulerTwelve = find ((>500) . numFactors) triangleNumber

Muchas gracias! :)

Fuente

2011-01-22 Deven.W

Se ve bien conmigo. ¿Cuál es el problema específico que estás teniendo? – luqui

se mueve increíblemente despacio –

Y todo el tema del proyecto Euler es que puedes hacer la mayoría de los problemas usando la fuerza bruta, o puedes hacerlo inteligentemente usando un ingenioso para evitar la fuerza bruta. Si su código es lento, ¿está utilizando el enfoque de la fuerza bruta? Piense en el problema antes de escribir el código de fuerza bruta. En el caso de PE 12, esto es manejable usando incluso la fuerza bruta si lo haces de una manera razonable. (Eso es cierto para la mayoría de los problemas PE pequeños numerados). Sin embargo, hay una manera de mejorar esa solución. Piensa en cuál es la suma de los números 1 a n. –

Lo copié y lo que me arrojó fue un error que no se pudo encontrar. Esto se debe a que necesita para importar la lista de módulos, donde hallazgo está en:

import Data.List

Por cierto, usted debe optimizar su función de factores.

Fuente

2011-01-23 00:08:47

Acerca de la optimización de factores: para resolver algunos de los problemas de PE posteriores, es importante que cree una caja de herramientas con funciones para resolver tareas comunes. La factorización de números enteros resulta ser una de estas cosas, pero a medida que trabajes despacio sobre los problemas encontrarás que hay más cosas que solo esto. Entonces, cuando empiece, use la solución simple, pero recuerde volver y optimizarla más adelante. –

Sí, importé Data.List olvidé incluir eso en la publicación. Sin embargo, el problema que estaba experimentando no era ningún tipo de error explícito, sino más bien una lentitud extrema en mi computadora que producía la respuesta, –

. Creo que puede ser la función de factores que la está desacelerando, así que intentaré optimizar eso, gracias –

Supongo que el problema que está aludiendo es que eulerTwelve tarda demasiado en terminar; tu código es correcto, es ineficiente. El cuello de botella es su función factors, que está probando cada número entre 1 y n para ver si es un divisor de n. Aquí está una manera más rápida de encontrar los divisores de un número, usando efficient prime factorization y a nifty implementation of the power set:

import Data.Numbers.Primes (primeFactors) 

powerSet = filterM (const [True, False]) 

factors = map product . nub . powerSet . primeFactors

Incluso esto es bastante ineficiente; en su lugar puede calcular directamente a partir de numFactorsprimeFactors así:

numFactors = product . map ((+1) . length) . group . primeFactors

Cuando reemplazar su numFactors con éste obtengo el resultado al instante.

Fuente

2011-01-23 01:10:52

IIRC cuando se comprueban los factores, no es necesario que pruebe cada número entero entre 1 y n, solo los números entre 1 yn^0.5 (raíz cuadrada de n), ya que en este número ya habrá obtenido todos los factores disponible.

Fuente

2011-01-23 14:30:41 hspim

Solo (aproximadamente) la mitad de ellos, y la factorización prima es más eficiente de todos modos. – adamax

Las preguntas de Project Euler están diseñadas para que sea una mala idea intentar resolverlas por "fuerza bruta", es decir, programando la búsqueda obvia y dejándola correr. (Algunas de las preguntas anteriores se pueden resolver así, pero es una buena idea no explotar eso, sino usarlas como práctica). En su lugar, debe pensar en el contenido matemático de la pregunta para hacer que la búsqueda en la computadora manejable.

yo no quiero revelar demasiado, pero aquí hay algunos consejos:

Hay una fórmula para el número triangular º n. Encuéntralo, para que no tengas que calcularlo por suma.
Dada esta fórmula para el número triangular n, ¿qué números pueden ser sus divisores?
Teniendo en cuenta lo que usted sabe acerca de estos divisores, ¿cuál es una manera fácil de averiguar cuántos de ellos hay?(Sin tener que enumerarlos.)

Fuente

2011-01-23 15:34:48

Es bueno saber la forma cerrada del _n_ triángulo número, pero no lo hará más eficiente, ya que aún debe inspeccionar todos los números del triángulo en orden hasta que encuentre el correcto. De hecho, creo que el método 'scanl1 (+)' es ligeramente _más_ eficiente dado este hecho. –

@pelotom: Estoy de acuerdo en que * si * tuvieras que calcular todos los números del triángulo, entonces la suma repetida sería la mejor manera de hacerlo. Pero, ¿qué te hace pensar que tienes que calcular * cualquier * número de triángulo? (Aparte de la que necesita para la respuesta.) –

@Gareth: punto justo, estoy haciendo esa suposición. ¿Tiene una solución que no requiere examinar cada número de triángulo en orden? –

Ayúdame a encontrar el problema con mi solución al Proyecto Euler # 12 en Haskell

Respuesta

Cuestiones relacionadas