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
|
-- Exercise 1
findNb :: Integer -> Integer
findNb m = calc 1 m 0
where
calc curr m n
| m < 0 = -1
| m == 0 = n
| otherwise = calc (curr + 1) (m - curr^3) (n + 1)
-- Exercise 2
dominates :: (Int -> Int) -> (Int -> Int) -> [Int] -> Bool
dominates _ _ [] = True
dominates f g xs = abs (f (head xs)) >= abs (g (head xs)) && dominates f g (tail xs)
-- Exercise 3
type Point = (Double,Double)
splitPoints :: Point -> Double -> [Point] -> ([Point],[Point])
splitPoints (px, py) r ps = (filter (\(x, y) -> (x^2 + y^2) <= ((px+r)^2 + (py+r)^2)) ps, filter (\(x, y) -> (x^2 + y^2) > ((px+r)^2 + (py+r)^2)) ps)
-- Exercise 4
data BTree = Empty | Node Int BTree BTree
isBinarySearchTree :: BTree -> Bool
isBinarySearchTree Empty = True
isBinarySearchTree (Node n bt1 bt2) = smallerAndBigger bt1 [] [n] && smallerAndBigger bt2 [n] []
where
smallerAndBigger Empty _ _ = True
smallerAndBigger (Node n bt1 bt2) min max = all (n<) max && all (n>=) min && smallerAndBigger bt1 min (n:max) && smallerAndBigger bt2 (n:min) max
-- main
t1 :: BTree -- 8
t1 = Node 8 (Node 3 (Node 1 Empty Empty) -- / \
(Node 4 Empty Empty)) -- 3 10
(Node 10 (Node 9 Empty Empty) -- / \ / \
(Node 14 Empty Empty)) -- 1 4 9 14
t2 :: BTree -- 8
t2 = Node 8 (Node 3 (Node 1 Empty Empty) -- / \
(Node 4 Empty Empty)) -- 3 10
(Node 10 (Node 5 Empty Empty) -- / \ / \
(Node 14 Empty Empty)) -- 1 4 5 14
t3 :: BTree -- 8
t3 = Node 8 (Node 3 (Node 5 Empty Empty) -- / \
(Node 6 Empty Empty)) -- 3 10
(Node 10 (Node 9 Empty Empty) -- / \ / \
(Node 14 Empty Empty)) -- 5 6 9 14
main :: IO()
main = do
print(findNb 1071225) -- --> 45
print(findNb 40539911473216) -- --> 3568
print(findNb 135440716410000) -- --> 4824
print(findNb 4183059834009) -- --> 2022
print(findNb 91716553919377) -- --> -1
print(findNb 24723578342962) -- --> -1
print(dominates (+4) (*2) [1..4]) -- --> True
print(dominates (+4) (*2) [1..5]) -- --> False (5+4=9 < 5*2=10)
print(splitPoints (1,1) 5 [(1,2),(2,3),(10,15),(-1,1),(12,14)]) -- --> ([(1.0,2.0),(2.0,3.0),(-1.0,1.0)],[(10.0,15.0),(12.0,14.0)])
print(isBinarySearchTree t1) -- --> True
print(isBinarySearchTree t2) -- --> False (в дясното поддърво има стойности, по-малки от тази в корена)
print(isBinarySearchTree t3) -- --> False (лявото поддърво не е двоично дърво за търсене)
|
