[FP/P02] Solved exercises from second practicum

1 files changed, 91 insertions, 0 deletions

diff --git a/Year 2/Functional Programming/02-Practice-10.11.2022.rkt b/Year 2/Functional Programming/02-Practice-10.11.2022.rkt
new file mode 100644
index 0000000..d21ce2b
--- /dev/null
+++ b/Year 2/Functional Programming/02-Practice-10.11.2022.rkt
@@ -0,0 +1,91 @@
+#lang racket
+
+
+
+;;; Задача 1. Да се напише функция mygcd a b, която връща НОД(a, b).
+
+(define (mygcd a b)
+  ;; Euclidean algorithm
+  (cond
+    [(> a b) (mygcd b a)]
+    [(= a 0) b]
+    [else (mygcd (remainder b a) a)]))
+
+
+
+;;; Задача 2. Да се напише функция mymaxdivisor x, която намира най-големия делител d на цялото число x > 1, за който d < x.
+
+(define (mymaxdivisor x)
+  ;; We find the smallest divisor, and x divided by it will bring the biggest divisor
+  (define (helper s)
+    (if (= (remainder x s) 0)
+      s
+      (helper (+ s 1))))
+  (quotient x (helper 2)))
+
+
+
+;;; Задача 3. Да се дефинира функция sum-odds a b, която намира сумата на нечетните числа в затворения интервал [a, b].
+
+(define (sum-odds a b)
+  (cond
+    [(= a b) a]
+    [(= (remainder a 2) 0) (sum-odds (+ 1 a) b)]
+    [(= (remainder b 2) 0) (sum-odds a (- 1 b))]
+    ;; Formula for sum of arithmetic progression, where a_1 = a, a_n = b, n = (b - a) / 2 + 1
+    ;; (n = count of odd numbers between a and b)
+    [else (* (/ (+ a b) 2) (+ (/ (- b a) 2) 1))]))
+
+
+
+;;; Задача 4. Да се дефинира предикат prime? n, който проверява дали естественото число n е просто.
+
+(define (prime? n)
+  ;; Finding primes is done with a plethora of optimizations. Here, we check until we reach (sqrt n)
+  ;; and we check the value above and below every six numbers. Wikipedia explains these methods in
+  ;; further detail: https://en.wikipedia.org/wiki/Primality_test#Simple_methods
+  ;; Implementation of my C code: https://gitlab.com/Syndamia/algorithms/-/blob/master/C/IsPrime.c
+  (define (helper i maxi)
+    (cond
+      [(> (- i 1) maxi) #t]
+      [(or (= (remainder n (- i 1)) 0) (= (remainder n (+ i 1)) 0)) #f]
+      [else (helper (+ i 6) maxi)]))
+  ;; Another optimization is to do a couple simple checks which will rule out a lot of numbers
+  (cond
+    [(<= n 1) #f]
+    [(<= n 3) #t]
+    [(or (= (remainder n 2) 0) (= (remainder n 3) 0)) #f]
+    [else (helper 6 (sqrt n))]))
+
+
+
+;;; Задача 5. Да се дефинира функция count-palindromes a b, която намира броя на палиндромите в интервала [a, b], където a и b са цели неотрицателни числа и a<b.
+
+(define (palindrome? n)
+  ;; i stores the left side of the digits, and j stores the right side
+  (define (helper i j)
+    (cond
+      [(= i 0) #f]
+      [(or (= i j) (= (quotient i 10) j)) #t]
+      [else (helper (quotient i 10) (+ (remainder i 10) (* j 10)))]))
+  (cond
+    [(= n 0) #t]
+    [(or (< n 0) (= (remainder n 10) 0)) #f]
+    [else (helper n 0)]))
+
+(define (count-palindromes a b)
+  (if (> a b)
+    0
+    (+ (count-palindromes (+ 1 a) b) (if (palindrome? a) 1 0))))
+
+
+
+;;; Задача 6. Да се дефинира функция count-divisors n, която чрез линейно итеративен процес намира броя на естествените делители на едно естествено число n.
+
+(define (count-divisors n)
+  (define (helper d)
+    (cond
+      [(< (quotient n 2) d) 0]
+      [(= (remainder n d) 0) (+ (helper (add1 d)) 1)]
+      [else (helper (add1 d))]))
+  (+ (helper 2) 2)) ; We don't need to have checks for 1 and n itself