Clausura respecto del valor absoluto de las diferencias
Dado un conjunto de números enteros positivos S su clausura del valor absoluto de la diferencia de pares es el menor conjunto T tal que T contiene a S y para cualquier par de elementos x e y de T (con x distinto de y) el valor absoluto de (x-y) también es un elemento de T. Por ejemplo, si S = {12, 30}, entonces
- 12 ∈ T, porque 12 ∈ S
- 30 ∈ T, porque 20 ∈ S
- 18 = |12 – 30| ∈ T
- 6 = |18 – 12| ∈ T
- 24 = |30 – 6| ∈ T
Por tanto, T = {12, 30, 18, 6, 24}.
Definir las funciones
|
1 2 |
clausura :: [Int] -> [Int] longitudClausura :: [Int] -> Int |
tales que
- (clausura xs) es la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,
|
1 2 |
clausura [12,30] == [12,30,18,6,24] clausura [3,5,2] == [3,5,2,1,4] |
- (longitudClausura xs) es el número de elementos de la clausura del conjunto de enteros positivos xs respecto del valor absoluto de la diferencia de pares. Por ejemplo,
|
1 2 3 |
longitudClausura [12,30] == 5 longitudClausura [3,5,2] == 5 longitudClausura [3,23..10^6] == 999983 |
Soluciones
|
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 |
import Data.List (nub, sort, union) import Test.QuickCheck -- Definición de clausura -- ====================== clausura :: [Int] -> [Int] clausura xs | contenida ys xs = xs | otherwise = clausura (union xs ys) where ys = diferencias xs -- (diferencias xs) es el conjunto de los valores absolutos de las -- diferencias de pares de elementos distintos de xs. Por ejemplo, -- diferencias [3,7,11] == [4,8] diferencias :: [Int] -> [Int] diferencias xs = nub [x - y | x <- xs , y <- xs , x > y] -- (contenida xs ys) se verifica si la lista xs esta contenida en -- ys. Por ejemplo, -- contenida [2,3] [3,5,2] == True -- contenida [2,3] [3,5,7] == False contenida :: [Int] -> [Int] -> Bool contenida xs ys = all (`elem` ys) xs -- 1ª definición de longitudClausura -- ================================= longitudClausura :: [Int] -> Int longitudClausura = length . clausura -- 2ª definición de longitudClausura -- ================================= -- longitudClausura2 [3,23..10^6] == 999983 longitudClausura2 :: [Int] -> Int longitudClausura2 xs = maximum xs `div` mcd xs -- (mcd xs) es el máximo común divisor de los elememtos de xs. Por -- ejemplo, -- mcd [12, 60] == 12 -- mcd [12, 60, 42] == 6 mcd :: [Int] -> Int mcd = foldl1 gcd -- Equivalencia -- ============ -- La propiedd de equivalencia es prop_clausura :: [Int] -> Property prop_clausura xs = not (null xs) ==> longitudClausura ys == longitudClausura2 ys where ys = nub (map ((+1) . abs) xs) -- La comprobación es -- λ> quickCheck prop_clausura -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> longitudClausura [3,23..10^3] -- 983 -- (2.22 secs, 239,761,904 bytes) -- λ> longitudClausura2 [3,23..10^3] -- 983 -- (0.01 secs, 118,968 bytes) |