1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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
|
