Итерация по двум переменным в haskell

Question

Хорошо, продолжая решение проблем на Project Euler , я все еще начинаю изучать Haskell и программирование в целом.

Мне нужно найти наименьшее число, делимое на числа 1: 20

Итак, я начал с:

divides :: Int -> Int -> Bool
divides d n = rem n d == 0

divise n a  | divides n a == 0 = n : divise n (a+1) 
        | otherwise        = n : divise (n+1) a

Я хочу, чтобы он продолжал двигаться вверх для значений n, пока один магически не будет равномерно делиться на [1..20].
Но это не работает, и теперь я застрял, откуда идти. Я предполагаю, что мне нужно использовать: [1..20] для значения а, но я не знаю, как это реализовать.

Answer 1

Ну, как алгоритм, это вроде отстой.

Извините.

Но вас вводит в заблуждение список. Я думаю, что вы пытаетесь перебрать все доступные числа, пока не найдете тот, который все в [1..20] делит. В вашей реализации выше, если a не делит n, вы никогда не вернетесь назад и не проверите b

Любая простая реализация вашего алгоритма будет:

lcmAll :: [Int] -> Maybe Int
lcmAll nums = find (\n -> all (divides n) nums) [1..]

(с использованием Data.List.find и Data.List.all).

Лучшим алгоритмом было бы найти попарно lcm, используя foldl:

lcmAll :: [Int] -> Int
lcmAll = foldl lcmPair 1

lcmPair :: Int -> Int -> Int
lcmPair a b = lcmPair' a b
   where lcmPair' a' b' | a' < b' = lcmPair' (a+a') b'
                        | a' > b' = lcmPair' a' (b + b')
                        | otherwise = a'

Конечно, вы можете использовать функцию lcm из Prelude вместо lcmPair.

Это работает, потому что наименьшее общее кратное любого набора чисел совпадает с наименьшим общим кратным [наименьшего общего кратного двух из этих чисел] и [остальных чисел]

Answer 2

Функция divise никогда не останавливается, у нее нет базового варианта. Обе ветви вызывают деление, поэтому они оба рекурсивны. Вы также используете функцию divides, как если бы она возвращала int (как это делает rem), но она возвращает Bool.

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

Еще одна вещь, которая может помочь, - это написать типы функций. Если ваша функция работает, но вы не уверены в ее типе, попробуйте :i myFunction в ghci. Здесь я исправил ошибку типа в divides (хотя другие ошибки остались):

*Main> :i divise
divise :: Int -> Int -> [Int]   -- Defined at divise.hs:4:0-5

Вы хотите, чтобы он вернул список?

Оставив вас решить проблему, попробуйте еще больше разделить проблему на части. Вот наивный способ сделать это:

1. Функция, которая проверяет, делится ли одно число на другое. Это ваша divides функция.

2. Функция, которая проверяет, делится ли число на все числа [1..20].

3. Функция, которая пытается перебрать все числа и попробовать их на функции из # 2.

Answer 3

Ну, так как я недавно решил проблему Эйлера сам, я хотел бы просто опубликовать свой ответ на этот вопрос, но сейчас я воздержусь. :)

---

Прямо сейчас поток вашей программы немного хаотичен, звучит как человек фэн-шуй. По сути, вы пытаетесь сделать одну вещь: увеличивать n до 1..20 делит n. Но на самом деле, вы должны рассматривать это как два шага.

В настоящее время ваш код говорит: «если a не делит n, увеличивает n. Если a делит n, увеличивает a». Но это не то, что вы хотите сказать.

Вы хотите (я думаю) сказать «увеличить n и посмотреть, делит ли оно [Правка: со ВСЕМИ числами 1..20]. Если нет, увеличьте n еще раз, а затем снова протестируйте и т. Д.» То, что вы хотите сделать, - это выполнить суб-тест: тот, который берет число и проверяет его по 1..20, и затем возвращает результат.

Надеюсь, это поможет! Веселитесь с проблемами Эйлера!

Редактировать: Я действительно, действительно должен помнить все слова.

Answer 4

Вот мой быстрый, более подход Haskell-y, , использующий ваш алгоритм :

Prelude> let divisibleByUpTo i n = all (\x -> (i `rem` x) == 0) [1..n]
Prelude> take 1 $ filter (\x -> snd x == True) $ map  (\x -> (x, divisibleByUpTo x 4)) [1..]
[(12,True)]

divisibleByUpTo возвращает логическое значение, если число i делится на каждое целое число вплоть до n, аналогично вашей функции divides.

Следующая строка, вероятно, выглядит довольно трудно для новичка на Haskell, поэтому я объясню это по крупицам:

Начиная справа, у нас есть map (\x -> (x, divisibleByUpTo x 4)) [1..], который говорит для каждого числа x от 1 и выше, введите divisibleByUpTo x 4 и верните его в кортеже (x, divisibleByUpTo x 4). Я использую кортеж, чтобы мы знали, какое число делится точно.

Слева от этого у нас есть filter (\x -> snd x == True); то есть возвращать только те элементы, где второй элемент кортежа - True.

И в самом левом утверждении мы take 1, потому что в противном случае у нас был бы бесконечный список результатов.

Это займет довольно много времени для значения 20. Как и другие говорили, вам нужен лучший алгоритм - подумайте, как получить значение 4, хотя наши «входные» числа были 1-2-3-4 в конечном итоге ответом было только произведение 3 * 4. Подумайте, почему 1 и 2 были «исключены» из уравнения.