- Вариант: 12, 19
- Преподаватель Пенской Александр Владимирович
- Выполнил
Горляков Даниил Петрович,367165 - ИТМО, Санкт-Петербург, 2024
Данная лабораторная работа направлена на применение различных подходов функционального программирования для решения задач из Project Euler. Решенные задачи:
- Задача 12: Нахождение первого треугольного числа с более чем
Nделителями. - Задача 19: Подсчет количества воскресений, выпадающих на первое число месяца за определенный период.
- p12/ и p19/ — директории с решениями задач 12 и 19 соответственно.
- lib/ — модули и файлы с реализациями различных подходов:
- test/ — тесты для проверки решений, написанные с использованием
OUnit2.*
* - только в p12, в p19 испльзуются inline тесты.
Ниже приведены тематические особенности реализаций (где использована рекурсия, хвостовая рекурсия, модульное решение и пр.)
let count_factors n =
let rec aux i =
if i * i > n
then 0
else if n mod i = 0
then if i * i = n then 1 + aux (i + 1) else 2 + aux (i + 1)
else aux (i + 1)
in
if n <= 0 then 0 else aux 1
;;let count_factors_tail n =
let rec aux i count =
if i * i > n
then count
else if n mod i = 0
then aux (i + 1) (count + if i * i = n then 1 else 2)
else aux (i + 1) count
in
if n <= 0 then 0 else aux 1 0
;;let result =
List.filter (fun x -> count_factors_tail x > 500) triangular_numbers
|> List.fold_left
(fun acc x ->
match acc with
| Some _ -> acc
| None -> Some x)
None
;;
let triangular_numbers limit =
let generate_range n = List.init n (fun i -> i + 1) in
List.map (fun n -> n * (n + 1) / 2) (generate_range limit)
;;let triangular_numbers =
Seq.unfold
(fun n ->
let t = n * (n + 1) / 2 in
Some (t, n + 1))
1
;;let find_first_triangular_with_factors n =
Seq.find (fun x -> count_factors_tail x > n) triangular_numbers
;;let count_divisors n =
let count = ref 0 in
let root = int_of_float (sqrt (float_of_int n)) in
for i = 1 to root do
if n mod i = 0 then if i = n / i then incr count else count := !count + 2
done;
!count
;;let find_triangle_with_divisors limit =
let found = ref false in
let result = ref 0 in
let n = ref 1 in
while not !found do
let tri_num = triangle_number !n in
if count_divisors tri_num > limit
then (
result := tri_num;
found := true);
incr n
done;
!result
;;def count_divisors(n):
sqrt_n = int(math.sqrt(n))
count = sum(2 for i in range(1, sqrt_n + 1) if n % i == 0)
if sqrt_n * sqrt_n == n:
count -= 1
return countdef first_triangle_number_with_divisors(limit):
n = 1
triangle = 1
while True:
divisors = count_divisors(triangle)
if divisors > limit:
return triangle
n += 1
triangle += nНиже приведены тематические особенности реализаций (где использована рекурсия, хвостовая рекурсия, модульное решение и пр.)
let rec count_sundays year month day_of_week =
if year > 2000
then 0
else (
let new_count = if day_of_week = 0 then 1 else 0 in
let days_this_month = days_in_month year month in
let next_day_of_week = (day_of_week + days_this_month) mod 7 in
if month == 12
then new_count + count_sundays (year + 1) 1 next_day_of_week
else new_count + count_sundays year (month + 1) next_day_of_week)
;;let rec count_sundays year month day_of_week count =
if year > 2000
then count
else (
let new_count = if day_of_week = 0 then count + 1 else count in
let days_this_month = days_in_month year month in
let next_day_of_week = (day_of_week + days_this_month) mod 7 in
if month == 12
then count_sundays (year + 1) 1 next_day_of_week new_count
else count_sundays year (month + 1) next_day_of_week new_count)
;;let count_sundays start_year end_year =
let years = List.init (end_year - start_year + 1) (fun i -> start_year + i) in
let aux year =
let months = List.init 12 (fun m -> m + 1) in
List.filter (fun month -> zellers_congruence year month 1 = 0) months |> List.length
in
List.fold_left (fun acc year -> acc + aux year) 0 years
;;let count_sundays start_year end_year =
let years = List.init (end_year - start_year + 1) (fun i -> start_year + i) in
let aux year =
let months = List.init 12 (fun m -> m + 1) in
let map_filter month = if zellers_congruence year month 1 = 0 then 1 else 0 in
List.fold_left ( + ) 0 (List.map map_filter months)
in
List.fold_left (fun acc year -> acc + aux year) 0 years
;;let count_sundays start_year end_year =
let count = ref 0 in
for year = start_year to end_year do
for month = 1 to 12 do
if zellers_congruence year month 1 = 0 then incr count
done
done;
!count
;;for year in range(1901, 2001):
for month in range(1, 13):
first_day = datetime(year, month, 1)
if first_day.weekday() == 6:
sundays_count += 1OCaml показался мне достаточно простым и понятным по синтаксису, однако, при поиске сталкивался с примерами на Haskell и не понимал, почему первый так усложняет местами.
Я познакомился с такими функциями, как List.map, List.filter и List.fold, они сделали код более компактным и понятным. Использование функции filter для отсеивания неподходящих значений делает код более декларативным.
Также я воспользовался ленивыми коллекциями (Seq), для генерации бесконечного количества треугольных чисел, что за счет лени позволило обратиться только к нужному количеству треугольных чисел и не нужно было придумывать, как создавать следующее.
Вторую (p19) задачу получилось решить более качественно, на мой взгляд, вероятнее всего благодаря тому, что уже разобрался с синтаксисом и подходам к решению задач. Тем не менее, было тяжело придумывать различные способы решения, поскольку обычно достаточно одного решения.
Для запуска тестов с использованием OUnit2:
dune runtestДля сборки и запуска проекта необходимо иметь:
- OCaml >= 4.12.0
- Dune >= 2.0
- OUnit2
- ppx_inline_test