blob: 336bb5a4cca8c6a52dc920f47bb33298181cfbbe (
plain) (
blame)
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
|
#lang racket
;;; Задача 1
(define (pair-compose fs xs)
(cond [(= (length fs) 0) 0]
[(= (length fs) 1) (lambda (y) ((car fs) (car xs) y))]
[else (lambda (y) (+ ((first fs) (first xs) ((second fs) (second xs) y))
((pair-compose (cddr fs) (cddr xs)) y) ))]))
;; Примери
(define fs (list *
(lambda (x y) (* x x x y))
(lambda (x y) (+ x 1 y))
(lambda (x y) (- x (+ 1 y)))
(lambda (x y) (* x y 2))))
(define xs '(1 2 3 4 5))
((pair-compose fs xs) 5) ; → 92
;;; Задача 2
(define (pop&pushb lst elem)
(append (cdr lst) (list elem)))
(define (range-doesnt-cover? range ranges)
(cond [(null? ranges) #t]
[(and (<= (car range) (cdar ranges))
(>= (cdr range) (caar ranges))) #f]
[else (range-doesnt-cover? range (cdr ranges))]))
;; Превръща всички двойки '(позиция . височина) в двойки '(позиция . позиция)
(define (treehs-to-range treehs) ; treeh са дървета от тип '(позиция . височина)
(define current (cons (caar treehs) (caar treehs)))
(if (null? (cdr treehs))
(list current)
(list* current (treehs-to-range (cdr treehs)))))
(define (fell-left treeh) ; treeh са дървета от тип '(позиция . височина)
(cons (- (car treeh) (cdr treeh)) (car treeh)))
(define (fell-right treeh) ; treeh са дървета от тип '(позиция . височина)
(cons (car treeh) (+ (car treeh) (cdr treeh))))
(define (woodcutters xs)
(define (calc xs trees count)
;; Третираме всяко дърво, което не е паднало, като интервал [xi, xi]
;; Така лесно проверяваме дали паднало дърво би се засекло с някое стоящо или друго паднало
;; За опростение на кода, винаги (car trees) трябва да бъде [xi, xi] представянето на (car xs),
;; затова ползваме pop&pushb
(cond [(null? xs) count]
; Ако падне в ляво и не покрива нищо
[(range-doesnt-cover? (fell-left (car xs)) (cdr trees))
(calc (cdr xs) (pop&pushb trees (fell-left (car xs))) (add1 count))]
; Ако падне в дясно и не покрива нищо
[(range-doesnt-cover? (fell-right (car xs)) (cdr trees))
(calc (cdr xs) (pop&pushb trees (fell-right (car xs))) (add1 count))]
[else
(calc (cdr xs) (pop&pushb trees (car trees)) count)]))
(calc xs (treehs-to-range xs) 0))
;; Примери
(woodcutters '((1 . 2) (2 . 1) (5 . 10) (10 . 9) (19 . 1))) ; → 3
(woodcutters '((1 . 2) (2 . 1) (5 . 10) (10 . 9) (20 . 1))) ; → 4
(woodcutters '((10 . 4) (15 . 1) (19 . 3) (20 . 1))) ; → 4
(woodcutters '((1 . 7) (3 . 11) (6 . 12) (7 . 6) (8 . 5) (9 . 11)
(15 . 3) (16 . 10) (22 . 2) (23 . 3) (25 . 7) (27 . 3) (34 . 5)
(35 . 10) (37 . 3) (39 . 4) (40 . 5) (41 . 1) (44 . 1) (47 . 7)
(48 . 11) (50 . 6) (52 . 5) (57 . 2) (58 . 7) (60 . 4) (62 . 1)
(67 . 3) (68 . 12) (69 . 8) (70 . 1) (71 . 5) (72 . 5)
(73 . 6) (74 . 4) ) ) ; → 10
|
