-
Notifications
You must be signed in to change notification settings - Fork 0
/
examen_2_5_dic.hs
223 lines (189 loc) · 7.74 KB
/
examen_2_5_dic.hs
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
-- Informática (1º del Grado en Matemáticas, Grupo 1)
-- 2º examen de evaluación continua (5 de diciembre de 2017)
-- ---------------------------------------------------------------------
-- Nota: La puntuación de cada ejercicio es 2.5 puntos.
-- ---------------------------------------------------------------------
-- § Librerías --
-- ---------------------------------------------------------------------
import Data.List
import Data.Maybe
import Test.QuickCheck
-- ---------------------------------------------------------------------
-- Ejercico 1. Definir la función
-- sublistasSuma :: (Num a, Eq a) => [a] -> a -> [[a]]
-- tal que (sublistasSuma xs m) es la lista de sublistas de xs cuya suma
-- es m. Por ejemplo,
-- sublistasSuma [1..5] 10 == [[2,3,5],[1,4,5],[1,2,3,4]]
-- sublistasSuma [1..5] 23 == []
-- length (sublistasSuma [1..20] 145) == 5337
-- ---------------------------------------------------------------------
-- 1ª solución (por orden superior):
sublistasSuma1 :: (Num a, Eq a) => [a] -> a -> [[a]]
sublistasSuma1 xs m = filter ((==m) . sum) (subsequences xs)
-- 2ª solución (por recursión:
sublistasSuma2 :: [Int] -> Int -> [[Int]]
sublistasSuma2 xs = aux (sort xs)
where aux [] m = []
aux (y:ys) m | y == m = [[m]]
| y > m = []
| otherwise = aux ys m ++ map (y:) (aux ys (m-y))
-- ---------------------------------------------------------------------
-- Ejercicio 2.1. La sucesión de Padovan es la secuencia de números
-- enteros P(n) definida por los valores iniciales
-- P(0) = P(1) = P( 2) = 1,
-- y por la relación
-- P (n) = P(n−2) + P(n−3) .
--
-- Los primeros valores de P(n) son
-- 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37,...
--
-- Definir la funciones
-- padovan :: Int -> Integer
-- sucPadovan :: [Integer]
-- tales que
-- sucPadovan es la sucesión así construida, y
-- (padovan n) es el término n-simo de la sucesión
-- Por ejemplo,
-- padovan 10 == 12
-- padovan 100 == 1177482265857
-- length $ show $ padovan 1000 == 122
-- take 14 sucPadovan == [1,1,1,2,2,3,4,5,7,9,12,16,21,28]
-- ---------------------------------------------------------------------
-- 1ª solución
-- ===========
padovan1 :: Int -> Integer
padovan1 n | n <= 2 = 1
| otherwise = padovan1 (n-2) + padovan1 (n-3)
sucPadovan1 :: [Integer]
sucPadovan1 = map padovan1 [0..]
-- 2ª solución
-- ===========
sucPadovan2 :: [Integer]
sucPadovan2 = 1:1:1: zipWith (+) sucPadovan2 (tail sucPadovan2)
padovan2 :: Int -> Integer
padovan2 n = sucPadovan2 `genericIndex` n
-- Comparación de eficiencia
-- =========================
-- ghci> sucPadovan1 !! 60
-- 15346786
-- (12.53 secs, 6,752,729,800 bytes)
-- ghci> sucPadovan2 !! 60
-- 15346786
-- (0.00 secs, 152,648 bytes)
-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Comprobar con QuickCheck la siguiente propiedad:
-- n
-- ---
-- \
-- / P(j) = P(n+4) - 2
-- ---
-- j=0
-- ---------------------------------------------------------------------
-- La propiedad es
propPadovan :: Int -> Bool
propPadovan n = sum (take m sucPadovan2) == padovan2 (m+4) - 2
where m = abs n
-- La comprobación es
-- ghci> quickCheck propPadovan
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 3. Los árboles con un número variable de sucesores se
-- pueden representar mediante el siguiente tipo de dato
-- data Arbol a = N a [Arbol a]
-- deriving Show
-- Por ejemplo, los árboles
-- 1 1 1
-- / \ / \ / \
-- 8 3 8 3 8 3
-- | /|\ /|\ |
-- 4 4 5 6 4 5 6 7
-- se representan por
-- ej1, ej2, ej3 :: Arbol Int
-- ej1 = N 1 [N 8 [],N 3 [N 4 []]]
-- ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]]
-- ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]
--
-- Definir la función
-- caminosDesdeRaiz :: Arbol a -> [[a]]
-- tal que (caminosDesdeRaiz x) es la lista de todos los caminos desde
-- la raiz. Por ejemplo,
-- caminosDesdeRaiz ej1 == [[1,8],[1,3,4]]
-- caminosDesdeRaiz ej2 == [[1,8],[1,3,4],[1,3,5],[1,3,6]]
-- caminosDesdeRaiz ej3 == [[1,8,4],[1,8,5],[1,8,6],[1,3,7]]
-- ---------------------------------------------------------------------
data Arbol a = N a [Arbol a]
deriving Show
ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 8 [],N 3 [N 4 []]]
ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]]
ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]
caminosDesdeRaiz :: Arbol a -> [[a]]
caminosDesdeRaiz (N r []) = [[r]]
caminosDesdeRaiz (N r as) = map (r:) (concatMap caminosDesdeRaiz as)
-- ---------------------------------------------------------------------
-- Ejercicio 4.1. La lista [7, 10, 12, 1, 2, 4] no está ordenada, pero si
-- consideramos las listas que se pueden formar cíclicamente a partir de
-- cada elemento, obtenemos:
-- [7, 10, 12, 1, 2, 4]
-- [10, 12, 1, 2, 4, 7]
-- [12, 1, 2, 4, 7, 10]
-- [1, 2, 4, 7, 10, 12] ** ordenada **
-- [2, 4, 7, 10, 12, 1]
-- [4, 7, 10, 12, 1, 2]
-- Se observa que una de ellas está ordenada.
--
-- Se dice que una lista [x(0), ..., x(n)] es cíclicamente ordenable
-- si existe un índice i tal que la lista
-- [x(i), x(i+1), ..., x(n), x(0), ..., x(i-1)]
-- está ordenada.
--
-- Definir la función
-- ciclicamenteOrdenable :: Ord a => [a] -> Bool
-- tal que (ciclicamenteOrdenable xs) se verifica si xs es una lista
-- cíclicamente ordenable. Por ejemplo,
-- ciclicamenteOrdenable [7,10,12,1,2,4] == True
-- ciclicamenteOrdenable [7,20,12,1,2,4] == False
-- ---------------------------------------------------------------------
ciclicamenteOrdenable :: Ord a => [a] -> Bool
ciclicamenteOrdenable xs =
any ordenada (zipWith (++) (tails xs) (inits xs))
ordenada :: Ord a => [a] -> Bool
ordenada xs = and (zipWith (<=) xs (tail xs))
-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Definir la función
-- posicionOC :: Ord a => [a] -> Maybe Int
-- tal que (posicionOC xs) es (Just i) si i es el índice a partir del
-- cual la lista xs está ordenada cíclicamente; o bien Nothing, en caso
-- contrario. Por ejemplo,
-- posicionOC [7,10,12,1,2,4] == Just 3
-- posicionOC [4,5,6,1,2,3] == Just 3
-- posicionOC [4,5,6,1,2,3,7] == Nothing
-- posicionOC ([10^3..10^4] ++ [1..999]) == Just 9001
-- ---------------------------------------------------------------------
-- 1ª solución
-- ===========
posicionOC :: Ord a => [a] -> Maybe Int
posicionOC xs | null is = Nothing
| otherwise = Just (head is)
where is = ciclosOrdenados xs
-- (cicloOrdenado xs i) se verifica si el ciclo i-ésimo de xs está
-- ordenado; es decir, si
-- [x(i), x(i+1), ..., x(n), x(0), ..., x(i-1)]
-- está ordenado. Por ejemplo,
-- cicloOrdenado [4,5,6,1,2,3] 3 == True
-- cicloOrdenado [4,5,6,1,2,3] 2 == False
-- cicloOrdenado [4,5,6,1,2,3] 4 == False
cicloOrdenado :: Ord a => [a] -> Int -> Bool
cicloOrdenado xs i = ordenada (drop i xs ++ take i xs)
-- (ciclosOrdenados xs) es el conjunto de índices i tales que el ciclo
-- i-ésimo de xs está ordenado. Por ejemplo,
-- ciclosOrdenados [7,10,12,1,2,4] == [3]
-- ciclosOrdenados [7,20,12,1,2,4] == []
ciclosOrdenados :: Ord a => [a] -> [Int]
ciclosOrdenados xs =
[i | i <- [0..length xs - 1]
, cicloOrdenado xs i]
-- 2ª solución
-- ===========
posicionOC2 :: Ord a => [a] -> Maybe Int
posicionOC2 = listToMaybe . ciclosOrdenados