Помогите мне найти проблему с моим решением Project Euler # 12 в Haskell

Question

Я совершенно новичок в Haskell и в программировании в целом, но я пытаюсь решить некоторые проблемы с Project Euler, потому что мне нравится решать их. Однако у меня проблема с проблема # 12 .

Я придумал решение, которое, как я думал, будет работать, но, увы, нет.

Можете ли вы помочь мне, открыв глаза на проблему с моим кодом, и, возможно, подтолкнуть меня в правильном направлении, чтобы исправить это? Спасибо.

Вот код:

triangleNumber = scanl1 (+) [1..]

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

numFactors = length . factors

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

Большое спасибо! :)

Answer 1

Вопросы Project Euler разработаны таким образом, что пытаться решить их «грубой силой», то есть запрограммировать очевидный поиск и просто оставить его для выполнения, - плохая идея.(Некоторые из более ранних вопросов могут быть решены таким образом, но это хорошая идея не использовать это, а использовать их как практику.) Вместо этого вам нужно подумать о математическом содержании вопроса, чтобы сделать компьютерный поискtractable.

Я не хочу отдавать слишком много, но вот несколько подсказок:

• Есть формула для n thтреугольное число.Найдите его, так что вам не нужно вычислять его суммированием.

• Учитывая эту формулу для n th треугольного числа, какие числа могут быть его делителями?

• Учитывая то, что вы знаете об этих делителях, как легко определить, сколько их существует?(Без необходимости перечислять их.)

Answer 2

Я скопировал его, и он бросил мне ошибку, которую не удалось найти. Это потому, что вам нужно импортировать модуль List, в котором находится find:

import Data.List

Кстати, вы должны оптимизировать функцию факторов.

Answer 3

Я предполагаю, что проблема, на которую вы намекаете, состоит в том, что eulerTwelve занимает слишком много времени для завершения;ваш код правильный, просто неэффективный.Узким местом является ваша функция factors, которая проверяет каждое число от 1 до n, чтобы определить, является ли это делителем n.Вот более быстрый способ найти делители числа, используя эффективную простую факторизацию и изящную реализацию набора мощности :

import Data.Numbers.Primes (primeFactors)

powerSet = filterM (const [True, False])

factors = map product . nub . powerSet . primeFactors

Даже это довольнонеэффективны;вместо этого вы можете вычислить numFactors непосредственно из primeFactors следующим образом:

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

Когда я заменяю ваш numFactors на этот, я сразу получаю результат.

Answer 4

IIRC при проверке факторов вам не нужно проверять каждое целое число от 1 до n - только числа от 1 до n ^ 0,5 (квадратный корень из n), поскольку по этому числу вы уже получите все доступные факторы .