Pull to refresh

Clojure и Project Euler, часть 1

Lisp *Clojure *

Предисловие


Недавно я начал изучать язык Clojure. Заинтересовал меня он потому, что это диалект lisp'a, выполняющийся на jvm. Сам я программирую на java, а lisp удивил меня своими скобочками. И тут такая смесь интересная. Да и с функциональным программированием тоже хотел познакомиться. Но тут же появилась проблема: как изучать clojure? Надо на нём что-то писать… А что? И пришёл к выводу, что очень удобно при изучении языка решить какие-нибудь несложные математические задачки: и к синтаксису привыкнешь, и с функционалом немного познакомишься. Для этого очень хорошо подходит Project Euler. Здесь я попробую показать, как начать работать с clojure и решить пару задач на нём. Я новичок в функциональном программировании и lisp'е, так что буду очень рад увидеть решения более близкие и красивые с точки зрения функционального и lisp'а.

Подготовка


Сперва надо конечно всё настроить, чтобы было где работать.
Clojure распространяется в виде jar-архива, как его подключать описано здесь.
Хороший, на мой взгляд, туториал можно найти тут.
Для clojure я использую emacs, как их подружить.
Вот, в принципе, и всё. Теперь можно приступить к решению этого самого Эйлера.

Задача 1


Задание
Найти сумму всех чисел от 1 до 1000 999, которые делятся на 3 или 5.

Алгоритм
1. Создать последовательность чисел от 1 до 1000 999 включительно.
2. Отфильтровать eё, оставив только нужные нам числа.
3. Просуммировать все числа.

Код
(reduce +
       (filter #(or (zero? (rem % 3))
                        (zero? (rem % 5)))
               (range 1000)))


(range 1000) — последовательность чисел от 0 до 999
(#or (zero? (rem % 3)) (zero? (rem % 5))) — анонимная ф-ция, проверяющая делится ли аргумент % на 3 или 5. Если аргумент 1, то он обозначается %, иначе %1, %2, %3…
(filter ...) — фильтрует нашу пос-ть с помощью нашей анонимной ф-ции.
(reduce + ...) — ф-ция, которая в нашем случае складывает числа последовательности.
Вообще стоит отдельно посмотреть описание reduce, т.к. она часто используемая.
Так же документацию на любую функцию можно посмотреть с помощью (doc functionName) прямо в repl'е.

Задача 2


Задание
Найти сумму всех чётных чисел Фиббоначи меньших 4 миллионов.

Алгоритм
1. Строим последовательность Фиббоначи fib-seq (бесконечную, благодаря ленивой инициализации).
2. Строим вторую последовательность из чисел Фиббоначи меньших 4 миллионов.
3. Отбираем только чётные.
3. Суммируем.

Код
(def fib-seq 
       (lazy-cat [1 2] (map + fib-seq (rest fib-seq))))
 
(reduce + 
            (filter even? 
                     (take-while #(< % 4000000) fib-seq))


Для меня тут самое сложно было осознать как задаётся пос-ть fib-seq в этом исполнении.
Она получается путём «склеивания» вектора [1 2] и пос-ти, которая вычисляется с помощью fib-seq. Как-то примерно так:

fib-seq = (1 2) + (3 5 8 13 ...)
                       =
         fib-seq: (1 2 3 5 ...)
                       +
  (rest fib-seq): (2 3 5 8 ...)


А дальше уже проще, с помощью take-while берём элементы из начала, пока они меньше 4000000, фильтруем и суммируем. Тут стоит отдельное внимание обратить на ф-цию map.

Задача промежуточная


Задание
Построить последовательность простых чисел (бесконечную).
Она пригодится ещё не в одной задаче из Эйлера.

Алгоритм
Идея и сама реализация взята отсюда.
В основе лежит решето Эратосфена. Решето — это у нас будет мап, в котором в качестве ключа будет выступать число, а значение — делитель числа. Сразу будем работать только с нечётными числами.
На каждом шагу мы будем брать очередного кандидата p, смотреть есть ли он в решете. Если нету — значит простое, иначе составное. Потом мы обновим решето, т.е. p — простое, то добавим в решето следующее число, делящееся на p, которого нет в решете. Если же p — составное, то мы его из решета достанем, достанем и его делитель, и добавим следующее число, которое делится на делитель и отсутствует в решете.

Код

Для реализаии напишем несколько ф-ций:

(defn enqueue [sieve candidate step]
      (let [(+ candidate step)]
            (if (sieve m)
                 (recur sieve m step)
                 (assoc sieve m step))))

Эта ф-ция добавляет в решето следующее число за кандидатом, которое делится на step и которого ещё нет в решете.

(defn next-sieve [sieve candidate]
        (if-let [step (sieve candidate)]
                (-> (dissoc sieve candidate)
                      (enqueue candidate step))
                (enqueue sieve candidate (+ candidate candidate))))

Эта ф-ция смотрит простой или составной кандидат и в зависимости от этого либо достаёт его из решета, либо нет. А потом добавляет следующий за ним, которого ещё нет в решете.

(defn next-primes [sieve candidate]
         (if (sieve candidate)
              (next-primes (next-sieve sieve candidate) (2 candidate))
              (cons candidate 
                       (lazy-seq (next-primes (next-sieve sieve candidate) (2 candidate))))))

Эта ф-ция и является основной, она возвращает пос-ть простых чисел. И она, к тому же, если я правильно понимаю, рекурсивная. На вход её даётся решето и кандидат. Она проверяет на простоту кандидата, и если он простой, то добавляет его к выходной пос-ти и вызывает себя рекурсивно с изменённым решетом и следующим кандидатом. Стоить отметить, что тут возвращается именно ленивая пос-ть (lazy-seq).

И теперь последняя фунцкия — создание глобальной последовательности простых чисел:
(def primes (concat [2] (next-primes {} 3)))


Задача 3


Задание
Найти максимальный простой делитель числа 600851475143.

Алгоритм
У нас будет 2 функции.
Одна вспомогательная, которая делит число на максимальную степень его делителя, чтобы «избавится» от делителя в числе.
Вторая основная, которая поочерёдно пробегает по всем простым числам и пытается наше число на них делить. И соответственно то простое число, после которого мы получили 1 и будет искомым.

Код
(defn divide-all [x divisor]
         (if (zero? (rem x divisor))
             (recur (/ x divisor) divisor)
             x))
 
(defn max-prime-divisor [x ind]
          (let [(divide-all x (nth primes ind))]
                (if (== m 1)
                    (nth primes ind)
                    (recur m (inc ind)))))

Тут мы использовали наши простые числа.

Вот и всё пока. Очень хотел бы увидеть какие-нибудь замечания, наставления на путь истинный с точки зрения самого языка и функционального программирования.
Tags:
Hubs:
Total votes 39: ↑35 and ↓4 +31
Views 5.3K
Comments Comments 25