Лабораторная работа №1

Цель:

Освоить базовые приёмы и абстракции функционального программирования: функции, поток управления и поток данных, сопоставление с образцом, рекурсия, свёртка, отображение, работа с функциями как с данными, списки.

В рамках лабораторной работы вам предлагается решить несколько задач проекта Эйлер. Список задач -- ваш вариант.

Для каждой проблемы должно быть представлено несколько решений:

монолитные реализации с использованием:
- хвостовой рекурсии;
- рекурсии (вариант с хвостовой рекурсией не является примером рекурсии);
модульной реализации, где явно разделена генерация последовательности, фильтрация и свёртка (должны использоваться функции reduce/fold, filter и аналогичные);
генерация последовательности при помощи отображения (map);
работа со спец. синтаксисом для циклов (где применимо);
работа с бесконечными списками для языков, поддерживающих ленивые коллекции или итераторы как часть языка (к примеру Haskell, Clojure);
реализация на любом удобном для вас традиционном языке программирования для сравнения.

Требуется использовать идиоматичный для технологии стиль программирования.

Решения:

Ссылка на ветку с CI в Github

Задача №5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Работа с бесконечными списками

   list1 = take 20 [1,2..]

Хвостовая рекурсия

Решение "в лоб" - ищем от единицы до n такое число, которое будет делиться без остатка на все числа до bound включительно.

Используется bounded-функция helper с сохранением результата и выхода из функции без повторных вычислений после разложения рекурсии.

smallestDividendByAll :: Int -> Int
smallestDividendByAll bound = helper 1 1 bound
  where
    helper n result b
      | n > b = result
      | result `mod` n == 0 = helper (n + 1) result b
      | otherwise = helper 1 (result + 1) b

Рекурсия (с использованием built-in LCM)

При помощи рекурсивного вызова функции LCM из пакета Prelude ищем наименьшее удовлетворяющее условиям число.

lcmForList :: [Int] -> Int
lcmForList [] = 1
lcmForList [x] = x
lcmForList (x : xs) = customLcm x (lcmForList xs)
  where
    customLcm _ 0 = 0
    customLcm 0 _ = 0
    customLcm a b = abs ((a `quot` gcd a b) * b)

Решение на языке Python:

ls = [x for x in range(1, 21)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(ls):
    tmp = 1
    for i in ls:
        tmp = tmp * i // gcd(tmp, i)
    return tmp


print(lcm(ls))

Задача №26:

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5

1/3 = 0.(3)

1/4 = 0.25

1/5 = 0.2

1/6 = 0.1(6)

1/7 = 0.(142857)

1/8 = 0.125

1/9 = 0.(1)

1/10 = 0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle. Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

Итератор и хвостовая рекурсия

cycleLength :: Int -> (Int, Int)
cycleLength n =
  let remainders = iterate (\x -> mod (x * 10) n) 1
      findCycle (_ : _) [] = undefined
      findCycle [] [] = undefined
      findCycle [] (x : xs) = findCycle (x : []) xs
      findCycle acc (x : xs) = case elemIndex x acc of
        Nothing -> findCycle (x : acc) xs
        Just i -> (i + 1, n)
   in findCycle [] remainders

Свёртка (вспомогательная функция для нахождения максимума)

argMax :: (Ord a) => [(a, a)] -> (a, a)
argMax = foldl1' (\x y -> if fst y > fst x then y else x)

Отображение для работы с бесконечными списками

mapList :: [Int] -> [(Int, Int)]
mapList ls = map cycleLength ls