Функциональное программирование
Отчет по лабораторной работе №1
Выполнил:
Ефремов Марк Андреевич
Группа:
P3334
Преподаватель:
Пенской Александр Владимирович
Проблема 4
https://projecteuler.net/problem=4
Найти наибольшее число-палиндром, являющееся произведением двух трёхзначных чисел.
Реализация:
Перебор пар трёхзначных чисел I и J со следующими оптимизациями:
- Перебор от наибольших значений к наименьшим
- Умножение коммутативно, можно рассматривать J < I
- Если найдена пара I1 и J, такая, что I1*J1 – палиндром, то, переходя к дальнейшим итерациям, где I2, можно рассматривать только J < J1.
Реализации:
- С простой рекурсией
- С хвостовой рекурсией
- С модульной реализацией
- С map-генерацией
- С синтаксисом для циклов
- С ленивой коллекцией
- Реализация на Python
Выводы:
Во время работы с обычной рекурсией получал переполнение стека, в то время, как хвостовая рекурсия оптимизируется компилятором. Для проверки того, является ли рекурсия хвостовой, была использована аннотация @tailcall, но убрана из кода ради читабельности.
Модульная реализация с использованием последовательностей становится очень компактной за счёт оператора конвеерной обработки. Однако он требует написания большого количества лямбда-функций, которые засоряют код. Также, сложнее было применить вышеописанные оптимизации, поэтому модульная реализация оказалась очень медленной.
Реализация с ленивой коллекцией (Seq) полностью совпадает с “map-generated”, и также получилась медленной.
**Проблема 27**
https://projecteuler.net/problem=27 Найти произведение чисел a и b, таких, что при подстановке в формулу n2+an+b последовательных значений n от 0, она даёт наибольшее количество простых чисел.
Реализация:
Перебор пар трёхзначных чисел a и b со следующими оптимизациями:
- при n=0, n2+an+b = b, должно быть простым числом. Вывод – b должно быть простым.
- при n=1, n2+an+b = 1 + a + b. А значит, чтобы число получилось простым, у a и b должна быть разная чётность.
Реализации:
- С простой рекурсией
- С хвостовой рекурсией
- С модульной реализацией
- С map-генерацией
- С синтаксисом для циклов
- С ленивой коллекцией
- Реализация на Python
Выводы:
В данном случае обычную рекурсию было сделать сложнее, чем хвостовую.
Благодаря мутабельным полям record, а также синтаксису для циклов, на Ocaml можно написать решение, полностью аналогичное решению на Python. Однако этот язык не предоставляет аналогов для “break” и “continue”, что значительно ограничивает возможности работы с циклами.
Генерация последовательности с помощью map - решение, которое для первой проблемы было самым медленным, для второй оказалось самым быстрым. Я предполагаю, что это связано с тем, что я применил фильтрацию на всех этапах формирования последовательности.