From b503560635cc91092bc9e93d76011338afa36656 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Thu, 20 Oct 2022 11:27:45 +0300 Subject: [FP/P02] Fixed month in filename --- .../02-Practice-10.10.2022.rkt | 91 ++++++++++++++++++++++ .../02-Practice-10.11.2022.rkt | 91 ---------------------- 2 files changed, 91 insertions(+), 91 deletions(-) create mode 100644 Year 2/Functional Programming/02-Practice-10.10.2022.rkt delete mode 100644 Year 2/Functional Programming/02-Practice-10.11.2022.rkt (limited to 'Year 2/Functional Programming') diff --git a/Year 2/Functional Programming/02-Practice-10.10.2022.rkt b/Year 2/Functional Programming/02-Practice-10.10.2022.rkt new file mode 100644 index 0000000..d21ce2b --- /dev/null +++ b/Year 2/Functional Programming/02-Practice-10.10.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 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 diff --git a/Year 2/Functional Programming/02-Practice-10.11.2022.rkt b/Year 2/Functional Programming/02-Practice-10.11.2022.rkt deleted file mode 100644 index d21ce2b..0000000 --- a/Year 2/Functional Programming/02-Practice-10.11.2022.rkt +++ /dev/null @@ -1,91 +0,0 @@ -#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 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 -- cgit v1.3.1-23-gd82d