El factorial de 7 es
|
1 |
7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040 |
por tanto, el último dígito no nulo del factorial de 7 es 4.
Definir la función
|
1 |
ultimoNoNuloFactorial :: Integer -> Integer |
tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,
|
1 2 3 4 5 |
ultimoNoNuloFactorial 7 == 4 ultimoNoNuloFactorial 10 == 8 ultimoNoNuloFactorial 12 == 6 ultimoNoNuloFactorial 97 == 2 ultimoNoNuloFactorial 0 == 1 |
Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.
|
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 |
import Data.Char (digitToInt) import Test.QuickCheck -- 1ª solución -- =========== ultimoNoNuloFactorial :: Integer -> Integer ultimoNoNuloFactorial = ultimoNoNulo . factorial -- (factorial n) es el factorial de n. Por ejemplo, -- factorial 7 == 5040 factorial :: Integer -> Integer factorial n = product [1..n] -- (ultimoNoNulo n) es el último dígito no nulo de n. Por ejemplo, -- ultimoNoNulo 5040 == 4 ultimoNoNulo :: Integer -> Integer ultimoNoNulo n | r /= 0 = r | otherwise = ultimoNoNulo q where (q,r) = n `quotRem` 10 -- 2ª solución -- =========== ultimoNoNuloFactorial2 :: Integer -> Integer ultimoNoNuloFactorial2 = last . filter (/= 0) . digitos . factorial digitos :: Integer -> [Integer] digitos n = [read [x] | x <- show n] -- 3ª solución -- =========== ultimoNoNuloFactorial3 :: Integer -> Integer ultimoNoNuloFactorial3 = last . filter (/= 0) . digitos3 . factorial3 digitos3 :: Integer -> [Integer] digitos3 = map (fromIntegral . digitToInt) . show factorial3 :: Integer -> Integer factorial3 = product . enumFromTo 1 -- 4ª solución -- =========== ultimoNoNulo4 :: Integer -> Integer ultimoNoNulo4 n = read [head (dropWhile (=='0') (reverse (show n)))] -- 5ª solución -- =========== ultimoNoNulo5 :: Integer -> Integer ultimoNoNulo5 = read . return . head . dropWhile ('0' ==) . reverse . show -- Propiedad -- ========= -- La propiedad es prop_ultimoNoNuloFactorial :: Integer -> Property prop_ultimoNoNuloFactorial n = n > 4 ==> even (ultimoNoNuloFactorial n) -- La comprobación es -- ghci> quickCheck prop_ultimoNoNuloFactorial -- +++ OK, passed 100 tests. |
Busca el tu esencial,
que no está en ninguna parte
y en todas partes está.Antonio Machado
La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por
Los primeros términos de las primeras sucesiones de Loomis son
Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,
Definir las siguientes funciones
|
1 2 3 |
sucLoomis :: Integer -> [Integer] convergencia :: Integer -> Integer graficaConvergencia :: [Integer] -> IO () |
tales que
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
λ> take 15 (sucLoomis 1) [1,2,4,8,16,22,26,38,62,74,102,104,108,116,122] λ> take 15 (sucLoomis 2) [2,4,8,16,22,26,38,62,74,102,104,108,116,122,126] λ> take 15 (sucLoomis 3) [3,6,12,14,18,26,38,62,74,102,104,108,116,122,126] λ> take 15 (sucLoomis 4) [4,8,16,22,26,38,62,74,102,104,108,116,122,126,138] λ> take 15 (sucLoomis 5) [5,10,11,12,14,18,26,38,62,74,102,104,108,116,122] λ> take 15 (sucLoomis 20) [20,22,26,38,62,74,102,104,108,116,122,126,138,162,174] λ> take 15 (sucLoomis 100) [100,101,102,104,108,116,122,126,138,162,174,202,206,218,234] λ> sucLoomis 1 !! (2*10^5) 235180736652 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
convergencia 2 == 2 convergencia 3 == 26 convergencia 4 == 4 convergencia 17 == 38 convergencia 19 == 102 convergencia 43 == 162 convergencia 27 == 202 convergencia 58 == 474 convergencia 63 == 150056 convergencia 81 == 150056 convergencia 89 == 150056 convergencia (10^12) == 1000101125092 |
|
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 |
import Data.List ((\\)) import Data.Char (digitToInt) import Graphics.Gnuplot.Simple (plotList, Attribute (Key, Title, XRange, PNG)) -- 1ª definición de sucLoomis -- ========================== sucLoomis :: Integer -> [Integer] sucLoomis x = map (loomis x) [0..] loomis :: Integer -> Integer -> Integer loomis x 0 = x loomis x n = y + productoDigitosNoNulos y where y = loomis x (n-1) productoDigitosNoNulos :: Integer -> Integer productoDigitosNoNulos = product . digitosNoNulos digitosNoNulos :: Integer -> [Integer] digitosNoNulos x = [read [c] | c <- show x, c /= '0'] -- 2ª definición de sucLoomis -- ========================== sucLoomis2 :: Integer -> [Integer] sucLoomis2 = iterate siguienteLoomis siguienteLoomis :: Integer -> Integer siguienteLoomis y = y + productoDigitosNoNulos y -- 3ª definición de sucLoomis -- ========================== sucLoomis3 :: Integer -> [Integer] sucLoomis3 = iterate ((+) <*> product . map (toInteger . digitToInt) . filter (/= '0') . show) -- Comparación de eficiencia -- ========================= -- λ> sucLoomis 1 !! 30000 -- 6571272766 -- (2.45 secs, 987,955,944 bytes) -- λ> sucLoomis2 1 !! 30000 -- 6571272766 -- (2.26 secs, 979,543,328 bytes) -- λ> sucLoomis3 1 !! 30000 -- 6571272766 -- (0.31 secs, 88,323,832 bytes) -- 1ª definición de convergencia -- ============================= convergencia1 :: Integer -> Integer convergencia1 x = head (dropWhile noEnSucLoomisDe1 (sucLoomis x)) noEnSucLoomisDe1 :: Integer -> Bool noEnSucLoomisDe1 x = not (pertenece x sucLoomisDe1) sucLoomisDe1 :: [Integer] sucLoomisDe1 = sucLoomis 1 pertenece :: Integer -> [Integer] -> Bool pertenece x ys = x == head (dropWhile (<x) ys) -- 2ª definición de convergencia -- ============================= convergencia2 :: Integer -> Integer convergencia2 = aux (sucLoomis3 1) . sucLoomis3 where aux as@(x:xs) bs@(y:ys) | x == y = x | x < y = aux xs bs | otherwise = aux as ys -- 3ª definición de convergencia -- ============================= convergencia3 :: Integer -> Integer convergencia3 = head . interseccion (sucLoomis3 1) . sucLoomis3 -- (interseccion xs ys) es la intersección entre las listas ordenadas xs -- e ys. Por ejemplo, -- λ> take 10 (interseccion (sucLoomis3 1) (sucLoomis3 2)) -- [2,4,8,16,22,26,38,62,74,102] interseccion :: Ord a => [a] -> [a] -> [a] interseccion = aux where aux as@(x:xs) bs@(y:ys) = case compare x y of LT -> aux xs bs EQ -> x : aux xs ys GT -> aux as ys aux _ _ = [] -- 4ª definición de convergencia -- ============================= convergencia4 :: Integer -> Integer convergencia4 x = perteneceA (sucLoomis3 x) 1 where perteneceA (y:ys) n | y == c = y | otherwise = perteneceA ys c where c = head $ dropWhile (< y) $ sucLoomis3 n -- Comparación de eficiencia -- ========================= -- λ> convergencia1 (10^4) -- 150056 -- (2.94 secs, 1,260,809,808 bytes) -- λ> convergencia2 (10^4) -- 150056 -- (0.03 secs, 700,240 bytes) -- λ> convergencia3 (10^4) -- 150056 -- (0.03 secs, 1,165,496 bytes) -- λ> convergencia4 (10^4) -- 150056 -- (0.02 secs, 1,119,648 bytes) -- -- λ> convergencia2 (10^12) -- 1000101125092 -- (1.81 secs, 714,901,080 bytes) -- λ> convergencia3 (10^12) -- 1000101125092 -- (1.92 secs, 744,932,184 bytes) -- λ> convergencia4 (10^12) -- 1000101125092 -- (1.82 secs, 941,053,328 bytes) -- Definición de graficaConvergencia -- ================================== graficaConvergencia :: [Integer] -> IO () graficaConvergencia xs = plotList [ Key Nothing , Title "Convergencia de sucesiones de Loomis" , XRange (fromIntegral (minimum xs),fromIntegral (maximum xs)) , PNG "Las_sucesiones_de_Loomis_2.png" ] [(x,convergencia2 x) | x <- xs] |
Era una noche del mes
de mayo, azul y serena.
Sobre el agudo ciprés
brillaba la luna llena.Antonio Machado
Definir la función
|
1 |
mayorProducto :: Int -> Integer -> Integer |
tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,
|
1 2 3 4 5 6 7 |
mayorProducto 2 325 == 10 mayorProducto 5 11111 == 1 mayorProducto 5 113111 == 3 mayorProducto 5 110111 == 0 mayorProducto 5 10151112 == 10 mayorProducto 5 101511124 == 10 mayorProducto 5 (product [1..1000]) == 41472 |
|
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 |
import Test.QuickCheck import Data.List (inits, tails) import Data.Char (digitToInt) -- 1ª solución -- =========== mayorProducto1 :: Int -> Integer -> Integer mayorProducto1 n x = maximum [product xs | xs <- segmentos n (cifras x)] -- (cifras x) es la lista de las cifras del número x. Por ejemplo, -- cifras 325 == [3,2,5] cifras :: Integer -> [Integer] cifras x = map (toInteger . digitToInt) (show x) -- (segmentos n xs) es la lista de los segmentos de longitud n de la -- lista xs. Por ejemplo, -- segmentos 2 [3,5,4,6] == [[3,5],[5,4],[4,6]] segmentos :: Int -> [Integer] -> [[Integer]] segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs)) -- 2ª solución -- =========== mayorProducto2 :: Int -> Integer -> Integer mayorProducto2 n x = maximum (aux ns) where ns = [read [d] | d <- show x] aux xs | length xs < n = [] | otherwise = product (take n xs) : aux (tail xs) -- 3ª solución -- =========== mayorProducto3 :: Int -> Integer -> Integer mayorProducto3 n = maximum . map (product . take n) . filter ((>=n) . length) . tails . cifras -- 4ª solución -- =========== mayorProducto4 :: Int -> Integer -> Integer mayorProducto4 n = maximum . map (product . map (fromIntegral . digitToInt)) . filter ((==n) . length) . concatMap inits . tails . show -- --------------------------------------------------------------------- -- Comparación de soluciones -- -- --------------------------------------------------------------------- -- Tiempo (en segundos) del cálculo de (mayorProducto 5 (product [1..n])) -- -- | Def | 500 | 1000 | 5000 | 10000 -- | 1 | 0.01 | 0.02 | 0.06 | 0.11 -- | 2 | 0.01 | 0.03 | 0.80 | 3.98 -- | 3 | 0.01 | 0.03 | 0.82 | 4.13 -- | 4 | 2.77 | | | |
A las palabras de amor
les sienta bien su poquito
de exageración.Antonio Machado
Definir la función
|
1 |
productos :: Integer -> Integer -> [[Integer]] |
tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,
|
1 2 3 4 |
productos 2 6 == [[2,3]] productos 3 6 == [[1,2,3]] productos 4 1680 == [[5,6,7,8]] productos 2 5 == [] |
Comprobar con QuickCheck que si n > 0 y x > 0, entonces
|
1 |
productos n (product [x..x+n-1]) == [[x..x+n-1]] |
Usando productos, definir la función
|
1 |
productosDe2y3consecutivos :: [Integer] |
cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,
|
1 |
head productosDe2y3consecutivos == 6 |
Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.
|
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 |
import Test.QuickCheck -- 1ª solución -- =========== productos1 :: Integer -> Integer -> [[Integer]] productos1 n x = [[y..y+n-1] | y <- [1..x] , product [y..y+n-1] == x] -- 2ª solución -- =========== productos2 :: Integer -> Integer -> [[Integer]] productos2 n x = [[z..z+n-1] | z <- [1..y] , product [z..z+n-1] == x] where y = head (filter (\y -> y^n >= x) [2..]) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> let (n,x) = (3,200) in productos1 n (product [x..x+n-1]) -- [[200,201,202]] -- (7.38 secs, 7,235,956,440 bytes) -- λ> let (n,x) = (3,200) in productos2 n (product [x..x+n-1]) -- [[200,201,202]] -- (0.01 secs, 451,928 bytes) -- -- λ> productos2 3 1000018000107000210 -- [[1000005,1000006,1000007]] -- (1.57 secs, 1,560,159,144 bytes) -- En lo que sigue se usa la 2ª definición productos :: Integer -> Integer -> [[Integer]] productos = productos2 -- La propiedad es prop_productos :: Integer -> Integer -> Property prop_productos n x = n > 0 && x > 0 ==> productos n (product [x..x+n-1]) == [[x..x+n-1]] -- La comprobación es -- λ> quickCheck prop_productos -- +++ OK, passed 100 tests. productosDe2y3consecutivos :: [Integer] productosDe2y3consecutivos = [x | x <- [1..] , let ys = productos 2 x , not (null ys) , let zs = productos 3 x , not (null zs)] -- El cálculo es -- λ> take 2 productosDe2y3consecutivos -- [6,210] |
Mis ojos en el espejo
son ojos ciegos que miran
los ojos con que los veo.Antonio Machado
Un segmento de una lista xs es una sublista de xs formada por elementos consecutivos en la lista. El problema de la máxima suma de segmentos consiste en dada una lista de números enteros calcular el máximo de las sumas de todos los segmentos de la lista. Por ejemplo, para la lista [-1,2,-3,5,-2,1,3,-2,-2,-3,6] la máxima suma de segmentos es 7 que es la suma del segmento [5,-2,1,3] y para la lista [-1,-2,-3] es 0 que es la suma de la lista vacía.
Definir la función
|
1 |
mss :: [Integer] -> Integer |
tal que (mss xs) es la máxima suma de los segmentos de xs. Por ejemplo,
|
1 2 3 4 5 6 |
mss [-1,2,-3,5,-2,1,3,-2,-2,-3,6] == 7 mss [-1,-2,-3] == 0 mss [1..500] == 125250 mss [1..1000] == 500500 mss [-500..3] == 6 mss [-1000..3] == 6 |
|
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 (inits,tails) -- 1ª solución mss :: [Integer] -> Integer mss = maximum . map sum . segmentos -- (segmentos xs) es la lista de los segmentos de xs. Por ejemplo, -- ghci> segmentos "abc" -- ["","a","ab","abc","","b","bc","","c",""] segmentos :: [a] -> [[a]] segmentos = concat . map inits . tails -- 2ª definición: mss2 :: [Integer] -> Integer mss2 = maximum . map (maximum . scanl (+) 0) . tails -- 3ª definición: mss3 :: [Integer] -> Integer mss3 = maximum . map sum . concatMap tails . inits -- 4ª definición mss4 :: [Integer] -> Integer mss4 = fst . foldr (\x (b,a) -> (max (a+x) b, max 0 (a+x))) (0,0) -- 5ª definición (con scanl): mss5 :: [Integer] -> Integer mss5 = maximum . scanl (\a x -> max 0 a + x) 0 -- Comparación de eficiencia -- ========================= -- ghci> mss [1..500] -- 125250 -- (7.52 secs, 2022130824 bytes) -- -- ghci> mss2 [1..500] -- 125250 -- (0.01 secs, 10474956 bytes) -- -- ghci> mss3 [1..500] -- 125250 -- (0.98 secs, 841862016 bytes) -- -- ghci> mss4 [1..500] -- 125250 -- (0.01 secs, 552252 bytes) -- -- ghci> mss2 [1..1000] -- 500500 -- (0.06 secs, 54575712 bytes) -- -- ghci> mss3 [1..1000] -- 500500 -- (7.87 secs, 7061347900 bytes) -- -- ghci> mss4 [1..1000] -- 500500 -- (0.01 secs, 549700 bytes) -- -- ghci> mss2 [1..2000] -- 2001000 -- (0.29 secs, 216424336 bytes) -- -- ghci> mss2 [1..5000] -- 12502500 -- (2.37 secs, 1356384840 bytes) -- -- ghci> mss4 [1..5000] -- 12502500 -- (0.02 secs, 1913548 bytes) -- -- ghci> mss5 [1..5000] -- 12502500 -- (0.01 secs, 2886360 bytes) |
Nubes, sol, prado verde y caserío
en la loma, revueltos. Primavera
puso en el aire de este campo frío
la gracia de sus chopos de ribera.Antonio Machado
Una serie de potencias es una serie de la forma
|
1 |
a₀ + a₁x + a₂x² + a₃x³ + ... |
Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es
|
1 |
e^x = 1 + x + x²/2! + x³/3! + ... |
y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, …]
Las operaciones con series se pueden ver como una generalización de las de los polinomios.
En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es
|
1 |
type Serie a = [a] |
Definir las siguientes funciones
|
1 2 3 4 5 6 7 8 |
opuesta :: Num a => Serie a -> Serie a suma :: Num a => Serie a -> Serie a -> Serie a resta :: Num a => Serie a -> Serie a -> Serie a producto :: Num a => Serie a -> Serie a -> Serie a cociente :: Fractional a => Serie a -> Serie a -> Serie a derivada :: (Num a, Enum a) => Serie a -> Serie a integral :: (Fractional a, Enum a) => Serie a -> Serie a expx :: Serie Rational |
tales que
|
1 2 |
λ> take 7 (opuesta [-6,-4..]) [6,4,2,0,-2,-4,-6] |
|
1 2 |
λ> take 7 (suma [1,3..] [2,4..]) [3,7,11,15,19,23,27] |
|
1 2 3 4 |
λ> take 7 (resta [3,5..] [2,4..]) [1,1,1,1,1,1,1] λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..]) [2,4,6,8,10,12,14] |
|
1 2 |
λ> take 7 (producto [3,5..] [2,4..]) [6,22,52,100,170,266,392] |
|
1 2 |
λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..]) [2.0,4.0,6.0,8.0,10.0,12.0,14.0] |
|
1 2 |
λ> take 7 (derivada [2,4..]) [4,12,24,40,60,84,112] |
|
1 2 |
λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0)) [0.0,4.0,6.0,8.0,10.0,12.0,14.0] |
|
1 2 3 4 5 6 |
λ> take 8 expx [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040] λ> take 8 (derivada expx) [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040] λ> take 8 (integral expx) [0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040] |
|
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 |
type Serie a = [a] opuesta :: Num a => Serie a -> Serie a opuesta = map negate suma :: Num a => Serie a -> Serie a -> Serie a suma = zipWith (+) resta :: Num a => Serie a -> Serie a -> Serie a resta xs ys = suma xs (opuesta ys) producto :: Num a => Serie a -> Serie a -> Serie a producto (x:xs) zs@(y:ys) = x*y : suma (producto xs zs) (map (x*) ys) cociente :: Fractional a => Serie a -> Serie a -> Serie a cociente (x:xs) (y:ys) = zs where zs = x/y : map (/y) (resta xs (producto zs ys)) derivada :: (Num a, Enum a) => Serie a -> Serie a derivada (_:xs) = zipWith (*) xs [1..] integral :: (Fractional a, Enum a) => Serie a -> Serie a integral xs = 0 : zipWith (/) xs [1..] expx :: Serie Rational expx = map (1/) (map fromIntegral factoriales) -- factoriales es la lista de los factoriales. Por ejemplo, -- take 7 factoriales == [1,1,2,6,24,120,720] factoriales :: [Integer] factoriales = 1 : scanl1 (*) [1..] |
Ni mármol duro y eterno,
ni música ni pintura,
sino palabra en el tiempo.Antonio Machado
Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:
Por ejemplo, para n = 5
|
1 2 3 4 5 6 7 |
Pase | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5 Inicial | Cerrada | Cerrada | Cerrada | Cerrada | Cerrada Pase 1 | Abierta | Abierta | Abierta | Abierta | Abierta Pase 2 | Abierta | Cerrada | Abierta | Cerrada | Abierta Pase 3 | Abierta | Cerrada | Cerrada | Cerrada | Abierta Pase 4 | Abierta | Cerrada | Cerrada | Abierta | Abierta Pase 5 | Abierta | Cerrada | Cerrada | Abierta | Cerrada |
Los estados de las puertas se representan por el siguiente tipo de datos
|
1 |
data Estado = Abierta | Cerrada deriving Show |
Definir la función
|
1 |
final :: Int -> [Estado] |
tal que (final n) es la lista de los estados de las n puertas después de que hayan pasado los n camareros. Por ejemplo,
|
1 2 3 4 |
ghci> final 5 [Abierta,Cerrada,Cerrada,Abierta,Cerrada] ghci> final 7 [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada] |
|
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 |
-- 1ª solución -- =========== data Estado = Abierta | Cerrada deriving (Eq, Show) cambia Abierta = Cerrada cambia Cerrada = Abierta -- (inicial n) es el estado inicial para el problema de las n -- habitaciones. Por ejemplo, -- inicial 5 == [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada] inicial :: Int -> [Estado] inicial n = replicate n Cerrada -- (pase k es) es la lista de los estados de las puertas después de pasar el -- camarero k que las encuentra en los estados es. Por ejemplo, -- ghci> pase 1 (inicial 5) -- [Abierta,Abierta,Abierta,Abierta,Abierta] -- ghci> pase 2 it -- [Abierta,Cerrada,Abierta,Cerrada,Abierta] -- ghci> pase 3 it -- [Abierta,Cerrada,Cerrada,Cerrada,Abierta] -- ghci> pase 4 it -- [Abierta,Cerrada,Cerrada,Abierta,Abierta] -- ghci> pase 5 it -- [Abierta,Cerrada,Cerrada,Abierta,Cerrada] pase :: [Estado] -> Int -> [Estado] pase es k = zipWith cambiaK es[1..] where cambiaK e n | n `mod` k == 0 = cambia e | otherwise = e final :: Int -> [Estado] final n = aux [1..n] (inicial n) where aux [] es = es aux (k:ks) es = aux ks (pase es k) -- 2ª solución -- =========== final2 :: Int -> [Estado] final2 n = foldl pase (inicial n) [1..n] -- 3ª solución -- ============= final3 :: Int -> [Estado] final3 n = map f [1..n] where f x | even (length (divisores x)) = Cerrada | otherwise = Abierta divisores :: Int -> [Int] divisores n = [x | x <- [1..n], n `mod` x == 0] -- 4ª solución -- =========== -- En primer lugar, vamos a determinar la lista de las posiciones -- (comenzando a contar en 1) de las puertas que quedan abierta en el -- problema de las n puertas. posicionesAbiertas :: Int -> [Int] posicionesAbiertas n = [x | (x,y) <- zip [1..] (final n), y == Abierta] -- Al calcularlas, -- ghci> posicionesAbiertas 200 -- [1,4,9,16,25,36,49,64,81,100,121,144,169,196] -- Se observa las que quedan abiertas son las que sus posiciones son -- cuadrados perfectos. Usando esta observación se construye la -- siguiente definición final4 :: Int -> [Estado] final4 n = aux [1..n] [k*k | k <- [1..]] where aux (x:xs) (y:ys) | x == y = Abierta : aux xs ys aux (x:xs) ys = Cerrada : aux xs ys aux [] _ = [] -- --------------------------------------------------------------------- -- § Comparación de eficiencia -- -- --------------------------------------------------------------------- -- ghci> last (final 1000) -- Cerrada -- (0.23 secs, 218727400 bytes) -- ghci> last (final 2000) -- Cerrada -- (1.78 secs, 868883080 bytes) -- ghci> last (final2 1000) -- Cerrada -- (0.08 secs, 218729392 bytes) -- ghci> last (final2 2000) -- Cerrada -- (1.77 secs, 868948600 bytes) -- ghci> last (final3 1000) -- Cerrada -- (0.01 secs, 1029256 bytes) -- ghci> last (final3 2000) -- Cerrada -- (0.01 secs, 2121984 bytes) -- ghci> last (final4 1000) -- Cerrada -- (0.01 secs, 1029328 bytes) -- ghci> last (final4 2000) -- Cerrada -- (0.01 secs, 1578504 bytes) -- ghci> last (final3 10000) -- Abierta -- (0.01 secs, 4670104 bytes) -- ghci> last (final3 100000) -- Cerrada -- (0.09 secs, 38717032 bytes) -- ghci> last (final3 1000000) -- Abierta -- (1.27 secs, 377100832 bytes) -- ghci> last (final4 1000000) -- Abierta -- (1.41 secs, 273292448 bytes) |
… cuánto exilio en la presencia cabe.
Antonio Machado
El sistema D’Hondt es una fórmula creada por Victor d’Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.
Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten
Definir la función
|
1 |
reparto :: Int -> [Int] -> [(Int,Int)] |
tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,
|
1 2 3 4 |
ghci> reparto 7 [340000,280000,160000,60000,15000] [(1,3),(2,3),(3,1)] ghci> reparto 21 [391000,311000,184000,73000,27000,12000,2000] [(1,9),(2,7),(3,4),(4,1)] |
es decir, en el primer ejemplo,
|
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 |
import Data.List (sort, group) -- Para los ejemplos que siguen, se usará la siguiente ditribución de -- votos entre 5 partidos. ejVotos :: [Int] ejVotos = [340000,280000,160000,60000,15000] -- 1ª solución -- =========== reparto :: Int -> [Int] -> [(Int,Int)] reparto n vs = [(x,1 + length xs) | (x:xs) <- group (sort (repartoAux n vs))] -- (repartoAux n vs) es el número de los partidos, cuyos votos son vs, que -- obtienen los n escaños. Por ejemplo, -- ghci> repartoAux 7 ejVotos -- [1,2,1,3,2,1,2] repartoAux :: Int -> [Int] -> [Int] repartoAux n vs = map snd (repartoAux' n vs) -- (repartoAux' n vs) es la lista formada por los n restos mayores -- correspondientes a la lista de votos vs. Por ejemplo, -- ghci> repartoAux' 7 ejVotos -- [(340000,1),(280000,2),(170000,1),(160000,3),(140000,2),(113333,1), -- (93333,2)] repartoAux' :: Int -> [Int] -> [(Int,Int)] repartoAux' n vs = take n (reverse (sort (concatMap (restos n) (votosPartidos vs)))) -- (votosPartidos vs) es la lista con los pares formados por los votos y -- el número de cada partido. Por ejemplo, -- ghci> votosPartidos ejVotos -- [(340000,1),(280000,2),(160000,3),(60000,4),(15000,5)] votosPartidos :: [Int] -> [(Int,Int)] votosPartidos vs = zip vs [1..] -- (restos n (x,i)) es la lista obtenidas dividiendo n entre 1, 2,..., n. -- Por ejemplo, -- ghci> restos 5 (340000,1) -- [(340000,1),(170000,1),(113333,1),(85000,1),(68000,1)] restos :: Int -> (Int,Int) -> [(Int,Int)] restos n (x,i) = [(x `div` k,i) | k <- [1..n]] -- 2ª solución -- =========== reparto2 :: Int -> [Int] -> [(Int,Int)] reparto2 n xs = ( map (\x -> (head x, length x)) . group . sort . map snd . take n . reverse . sort ) [(x `div` i, p) | (x,p) <- zip xs [1..], i <- [1..n]] |
Sus cantares llevan
agua de remanso,
que parece quieta.
Y que no lo está;
mas no tiene prisa
por ir a la mar.Antonio Machado
La conjetura de Goldbach afirma que
Todo número entero mayor que 5 se puede escribir como suma de tres números primos.
En este ejercicio consideraremos la variación consistente en exigir que los tres sumandos sean distintos.
Definir las funciones
|
1 2 3 |
sumas3PrimosDistintos :: Int -> [(Int,Int,Int)] conKsumas3PrimosDistintos :: Int -> Int -> [Int] noSonSumas3PrimosDistintos :: Int -> [Int] |
tales que
|
1 2 3 4 |
sumas3PrimosDistintos 26 == [(13,11,2),(17,7,2),(19,5,2)] sumas3PrimosDistintos 18 == [(11,5,2),(13,3,2)] sumas3PrimosDistintos 10 == [(5,3,2)] sumas3PrimosDistintos 11 == [] |
|
1 2 3 4 |
conKsumas3PrimosDistintos 3 99 == [26,27,29,32,36,42,46,48,54,58,60] conKsumas3PrimosDistintos 2 99 == [18,20,21,22,23,24,25,28,30,34,64,70] conKsumas3PrimosDistintos 1 99 == [10,12,14,15,16,19,40] conKsumas3PrimosDistintos 0 99 == [11,13,17] |
|
1 2 |
noSonSumas3PrimosDistintos 99 == [11,13,17] noSonSumas3PrimosDistintos 500 == [11,13,17] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
import Data.Numbers.Primes sumas3PrimosDistintos :: Int -> [(Int,Int,Int)] sumas3PrimosDistintos n = [(a,b,c) | a <- takeWhile (<=n-5) primes , b <- takeWhile (<a) primes , let c = n - a - b , c < b , isPrime c] conKsumas3PrimosDistintos :: Int -> Int -> [Int] conKsumas3PrimosDistintos k n = [x | x <- [10..n] , length (sumas3PrimosDistintos x) == k] noSonSumas3PrimosDistintos :: Int -> [Int] noSonSumas3PrimosDistintos = conKsumas3PrimosDistintos 0 |
En su claro verso
se canta y medita
sin grito ni ceño.Antonio Machado
Como se explica en Create a Twelve-Tone Melody With a Twelve-Tone Matrix una matriz dodecafónica es una matriz de 12 filas y 12 columnas construidas siguiendo los siguientes pasos:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
( 3 1 9 5 4 6 8 7 12 10 11 2 ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) |
|
1 |
(a(1,1) - a(i,1)) = (a(1,i) - a(1,1)) (módulo 12) |
Siguiendo con el ejemplo anterior, la matriz con la 1ª fila y la 1ª columna es
|
1 2 3 4 5 6 7 8 9 10 11 12 |
( 3 1 9 5 4 6 8 7 12 10 11 2 ) ( 5 ) ( 9 ) ( 1 ) ( 2 ) ( 12 ) ( 10 ) ( 11 ) ( 6 ) ( 8 ) ( 7 ) ( 4 ) |
|
1 |
(a(2,j) - a(1,j)) = (a(2,1) - a(1,1)) (módulo 12) |
Siguiendo con el ejemplo anterior, la matriz con la 1ª fila, 1ª columna y 2ª fila es
|
1 2 3 4 5 6 7 8 9 10 11 12 |
( 3 1 9 5 4 6 8 7 12 10 11 2 ) ( 5 3 11 7 6 8 10 9 2 12 1 4 ) ( 9 ) ( 1 ) ( 2 ) ( 12 ) ( 10 ) ( 11 ) ( 6 ) ( 8 ) ( 7 ) ( 4 ) |
|
1 |
(a(i,j) - a(1,j)) = (a(i,1) - a(1,1)) (módulo 12) |
Siguiendo con el ejemplo anterior, la matriz dodecafónica es
|
1 2 3 4 5 6 7 8 9 10 11 12 |
( 3 1 9 5 4 6 8 7 12 10 11 2 ) ( 5 3 11 7 6 8 10 9 2 12 1 4 ) ( 9 7 3 11 10 12 2 1 6 4 5 8 ) ( 1 11 7 3 2 4 6 5 10 8 9 12 ) ( 2 12 8 4 3 5 7 6 11 9 10 1 ) ( 12 10 6 2 1 3 5 4 9 7 8 11 ) ( 10 8 4 12 11 1 3 2 7 5 6 9 ) ( 11 9 5 1 12 2 4 3 8 6 7 10 ) ( 6 4 12 8 7 9 11 10 3 1 2 5 ) ( 8 6 2 10 9 11 1 12 5 3 4 7 ) ( 7 5 1 9 8 10 12 11 4 2 3 6 ) ( 4 2 10 6 5 7 9 8 1 11 12 3 ) |
Definir la función
|
1 |
matrizDodecafonica :: [Int] -> Matrix Int |
tal que (matrizDodecafonica xs) es la matriz dodecafónica cuya primera fila es xs (que se supone que es una permutación de los números del 1 al 12). Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> matrizDodecafonica [3,1,9,5,4,6,8,7,12,10,11,2] ( 3 1 9 5 4 6 8 7 12 10 11 2 ) ( 5 3 11 7 6 8 10 9 2 12 1 4 ) ( 9 7 3 11 10 12 2 1 6 4 5 8 ) ( 1 11 7 3 2 4 6 5 10 8 9 12 ) ( 2 12 8 4 3 5 7 6 11 9 10 1 ) ( 12 10 6 2 1 3 5 4 9 7 8 11 ) ( 10 8 4 12 11 1 3 2 7 5 6 9 ) ( 11 9 5 1 12 2 4 3 8 6 7 10 ) ( 6 4 12 8 7 9 11 10 3 1 2 5 ) ( 8 6 2 10 9 11 1 12 5 3 4 7 ) ( 7 5 1 9 8 10 12 11 4 2 3 6 ) ( 4 2 10 6 5 7 9 8 1 11 12 3 ) |
Comprobar con QuickCheck para toda matriz dodecafónica D se verifican las siguientes propiedades:
Nota: Este ejercicio ha sido propuesto por Francisco J. Hidalgo.
|
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 |
import Data.List import Test.QuickCheck import Data.Matrix -- 1ª solución -- =========== matrizDodecafonica :: [Int] -> Matrix Int matrizDodecafonica xs = matrix 12 12 f where f (1,j) = xs !! (j-1) f (i,1) = modulo12 (2 * f (1,1) - f (1,i)) f (i,j) = modulo12 (f (1,j) + f (i,1) - f (1,1)) modulo12 0 = 12 modulo12 12 = 12 modulo12 x = x `mod` 12 -- 2ª solución -- =========== matrizDodecafonica2 :: [Int] -> Matrix Int matrizDodecafonica2 xs = fromLists (secuencias xs) secuencias :: [Int] -> [[Int]] secuencias xs = [secuencia a xs | a <- inversa xs] inversa :: [Int] -> [Int] inversa xs = map conv (map (\x -> (-x) + 2* (abs a)) xs) where a = head xs secuencia :: Int -> [Int] -> [Int] secuencia n xs = [conv (a+(n-b)) | a <- xs] where b = head xs conv :: Int -> Int conv n | n == 0 = 12 | n < 0 = conv (n+12) | n > 11 = conv (mod n 12) | otherwise = n -- Propiedades -- =========== -- Las propiedades son prop_dodecafonica :: Int -> Property prop_dodecafonica n = n >= 0 ==> all esPermutacion (toLists d) && all (== d!(1,1)) [d!(i,i) | i <- [2..12]] && sum d == 936 where xss = permutations [1..12] k = n `mod` product [1..12] d = matrizDodecafonica (xss !! k) esPermutacion ys = sort ys == [1..12] -- La comprobación es -- λ> quickCheck prop_dodecafonica -- +++ OK, passed 100 tests. |
Como el olivar,
mucho fruto lleva,
poca sombra da.Antonio Machado
La conjetura de Collatz, conocida también como conjetura 3n+1, fue enunciada por Lothar Collatz en 1937 y, hasta la fecha, no se ha resuelto.
La conjetura hace referencia a una propiedad de las sucesiones de Siracusa. La sucesión de Siracusa de un número entero positivo x es la sucesión cuyo primer término es x y el siguiente de un término se obtiene dividiéndolo entre 2, si es par o multiplicándolo por 3 y sumándole 1, si es impar. Por ejemplo, la sucesión de Siracusa de 12 es
|
1 |
12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, .... |
La conjetura de Collatz afirma que para todo número entero positivo x, el 1 pertenece a la sucesión de Siracusa de x.
Definir las funciones
|
1 2 |
siracusa :: Integer -> [Integer] graficaSiracusa :: Int -> [Integer] -> IO () |
tales que
|
1 2 3 4 |
λ> take 20 (siracusa 12) [12,6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4] λ> take 20 (siracusa 22) [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4] |
y (graficaSiracusa 150 [1..1000]) dibuja
Comprobar con QuickCheck la conjetura de Collatz.
|
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 |
import Test.QuickCheck import Graphics.Gnuplot.Simple -- 1ª definición de siracusa -- ========================= siracusa :: Integer -> [Integer] siracusa n | even n = n : siracusa (n `div` 2) | otherwise = n : siracusa (3*n+1) -- 2ª definición de siracusa -- ========================= siracusa2 :: Integer -> [Integer] siracusa2 = iterate siguiente where siguiente x | even x = x `div` 2 | otherwise = 3*x+1 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> siracusa 12 !! (10^6) -- 4 -- (0.55 secs, 362,791,008 bytes) -- λ> siracusa 12 !! (2*10^6) -- 2 -- (1.05 secs, 725,456,376 bytes) -- λ> siracusa2 12 !! (10^6) -- 4 -- (1.66 secs, 647,189,664 bytes) -- λ> siracusa2 12 !! (2*10^6) -- 2 -- (3.11 secs, 1,294,286,792 bytes) -- Definición de graficaSiracusa -- ============================= graficaSiracusa :: Int -> [Integer] -> IO () graficaSiracusa n xs = plotLists [ Key Nothing , PNG "La_conjetura_de_Collatz.png" ] [take n (siracusa x) | x <- xs] -- Comprobación de la conjetura -- ============================ -- La conjetura es conjeturaCollatz :: Positive Integer -> Bool conjeturaCollatz (Positive n) = 1 `elem` siracusa n -- La comprobación es -- λ> quickCheck conjeturaCollatz -- +++ OK, passed 100 tests. |
Que el caminante es suma del camino …
Antonio Machado
Definir la función
|
1 |
numeros :: String -> [Int] |
tal que (numeros cs) es la lista de los números enteros no negativos de la cadena cs. Por ejemplo,
|
1 2 3 4 5 6 |
λ> numeros "Esta cadena tiene 3 numeros: el 16 y el 2019 solamente." [3,16,2019] λ> numeros "Esta cadena tiene 3 numeros naturales: -2 más 2 es 0" [3,2,0] λ> numeros "Esta cadena tiene 1 numero natural: 2.5 no es entereo" [1] |
|
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 |
import Data.Char (isDigit) -- 1ª definición -- ============= numeros :: String -> [Int] numeros cs = map read (filter esNumero (words cs)) -- (esNumero cs) se verifica si la cadena no vacía cs representa -- un número entero. Por ejemplo, -- esNumero "2019" == True -- esNumero "20.9" == False -- esNumero "201a" == False esNumero :: String -> Bool esNumero = all (`elem` ['0'..'9']) -- 2ª solución -- =========== numeros2 :: String -> [Int] numeros2 cs = map read (filter (all isDigit) (words cs)) -- 3ª solución -- =========== numeros3 :: String -> [Int] numeros3 = map read . filter (all isDigit) . words |
Tu profecía, poeta.
— Mañana hablarán los mudos:
el corazón y la piedra.Antonio Machado
Usando la librería Data.Number.CReal, que se instala con
|
1 |
cabal install number |
se pueden calcular el número pi con la precisión que se desee. Por ejemplo,
|
1 2 3 |
λ> import Data.Number.CReal λ> showCReal 60 pi "3.141592653589793238462643383279502884197169399375105820974945" |
importa la librería y calcula el número pi con 60 decimales.
La distribución de las diferencias de los dígitos consecutivos para los 18 primeros n dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son
|
1 |
3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3 |
Las diferencias de sus elementos consecutivos es
|
1 |
2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1 |
y la distribución de sus frecuencias en el intervalo [-9,9] es
|
1 |
0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0 |
es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.
Definir las funciones
|
1 2 |
distribucionDDCpi :: Int -> [Int] graficas :: [Int] -> FilePath -> IO () |
tales que
|
1 2 3 4 5 6 7 8 9 10 |
λ> distribucionDDCpi 18 [0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0] λ> distribucionDDCpi 100 [1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0] λ> distribucionDDCpi 200 [3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0] λ> distribucionDDCpi 1000 [16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8] λ> distribucionDDCpi 5000 [67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47] |
|
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 |
import Data.Number.CReal import Graphics.Gnuplot.Simple import Data.Array -- λ> digitosPi 18 -- [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3] digitosPi :: Int -> [Int] digitosPi n = init [read [c] | c <- (x:xs)] where (x:_:xs) = showCReal n pi -- λ> diferenciasConsecutivos (digitosPi 18) -- [2,-3,3,-4,-4,7,-4,1,2,-2,-3,-1,2,-2,6,1,-1] diferenciasConsecutivos :: Num a => [a] -> [a] diferenciasConsecutivos xs = zipWith (-) xs (tail xs) distribucionDDCpi :: Int -> [Int] distribucionDDCpi = distribucion . diferenciasConsecutivos . digitosPi where distribucion xs = elems (accumArray (+) 0 (-9,9) (zip xs (repeat 1))) graficas :: [Int] -> FilePath -> IO () graficas ns f = plotLists [Key Nothing, PNG f] [puntos n | n <- ns] where puntos :: Int -> [(Int,Int)] puntos n = zip [-9..9] (distribucionDDCpi n) |
Doy consejo, a fuer de viejo:
nunca sigas mi consejo.Antonio Machado
Un número de Aquiles es un número natural n que es potente (es decir, si p es un divisor primo de n, entonces p² también lo es) y no es una potencia perfecta (es decir, no existen números naturales m y k tales que n es igual a m^k). Por ejemplo,
Los primeros números de Aquiles son
|
1 |
72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, ... |
Definir las funciones
|
1 2 3 |
esAquiles :: Integer -> Bool huecosDeAquiles :: [Integer] graficaHuecosDeAquiles :: Int -> IO () |
tales que
|
1 2 3 4 5 |
esAquiles 108 == True esAquiles 360 == False esAquiles 784 == False esAquiles 5425069447 == True esAquiles 5425069448 == True |
|
1 2 |
λ> take 15 huecosDeAquiles [36,92,88,104,40,68,148,27,125,64,104,4,153,27,171] |
|
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 |
import Data.List (group) import Data.Numbers.Primes (primeFactors) import Graphics.Gnuplot.Simple -- Definición de esAquiles -- ======================= esAquiles :: Integer -> Bool esAquiles x = esPotente x && noEsPotenciaPerfecta x -- (esPotente x) se verifica si x es potente. Por ejemplo, -- esPotente 108 == True -- esPotente 360 == False -- esPotente 784 == True esPotente :: Integer -> Bool esPotente x = all (>1) (exponentes x) -- (exponentes x) es la lista de los exponentes en la factorización de -- x. Por ejemplo, -- exponentes 108 == [2,3] -- exponentes 360 == [3,2,1] -- exponentes 784 == [4,2] exponentes :: Integer -> [Int] exponentes x = map length (group (primeFactors x)) -- (noEsPotenciaPerfecta x) se verifica si x no es una potencia -- perfecta. Por ejemplo, -- noEsPotenciaPerfecta 108 == True -- noEsPotenciaPerfecta 360 == True -- noEsPotenciaPerfecta 784 == False noEsPotenciaPerfecta :: Integer -> Bool noEsPotenciaPerfecta x = foldl1 gcd (exponentes x) == 1 -- Definición de huecosDeAquiles -- ============================= huecosDeAquiles :: [Integer] huecosDeAquiles = zipWith (-) (tail aquiles) aquiles -- aquiles es la sucesión de los números de Aquiles. Por ejemplo, -- λ> take 15 aquiles -- [72,108,200,288,392,432,500,648,675,800,864,968,972,1125,1152] aquiles :: [Integer] aquiles = filter esAquiles [2..] -- Definición de graficaHuecosDeAquiles -- ==================================== graficaHuecosDeAquiles :: Int -> IO () graficaHuecosDeAquiles n = plotList [ Key Nothing , PNG "Huecos_de_Aquiles.png" ] (take n huecosDeAquiles) |
Tengo a mis amigos
en mi soledad;
cuando estoy con ellos
¡qué lejos están!Antonio Machado
El árbol binario de los divisores de 90 es
|
1 2 3 4 5 6 7 |
90 /\ 2 45 /\ 3 15 /\ 3 5 |
Se puede representar por
|
1 |
N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5))) |
usando el tipo de dato definido por
|
1 2 3 |
data Arbol = H Int | N Int Arbol Arbol deriving (Eq, Show) |
Análogamente se obtiene el árbol binario de cualquier número x: se comienza en x y en cada paso se tiene dos hijos (su menor divisor y su cociente) hasta obtener números primos en las hojas.
Definir las funciones
|
1 2 |
arbolDivisores :: Int -> Arbol hojasArbolDivisores :: Int -> [Int] |
tales que
|
1 2 3 4 5 6 |
λ> arbolDivisores 90 N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5))) λ> arbolDivisores 24 N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3))) λ> arbolDivisores 300 N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5)))) |
|
1 2 3 |
hojasArbolDivisores 90 == [2,3,3,5] hojasArbolDivisores 24 == [2,2,2,3] hojasArbolDivisores 300 == [2,2,3,5,5] |
|
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 |
import Data.Numbers.Primes (primeFactors) data Arbol = H Int | N Int Arbol Arbol deriving (Eq, Show) -- Definición de arbolDivisores -- ============================ arbolDivisores :: Int -> Arbol arbolDivisores x | y == x = H x | otherwise = N x (H y) (arbolDivisores (x `div` y)) where y = menorDivisor x -- (menorDivisor x) es el menor divisor primo de x. Por ejemplo, -- menorDivisor 45 == 3 -- menorDivisor 5 == 5 menorDivisor :: Int -> Int menorDivisor x = head [y | y <- [2..x], x `mod` y == 0] -- 1ª definición de hojasArbolDivisores -- ==================================== hojasArbolDivisores :: Int -> [Int] hojasArbolDivisores = hojas . arbolDivisores -- (hojas a) es la lista de las hojas del árbol a. Por ejemplo, -- hojas (N 3 (H 4) (N 5 (H 7) (H 2))) == [4,7,2] hojas :: Arbol -> [Int] hojas (H x) = [x] hojas (N _ i d) = hojas i ++ hojas d -- 2ª definición de hojasArbolDivisores -- ==================================== hojasArbolDivisores2 :: Int -> [Int] hojasArbolDivisores2 = primeFactors |
Entre las brevas soy blando;
entre las rocas, de piedra.
¡Malo!Antonio Machado
El triángulo de Euler se construye a partir de las siguientes relaciones
|
1 2 |
A(n,1) = A(n,n) = 1 A(n,m) = (n-m)A(n-1,m-1) + (m+1)A(n-1,m). |
Sus primeros términos son
|
1 2 3 4 5 6 7 8 9 |
1 1 1 1 4 1 1 11 11 1 1 26 66 26 1 1 57 302 302 57 1 1 120 1191 2416 1191 120 1 1 247 4293 15619 15619 4293 247 1 1 502 14608 88234 156190 88234 14608 502 1 |
Definir las siguientes funciones:
|
1 2 3 |
numeroEuler :: Integer -> Integer -> Integer filaTrianguloEuler :: Integer -> [Integer] trianguloEuler :: [[Integer]] |
tales que
|
1 2 3 |
numeroEuler 8 3 == 15619 numeroEuler 20 6 == 21598596303099900 length (show (numeroEuler 1000 500)) == 2567 |
|
1 2 3 |
filaTrianguloEuler 7 == [1,120,1191,2416,1191,120,1] filaTrianguloEuler 8 == [1,247,4293,15619,15619,4293,247,1] length (show (maximum (filaTrianguloEuler 1000))) == 2567 |
|
1 2 3 4 |
λ> take 6 trianguloEuler [[1],[1,1],[1,4,1],[1,11,11,1],[1,26,66,26,1],[1,57,302,302,57,1]] λ> length (show (maximum (trianguloEuler !! 999))) 2567 |
|
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 |
import Data.List (genericLength, genericIndex) import Data.Array (Array, (!), array) -- 1ª solución -- =========== trianguloEuler :: [[Integer]] trianguloEuler = iterate siguiente [1] -- (siguiente xs) es la fila siguiente a la xs en el triángulo de -- Euler. Por ejemplo, -- λ> siguiente [1] -- [1,1] -- λ> siguiente it -- [1,4,1] -- λ> siguiente it -- [1,11,11,1] siguiente :: [Integer] -> [Integer] siguiente xs = zipWith (+) us vs where n = genericLength xs us = zipWith (*) (0:xs) [n+1,n..1] vs = zipWith (*) (xs++[0]) [1..n+1] filaTrianguloEuler :: Integer -> [Integer] filaTrianguloEuler n = trianguloEuler `genericIndex` (n-1) numeroEuler :: Integer -> Integer -> Integer numeroEuler n k = filaTrianguloEuler n `genericIndex` k -- 2ª solución -- =========== numeroEuler2 :: Integer -> Integer -> Integer numeroEuler2 n 0 = 1 numeroEuler2 n m | n == m = 0 | otherwise = (n-m) * numeroEuler2 (n-1) (m-1) + (m+1) * numeroEuler2 (n-1) m filaTrianguloEuler2 :: Integer -> [Integer] filaTrianguloEuler2 n = map (numeroEuler2 n) [0..n-1] trianguloEuler2 :: [[Integer]] trianguloEuler2 = map filaTrianguloEuler2 [1..] -- 3ª solución -- =========== numeroEuler3 :: Integer -> Integer -> Integer numeroEuler3 n k = (matrizEuler n k) ! (n,k) -- (matrizEuler n m) es la matriz de n+1 filas y m+1 columnsa formada -- por los números de Euler. Por ejemplo, -- λ> [[matrizEuler 6 6 ! (i,j) | j <- [0..i-1]] | i <- [1..6]] -- [[1],[1,1],[1,4,1],[1,11,11,1],[1,26,66,26,1],[1,57,302,302,57,1]] matrizEuler :: Integer -> Integer -> Array (Integer,Integer) Integer matrizEuler n m = q where q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]] f i 0 = 1 f i j | i == j = 0 | otherwise = (i-j) * q!(i-1,j-1) + (j+1)* q!(i-1,j) filaTrianguloEuler3 :: Integer -> [Integer] filaTrianguloEuler3 n = map (numeroEuler3 n) [0..n-1] trianguloEuler3 :: [[Integer]] trianguloEuler3 = map filaTrianguloEuler3 [1..] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> numeroEuler 22 11 -- 301958232385734088196 -- (0.01 secs, 118,760 bytes) -- λ> numeroEuler2 22 11 -- 301958232385734088196 -- (3.96 secs, 524,955,384 bytes) -- λ> numeroEuler3 22 11 -- 301958232385734088196 -- (0.01 secs, 356,296 bytes) -- -- λ> length (show (numeroEuler 800 400)) -- 1976 -- (0.01 secs, 383,080 bytes) -- λ> length (show (numeroEuler3 800 400)) -- 1976 -- (2.13 secs, 508,780,696 bytes) |
Señor San Jerónimo,
suelte usted la piedra
con que se machaca.
Me pegó con ella.Antonio Machado
Definir la función
|
1 |
subconjuntosDivisibles :: [Int] -> [[Int]] |
tal que (subconjuntosDivisibles xs) es la lista de todos los subconjuntos de xs en los que todos los elementos tienen un factor común mayor que 1. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 |
subconjuntosDivisibles [] == [[]] subconjuntosDivisibles [1] == [[]] subconjuntosDivisibles [3] == [[3],[]] subconjuntosDivisibles [1,3] == [[3],[]] subconjuntosDivisibles [3,6] == [[3,6],[3],[6],[]] subconjuntosDivisibles [1,3,6] == [[3,6],[3],[6],[]] subconjuntosDivisibles [2,3,6] == [[2,6],[2],[3,6],[3],[6],[]] subconjuntosDivisibles [2,3,6,8] == [[2,6,8],[2,6],[2,8],[2],[3,6],[3],[6,8],[6],[8],[]] length (subconjuntosDivisibles [1..10]) == 41 length (subconjuntosDivisibles [1..20]) == 1097 length (subconjuntosDivisibles [1..30]) == 33833 length (subconjuntosDivisibles [1..40]) == 1056986 |
|
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 |
import Data.List (foldl1', subsequences) -- 1ª solución -- =========== subconjuntosDivisibles :: [Int] -> [[Int]] subconjuntosDivisibles xs = filter esDivisible (subsequences xs) -- (esDivisible xs) se verifica si todos los elementos de xs tienen un -- factor común mayor que 1. Por ejemplo, -- esDivisible [6,10,22] == True -- esDivisible [6,10,23] == False esDivisible :: [Int] -> Bool esDivisible [] = True esDivisible xs = mcd xs > 1 -- (mcd xs) es el máximo común divisor de xs. Por ejemplo, -- mcd [6,10,22] == 2 -- mcd [6,10,23] == 1 mcd :: [Int] -> Int mcd = foldl1' gcd -- 2ª solución -- =========== subconjuntosDivisibles2 :: [Int] -> [[Int]] subconjuntosDivisibles2 [] = [[]] subconjuntosDivisibles2 (x:xs) = [x:ys | ys <- yss, esDivisible (x:ys)] ++ yss where yss = subconjuntosDivisibles2 xs -- 3ª solución -- =========== subconjuntosDivisibles3 :: [Int] -> [[Int]] subconjuntosDivisibles3 [] = [[]] subconjuntosDivisibles3 (x:xs) = filter esDivisible (map (x:) yss) ++ yss where yss = subconjuntosDivisibles3 xs -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (subconjuntosDivisibles [1..21]) -- 1164 -- (3.83 secs, 5,750,416,768 bytes) -- λ> length (subconjuntosDivisibles2 [1..21]) -- 1164 -- (0.01 secs, 5,400,232 bytes) -- λ> length (subconjuntosDivisibles3 [1..21]) -- 1164 -- (0.01 secs, 5,264,928 bytes) -- -- λ> length (subconjuntosDivisibles2 [1..40]) -- 1056986 -- (6.95 secs, 8,845,664,672 bytes) -- λ> length (subconjuntosDivisibles3 [1..40]) -- 1056986 -- (6.74 secs, 8,727,141,792 bytes) |
Abejas, cantores,
no a la miel, sino a las flores.Antonio Machado
Definir la función
|
1 |
matrizGirada180 :: Matrix a -> Matrix a |
tal que (matrizGirada180 p) es la matriz obtenida girando 180 grados la matriz p. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
λ> fromList 4 3 [1..] ( 1 2 3 ) ( 4 5 6 ) ( 7 8 9 ) ( 10 11 12 ) λ> matrizGirada180 (fromList 4 3 [1..]) ( 12 11 10 ) ( 9 8 7 ) ( 6 5 4 ) ( 3 2 1 ) λ> fromList 3 4 [1..] ( 1 2 3 4 ) ( 5 6 7 8 ) ( 9 10 11 12 ) λ> matrizGirada180 (fromList 3 4 [1..]) ( 12 11 10 9 ) ( 8 7 6 5 ) ( 4 3 2 1 ) |
|
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 |
import Data.Matrix ( Matrix , (!) , fromList , fromLists , matrix , ncols , nrows , toLists ) -- 1ª solución matrizGirada180 :: Matrix a -> Matrix a matrizGirada180 p = matrix m n f where m = nrows p n = ncols p f (i,j) = p!(m-i+1,n-j+1) -- 2ª solución matrizGirada180b :: Matrix a -> Matrix a matrizGirada180b p = fromLists (reverse (map reverse (toLists p))) -- 3ª solución matrizGirada180c :: Matrix a -> Matrix a matrizGirada180c = fromLists . reverse . map reverse . toLists |
Bueno es recordar
las palabras viejas
que han de volver a sonar.Antonio Machado
Los árboles se pueden representar mediante el siguiente tipo de dato
|
1 2 |
data Arbol a = N a [Arbol a] deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
-1 1 1 / \ / \ /|\ 2 3 -2 3 / | \ / \ | -2 7 3 4 5 -4 / \ 4 5 |
se representan por
|
1 2 3 4 |
ej1, ej2, ej3 :: Arbol Int ej1 = N (-1) [N 2 [N 4 [], N 5 []], N 3 []] ej2 = N 1 [N (-2) [N (-4) []], N 3 []] ej3 = N 1 [N (-2) [N 4 [], N 5 []], N 7 [], N 3 []] |
Definir la función
|
1 |
todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool |
tal que (todasDesdeAlguno p ar) se verifica si para toda rama existe un elemento a partir del cual todos los elementos de la rama verifican la propiedad p. Por ejemplo,
|
1 2 3 |
todasDesdeAlguno (>0) ej1 == True todasDesdeAlguno (>0) ej2 == False todasDesdeAlguno (>0) ej3 == True |
|
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 |
import Data.List (tails) data Arbol a = N a [Arbol a] deriving Show ej1, ej2, ej3 :: Arbol Int ej1 = N (-1) [N 2 [N 4 [], N 5 []], N 3 []] ej2 = N 1 [N (-2) [N (-4) []], N 3 []] ej3 = N 1 [N (-2) [N 4 [], N 5 []], N 7 [], N 3 []] -- 1ª solución -- =========== todasDesdeAlguno :: (b -> Bool) -> Arbol b -> Bool todasDesdeAlguno p a = all (desdeAlguno p) (ramas a) -- (desdeAlguno p xs) se verifica si la propiedad xs tiene un elementemo -- a partir del cual todos los siguientes cumplen la propiedad p. Por -- ejemplo, -- desdeAlguno (>0) [-1,2,4] == True -- desdeAlguno (>0) [1,-2,-4] == False -- desdeAlguno (>0) [1,-2,4] == True -- 1ª definición de desdeAlguno desdeAlguno1 :: (a -> Bool) -> [a] -> Bool desdeAlguno1 p xs = not (null (takeWhile p (reverse xs))) -- 2ª definición de desdeAlguno desdeAlguno2 :: (a -> Bool) -> [a] -> Bool desdeAlguno2 p xs = any (all p) (init (tails xs)) -- Comparación de eficiencia: -- λ> desdeAlguno1 (>10^7) [1..1+10^7] -- True -- (4.36 secs, 960,101,896 bytes) -- λ> desdeAlguno2 (>10^7) [1..1+10^7] -- True -- (5.62 secs, 3,600,101,424 bytes) -- Usaremos la 1ª definición de desdeAlguno desdeAlguno :: (a -> Bool) -> [a] -> Bool desdeAlguno = desdeAlguno1 -- (ramas a) es la lista de las ramas de a. Por ejemplo, -- ramas ej1 == [[-1,2,4],[-1,2,5],[-1,3]] -- ramas ej2 == [[1,-2,-4],[1,3]] -- ramas ej3 == [[1,-2,4],[1,-2,5],[1,7],[1,3]] ramas :: Arbol a -> [[a]] ramas (N x []) = [[x]] ramas (N x as) = map (x:) (concatMap ramas as) -- 2ª solución -- =========== todasDesdeAlguno2 :: (b -> Bool) -> Arbol b -> Bool todasDesdeAlguno2 p (N x []) = p x todasDesdeAlguno2 p (N _ as) = all (todasDesdeAlguno2 p) as |
Por dar al viento trabajo,
cosía con hilo doble
las hojas secas del árbol.Antonio Machado
Definir las funciones
|
1 2 |
minimasDistancias :: Matrix Int -> Matrix Int sumaMinimaDistanciasIdentidad :: Int -> Int |
tales que
|
1 2 3 4 5 6 7 8 9 10 11 12 |
λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]]) ( 1 0 0 ) ( 2 1 0 ) λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]]) ( 1 1 0 ) ( 0 1 1 ) λ> minimasDistancias (identity 5) ( 0 1 2 3 4 ) ( 1 0 1 2 3 ) ( 2 1 0 1 2 ) ( 3 2 1 0 1 ) ( 4 3 2 1 0 ) |
|
1 2 3 4 |
sumaMinimaDistanciasIdentidad 5 == 40 sumaMinimaDistanciasIdentidad (10^2) == 333300 sumaMinimaDistanciasIdentidad (10^4) == 333333330000 sumaMinimaDistanciasIdentidad (10^6) == 333333333333000000 |
|
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 |
import Data.Matrix import Data.Maybe (isJust, fromJust) import Test.QuickCheck -- Definición de minimasDistancias -- =============================== minimasDistancias :: Matrix Int -> Matrix Int minimasDistancias a = fmap fromJust (aux (matrizInicial a)) where aux b | Nothing `elem` c = aux c | otherwise = c where c = propagacion b -- (matrizInicial a) es la matriz que tiene (Just 0) en los elementos de -- a iguales a 1 y Nothing en los restantes. Por ejemplo, -- λ> matrizInicial (fromLists [[0,0,1],[1,0,0]]) -- ( Nothing Nothing Just 0 ) -- ( Just 0 Nothing Nothing ) matrizInicial :: Matrix Int -> Matrix (Maybe Int) matrizInicial a = matrix m n f where m = nrows a n = ncols a f (i,j) | a ! (i,j) == 1 = Just 0 | otherwise = Nothing -- (propagacion a) es la matriz obtenida cambiando los elementos Nothing -- de a por el sigiente del mínomo de los valores de sus vecinos. Por -- ejemplo, -- λ> propagacion (fromLists [[0,1,1],[0,0,1]]) -- ( Just 1 Just 0 Just 0 ) -- ( Nothing Just 1 Just 0 ) -- -- λ> propagacion it -- ( Just 1 Just 0 Just 0 ) -- ( Just 2 Just 1 Just 0 ) propagacion :: Matrix (Maybe Int) -> Matrix (Maybe Int) propagacion a = matrix m n f where m = nrows a n = ncols a f (i,j) | isJust x = x | otherwise = siguiente (minimo (valoresVecinos a (i,j))) where x = a ! (i,j) -- (valoresVecinos a p) es la lista de los valores de los vecinos la -- posición p en la matriz a. Por ejemplo, -- λ> a = fromList 3 4 [1..] -- λ> a -- ( 1 2 3 4 ) -- ( 5 6 7 8 ) -- ( 9 10 11 12 ) -- -- λ> valoresVecinos a (1,1) -- [5,2] -- λ> valoresVecinos a (2,3) -- [3,11,6,8] -- λ> valoresVecinos a (2,4) -- [4,12,7] valoresVecinos :: Matrix a -> (Int,Int) -> [a] valoresVecinos a (i,j) = [a ! (k,l) | (k,l) <- vecinos m n (i,j)] where m = nrows a n = ncols a -- (vecinos m n p) es la lista de las posiciones vecinas de la posición -- p en la matriz a; es decir, los que se encuentran a su izquierda, -- derecha, arriba o abajo. por ejemplo, -- vecinos 3 4 (1,1) == [(2,1),(1,2)] -- vecinos 3 4 (2,3) == [(1,3),(3,3),(2,2),(2,4)] -- vecinos 3 4 (2,4) == [(1,4),(3,4),(2,3)] vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)] vecinos m n (i,j) = [(i - 1,j) | i > 1] ++ [(i + 1,j) | i < m] ++ [(i, j - 1) | j > 1] ++ [(i, j + 1) | j < n] -- (minimo xs) es el mínimo de la lista de valores opcionales xs -- (considerando Nothing como el mayor elemento). Por ejemplo, -- minimo [Just 3, Nothing, Just 2] == Just 2 minimo :: [Maybe Int] -> Maybe Int minimo = foldr1 minimo2 -- (minimo2 x y) es el mínimo de los valores opcionales x e y -- (considerando Nothing como el mayor elemento). Por ejemplo, -- minimo2 (Just 3) (Just 2) == Just 2 -- minimo2 (Just 1) (Just 2) == Just 1 -- minimo2 (Just 1) Nothing == Just 1 -- minimo2 Nothing (Just 2) == Just 2 -- minimo2 Nothing Nothing == Nothing minimo2 :: Maybe Int -> Maybe Int -> Maybe Int minimo2 (Just x) (Just y) = Just (min x y) minimo2 Nothing (Just y) = Just y minimo2 (Just x) Nothing = Just x minimo2 Nothing Nothing = Nothing -- (siguiente x) es el siguiente elemento del opcional x (considerando -- Nothing como el infinito). Por ejemplo, -- siguiente (Just 3) == Just 4 -- siguiente Nothing == Nothing siguiente :: Maybe Int -> Maybe Int siguiente (Just x) = Just (1 + x) siguiente Nothing = Nothing -- 1ª definición de sumaMinimaDistanciasIdentidad -- ============================================== sumaMinimaDistanciasIdentidad :: Int -> Int sumaMinimaDistanciasIdentidad n = sum (minimasDistancias (identity n)) -- 2ª definición de sumaMinimaDistanciasIdentidad -- ============================================== sumaMinimaDistanciasIdentidad2 :: Int -> Int sumaMinimaDistanciasIdentidad2 n = n*(n^2-1) `div` 3 -- Equivalencia de las definiciones de sumaMinimaDistanciasIdentidad -- ================================================================= -- La propiedad es prop_MinimaDistanciasIdentidad :: Positive Int -> Bool prop_MinimaDistanciasIdentidad (Positive n) = sumaMinimaDistanciasIdentidad n == sumaMinimaDistanciasIdentidad2 n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=50}) prop_MinimaDistanciasIdentidad -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sumaMinimaDistanciasIdentidad 50 -- 41650 -- (0.24 secs, 149,395,744 bytes) -- λ> sumaMinimaDistanciasIdentidad 100 -- 333300 -- (1.98 secs, 1,294,676,272 bytes) -- λ> sumaMinimaDistanciasIdentidad 200 -- 2666600 -- (17.96 secs, 11,094,515,016 bytes) -- -- λ> sumaMinimaDistanciasIdentidad2 50 -- 41650 -- (0.00 secs, 126,944 bytes) -- λ> sumaMinimaDistanciasIdentidad2 100 -- 333300 -- (0.00 secs, 126,872 bytes) -- λ> sumaMinimaDistanciasIdentidad2 200 -- 2666600 -- (0.00 secs, 131,240 bytes) -- -- Resumidamente, el tiempo es -- -- +-----+---------+--------+ -- | n | 1ª def. | 2ª def | -- +-----+---------+--------+ -- | 50 | 0.24 | 0.00 | -- | 100 | 1.98 | 0.00 | -- | 200 | 17.96 | 0.00 | -- +-----+---------+--------+ |
La primavera ha venido.
Nadie sabe como ha sido.Antonio Machado
Definir la función
|
1 |
siguienteMayor :: Ord a => [a] -> [Maybe a] |
tal que (siguienteMayos xs) es la lista obtenida sustiyendo cada elemento de xs por el primer elemento de xs a la derechha de x que sea mayor que x, si existe y Nothing en caso contrario. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
λ> siguienteMayor [4,5,2,3,9] [Just 5,Just 9,Just 3,Just 9,Nothing] λ> siguienteMayor [9,5,2,3,4] [Nothing,Nothing,Just 3,Just 4,Nothing] λ> siguienteMayor [9,5,2,2,4] [Nothing,Nothing,Just 4,Just 4,Nothing] λ> siguienteMayor "betis" [Just 'e',Just 't',Nothing,Just 's',Nothing] λ> siguienteMayor "sevilla" [Just 'v',Just 'v',Nothing,Just 'l',Nothing,Nothing,Nothing] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
import Data.Maybe (listToMaybe) -- 1ª solución siguienteMayor :: Ord a => [a] -> [Maybe a] siguienteMayor [] = [] siguienteMayor (x:xs) | null ys = Nothing : siguienteMayor xs | otherwise = Just (head ys) : siguienteMayor xs where ys = [y | y <- xs, y > x] -- 2ª solución siguienteMayor2 :: Ord a => [a] -> [Maybe a] siguienteMayor2 [] = [] siguienteMayor2 (x:xs) = listToMaybe [y | y <- xs, y > x] : siguienteMayor2 xs -- 3ª solución siguienteMayor3 :: Ord a => [a] -> [Maybe a] siguienteMayor3 [] = [] siguienteMayor3 (x:xs) = listToMaybe (dropWhile (<=x) xs) : siguienteMayor3 xs |
Si vivir es bueno
es mejor soñar,
y mejor que todo,
madre, despertar.Antonio Machado
En la librería Data.Tree se definen los tipos de árboles y bosques como sigue
|
1 2 |
data Tree a = Node a (Forest a) type Forest a = [Tree a] |
Se pueden definir árboles. Por ejemplo,
|
1 |
ej = Node 3 [Node 5 [Node 9 []], Node 7 []] |
Y se pueden dibujar con la función drawTree. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> putStrLn (drawTree (fmap show ej)) 3 | +- 5 | | | `- 9 | `- 7 |
Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u.v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.
El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es
|
1 2 3 4 5 6 7 8 9 10 11 |
6 / \ 5 3 | | 4 2 / \ | 3 2 1 | | 2 1 | 1 |
Definir las siguientes funciones
|
1 2 3 4 |
mayoresDivisores :: Int -> [Int] arbol :: Int -> Tree Int caminos :: Int -> [[Int]] caminosMinimales :: Int -> [[Int]] |
tales que
+ (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,
|
1 2 3 4 |
mayoresDivisores 24 == [12,8,6] mayoresDivisores 16 == [8,4] mayoresDivisores 10 == [5] mayoresDivisores 17 == [] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
λ> putStrLn (drawTree (fmap show (arbol 6))) 6 | +- 5 | | | `- 4 | | | +- 3 | | | | | `- 2 | | | | | `- 1 | | | `- 2 | | | `- 1 | `- 3 | `- 2 | `- 1 |
|
1 2 |
λ> caminos 6 [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]] |
|
1 2 3 4 5 6 |
λ> caminosMinimales 6 [[6,3,2,1]] λ> caminosMinimales 17 [[17,16,4,2,1]] λ> caminosMinimales 50 [[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]] |
|
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 |
import Data.Tree import Test.QuickCheck mayoresDivisores :: Int -> [Int] mayoresDivisores x = [max u v | u <- [2..floor (sqrt (fromIntegral x))] , x `mod` u == 0 , let v = x `div` u] arbol :: Int -> Tree Int arbol 1 = Node 1 [] arbol x = Node x (arbol (x-1) : [arbol y | y <- mayoresDivisores x]) caminos :: Int -> [[Int]] caminos = caminosArbol . arbol -- λ> caminosArbol (arbol 6) -- [[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]] caminosArbol :: Tree a -> [[a]] caminosArbol (Node x []) = [[x]] caminosArbol (Node x as) = [x:ys | ys <- caminosBosque as] caminosBosque :: Forest a -> [[a]] caminosBosque = concatMap caminosArbol caminosMinimales :: Int -> [[Int]] caminosMinimales x = [ys | ys <- yss, length ys == m] where yss = caminos x m = minimum (map length yss) |
Tras el vivir y el soñar,
está lo que más importa:
despertar.Antonio Machado
El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas
|
1 2 3 4 |
1, 1, 1, 1, 1, 1 1, 1, 1, 3 1, 1, 4 3, 3 |
El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.
Definir
|
1 |
monedas :: [Int] -> Int -> Maybe Int |
tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,
|
1 2 3 |
monedas [1,3,4] 6 == Just 2 monedas [2,5,10] 3 == Nothing monedas [1,2,5,10,20,50,100,200] 520 == Just 4 |
|
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 |
import Data.Array ((!), array) -- 1ª solución -- =========== monedas :: [Int] -> Int -> Maybe Int monedas ms x | null cs = Nothing | otherwise = Just (minimum (map length cs)) where cs = cambios ms x -- (cambios ms x) es la lista de las foemas de obtener x sumando monedas -- de ms. Por ejemplo, -- λ> cambios [1,5,10] 12 -- [[1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,5],[1,1,5,5],[1,1,10]] -- λ> cambios [2,5,10] 3 -- [] -- λ> cambios [1,3,4] 6 -- [[1,1,1,1,1,1],[1,1,1,3],[1,1,4],[3,3]] cambios :: [Int] -> Int -> [[Int]] cambios _ 0 = [[]] cambios [] _ = [] cambios (k:ks) m | m < k = [] | otherwise = [k:zs | zs <- cambios (k:ks) (m - k)] ++ cambios ks m -- 2ª solución -- =========== monedas2 :: [Int] -> Int -> Maybe Int monedas2 ms n | sol == infinito = Nothing | otherwise = Just sol where sol = aux n aux 0 = 0 aux k = siguiente (minimo [aux (k - x) | x <- ms, k >= x]) infinito :: Int infinito = 10^30 minimo :: [Int] -> Int minimo [] = infinito minimo xs = minimum xs siguiente :: Int -> Int siguiente x | x == infinito = infinito | otherwise = 1 + x -- 3ª solución -- =========== monedas3 :: [Int] -> Int -> Maybe Int monedas3 ms n | sol == infinito = Nothing | otherwise = Just sol where sol = v ! n v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f k = siguiente (minimo [v ! (k - x) | x <- ms, k >= x]) -- Comparación de eficiencia -- ========================= -- λ> monedas [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (0.02 secs, 871,144 bytes) -- λ> monedas2 [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (15.44 secs, 1,866,519,080 bytes) -- λ> monedas3 [1,2,5,10,20,50,100,200] 27 -- Just 3 -- (0.01 secs, 157,232 bytes) -- -- λ> monedas [1,2,5,10,20,50,100,200] 188 -- Just 7 -- (14.20 secs, 1,845,293,080 bytes) -- λ> monedas3 [1,2,5,10,20,50,100,200] 188 -- Just 7 -- (0.01 secs, 623,376 bytes) |
Demos tiempo al tiempo:
para que el vaso rebose
hay que llenarlo primero.Antonio Machado
Definir la función
|
1 |
longitudMayorSublistaCreciente :: Ord a => [a] -> Int |
tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
λ> longitudMayorSublistaCreciente [3,2,6,4,5,1] 3 λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80] 6 λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] 6 λ> longitudMayorSublistaCreciente [1..2000] 2000 λ> longitudMayorSublistaCreciente [2000,1999..1] 1 λ> import System.Random λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]] λ> longitudMayorSublistaCreciente2 xs 61 λ> longitudMayorSublistaCreciente3 xs 61 |
|
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 |
import Data.List (nub, sort) import Data.Array (Array, (!), array, elems, listArray) -- 1ª solución -- =========== longitudMayorSublistaCreciente1 :: Ord a => [a] -> Int longitudMayorSublistaCreciente1 = length . head . mayoresCrecientes -- (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs -- de mayor longitud. Por ejemplo, -- λ> mayoresCrecientes [3,2,6,4,5,1] -- [[3,4,5],[2,4,5]] -- λ> mayoresCrecientes [3,2,3,2,3,1] -- [[2,3],[2,3],[2,3]] -- λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80] -- [[10,22,33,50,60,80],[10,22,33,41,60,80]] -- λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] -- [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]] mayoresCrecientes :: Ord a => [a] -> [[a]] mayoresCrecientes xs = [ys | ys <- xss , length ys == m] where xss = sublistasCrecientes xs m = maximum (map length xss) -- (sublistasCrecientes xs) es la lista de las sublistas crecientes de -- xs. Por ejemplo, -- λ> sublistasCrecientes [3,2,5] -- [[3,5],[3],[2,5],[2],[5],[]] sublistasCrecientes :: Ord a => [a] -> [[a]] sublistasCrecientes [] = [[]] sublistasCrecientes (x:xs) = [x:ys | ys <- yss, null ys || x < head ys] ++ yss where yss = sublistasCrecientes xs -- 2ª solución -- =========== longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int longitudMayorSublistaCreciente2 xs = longitudSCM xs (sort (nub xs)) -- (longitudSCM xs ys) es la longitud de la subsecuencia máxima de xs e -- ys. Por ejemplo, -- longitudSCM "amapola" "matamoscas" == 4 -- longitudSCM "atamos" "matamoscas" == 6 -- longitudSCM "aaa" "bbbb" == 0 longitudSCM :: Eq a => [a] -> [a] -> Int longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m) where n = length xs m = length ys -- (matrizLongitudSCM xs ys) es la matriz de orden (n+1)x(m+1) (donde n -- y m son los números de elementos de xs e ys, respectivamente) tal que -- el valor en la posición (i,j) es la longitud de la SCM de los i -- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo, -- λ> elems (matrizLongitudSCM "amapola" "matamoscas") -- [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2, -- 0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3, -- 0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4] -- Gráficamente, -- m a t a m o s c a s -- [0,0,0,0,0,0,0,0,0,0,0, -- a 0,0,1,1,1,1,1,1,1,1,1, -- m 0,1,1,1,1,2,2,2,2,2,2, -- a 0,1,2,2,2,2,2,2,2,3,3, -- p 0,1,2,2,2,2,2,2,2,3,3, -- o 0,1,2,2,2,2,3,3,3,3,3, -- l 0,1,2,2,2,2,3,3,3,3,3, -- a 0,1,2,2,3,3,3,3,3,4,4] matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int matrizLongitudSCM xs ys = q where n = length xs m = length ys v = listArray (1,n) xs w = listArray (1,m) ys q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]] where f 0 _ = 0 f _ 0 = 0 f i j | v ! i == w ! j = 1 + q ! (i-1,j-1) | otherwise = max (q ! (i-1,j)) (q ! (i,j-1)) -- 3ª solución -- =========== longitudMayorSublistaCreciente3 :: Ord a => [a] -> Int longitudMayorSublistaCreciente3 xs = maximum (elems (vectorlongitudMayorSublistaCreciente xs)) -- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n -- (donde n es el tamaño de xs) tal que el valor i-ésimo es la longitud -- de la sucesión más larga que termina en el elemento i-ésimo de -- xs. Por ejemplo, -- λ> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1] -- array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)] vectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int vectorlongitudMayorSublistaCreciente xs = v where v = array (1,n) [(i,f i) | i <- [1..n]] n = length xs w = listArray (1,n) xs f 1 = 1 f i | null ls = 1 | otherwise = 1 + maximum ls where ls = [v ! j | j <-[1..i-1], w ! j < w ! i] -- Comparación de eficiencia -- ========================= -- λ> longitudMayorSublistaCreciente1 [1..20] -- 20 -- (4.60 secs, 597,014,240 bytes) -- λ> longitudMayorSublistaCreciente2 [1..20] -- 20 -- (0.03 secs, 361,384 bytes) -- λ> longitudMayorSublistaCreciente3 [1..20] -- 20 -- (0.03 secs, 253,944 bytes) -- -- λ> longitudMayorSublistaCreciente2 [1..2000] -- 2000 -- (8.00 secs, 1,796,495,488 bytes) -- λ> longitudMayorSublistaCreciente3 [1..2000] -- 2000 -- (5.12 secs, 1,137,667,496 bytes) -- -- λ> longitudMayorSublistaCreciente1 [1000,999..1] -- 1 -- (0.95 secs, 97,029,328 bytes) -- λ> longitudMayorSublistaCreciente2 [1000,999..1] -- 1 -- (7.48 secs, 1,540,857,208 bytes) -- λ> longitudMayorSublistaCreciente3 [1000,999..1] -- 1 -- (0.86 secs, 160,859,128 bytes) -- -- λ> longitudMayorSublistaCreciente1 (show (2^300)) -- 10 -- (7.90 secs, 887,495,368 bytes) -- λ> longitudMayorSublistaCreciente2 (show (2^300)) -- 10 -- (0.04 secs, 899,152 bytes) -- λ> longitudMayorSublistaCreciente3 (show (2^300)) -- 10 -- (0.04 secs, 1,907,936 bytes) -- -- λ> longitudMayorSublistaCreciente2 (show (2^6000)) -- 10 -- (0.06 secs, 9,950,592 bytes) -- λ> longitudMayorSublistaCreciente3 (show (2^6000)) -- 10 -- (3.46 secs, 686,929,744 bytes) -- -- λ> import System.Random -- (0.00 secs, 0 bytes) -- λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]] -- (0.02 secs, 1,993,032 bytes) -- λ> longitudMayorSublistaCreciente2 xs -- 61 -- (7.73 secs, 1,538,771,392 bytes) -- λ> longitudMayorSublistaCreciente3 xs -- 61 -- (1.04 secs, 212,538,648 bytes) -- λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]] -- (0.03 secs, 1,993,032 bytes) -- λ> longitudMayorSublistaCreciente2 xs -- 57 -- (7.56 secs, 1,538,573,680 bytes) -- λ> longitudMayorSublistaCreciente3 xs -- 57 -- (1.05 secs, 212,293,984 bytes) |
No es el yo fundamental
eso que busca el poeta,
sino el tú esencial.Antonio Machado
Un número cíclope es un número natural cuya representación binaria sólo tiene un cero en el centro. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 |
0 es ciclope porque su representación binaria es 0 1 no es ciclope porque su representación binaria es 1 5 es ciclope porque su representación binaria es 101 9 no es ciclope porque su representación binaria es 1001 10 no es ciclope porque su representación binaria es 1010 27 es ciclope porque su representación binaria es 11011 85 no es ciclope porque su representación binaria es 1010101 101 no es ciclope porque su representación binaria es 1100101 111 no es ciclope porque su representación binaria es 1101111 119 es ciclope porque su representación binaria es 1110111 |
Definir las funciones
|
1 2 3 |
esCiclope :: Integer -> Bool ciclopes :: [Integer] graficaCiclopes :: Int -> IO () |
tales que
|
1 2 3 4 5 6 7 8 9 10 |
esCiclope 0 == True esCiclope 1 == False esCiclope 5 == True esCiclope 9 == False esCiclope 10 == False esCiclope 27 == True esCiclope 85 == False esCiclope 101 == False esCiclope 111 == False esCiclope 119 == True |
|
1 2 3 4 |
λ> take 12 ciclopes [0,5,27,119,495,2015,8127,32639,130815,523775,2096127,8386559] λ> length (show (ciclopes !! (10^5))) 60207 |
|
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 |
import Graphics.Gnuplot.Simple -- 1ª solución -- =========== -- esCiclope 5 == True -- esCiclope 6 == False esCiclope :: Integer -> Bool esCiclope n = esCiclopeBinario (decimalAbinario n) -- decimalAbinario 4 == [0,0,1] -- decimalAbinario 5 == [1,0,1] -- decimalAbinario 6 == [0,1,1] decimalAbinario :: Integer -> [Integer] decimalAbinario 0 = [0] decimalAbinario 1 = [1] decimalAbinario n = r : decimalAbinario q where (q,r) = quotRem n 2 -- esCiclopeBinario [1,1,0,1,1] == True -- esCiclopeBinario [1,1,0,1] == False -- esCiclopeBinario [1,1,2,1,1] == False -- esCiclopeBinario [2,2,0,2,2] == False esCiclopeBinario :: [Integer] -> Bool esCiclopeBinario xs = odd n && xs == ys ++ 0 : ys where n = length xs m = n `div` 2 ys = replicate m 1 -- take 8 ciclopes == [0,5,27,119,495,2015,8127,32639] ciclopes :: [Integer] ciclopes = filter esCiclope [0..] -- 2ª solución -- =========== -- take 8 ciclopes2 == [0,5,27,119,495,2015,8127,32639] ciclopes2 :: [Integer] ciclopes2 = [binarioAdecimal (replicate n 1 ++ 0 : replicate n 1) | n <- [0..]] -- binarioAdecimal [0,1,1] == 6 binarioAdecimal :: [Integer] -> Integer binarioAdecimal [x] = x binarioAdecimal (x:xs) = x + 2 * binarioAdecimal xs esCiclope2 :: Integer -> Bool esCiclope2 n = n `pertenece` ciclopes2 pertenece :: Integer -> [Integer] -> Bool pertenece x ys = x == head (dropWhile (<x) ys) -- 3ª solución -- =========== -- take 8 ciclopes3 == [0,5,27,119,495,2015,8127,32639] ciclopes3 :: [Integer] ciclopes3 = [sum [2^k | k <- [0..n-1]] + sum [2^k | k <- [n+1..n+n]] | n <- [0..]] esCiclope3 :: Integer -> Bool esCiclope3 n = n `pertenece` ciclopes3 -- 4ª solución -- =========== -- take 8 ciclopes3 == [0,5,27,119,495,2015,8127,32639] ciclopes4 :: [Integer] ciclopes4 = [2^(2*n+1) - 1 - 2^n | n <- [0..]] esCiclope4 :: Integer -> Bool esCiclope4 n = n `pertenece` ciclopes4 -- 5ª solución -- =========== -- take 8 ciclopes5 == [0,5,27,119,495,2015,8127,32639] ciclopes5 :: [Integer] ciclopes5 = [2*4^n - 1 - 2^n | n <- [0..]] esCiclope5 :: Integer -> Bool esCiclope5 n = n `pertenece` ciclopes5 -- 6ª solución -- =========== -- take 8 ciclopes6 == [0,5,27,119,495,2015,8127,32639] ciclopes6 :: [Integer] ciclopes6 = [2*x*x - 1 - x | x <- iterate (*2) 1] esCiclope6 :: Integer -> Bool esCiclope6 n = n `pertenece` ciclopes6 -- Comparación de eficiencia -- ========================= -- λ> ciclopes !! 9 -- 523775 -- (6.68 secs, 4,696,734,960 bytes) -- λ> ciclopes2 !! 9 -- 523775 -- (0.00 secs, 134,664 bytes) -- λ> ciclopes3 !! 9 -- 523775 -- (0.00 secs, 150,920 bytes) -- λ> ciclopes4 !! 9 -- 523775 -- (0.01 secs, 131,936 bytes) -- λ> ciclopes5 !! 9 -- 523775 -- (0.00 secs, 132,064 bytes) -- -- λ> length (show (ciclopes2 !! (3*10^4))) -- 18063 -- (0.65 secs, 486,437,480 bytes) -- λ> length (show (ciclopes3 !! (3*10^4))) -- 18063 -- (2.94 secs, 1,188,645,584 bytes) -- λ> length (show (ciclopes4 !! (3*10^4))) -- 18063 -- (0.02 secs, 6,769,592 bytes) -- λ> length (show (ciclopes5 !! (3*10^4))) -- 18063 -- (0.02 secs, 6,773,552 bytes) -- -- λ> length (show (ciclopes2 !! (10^5))) -- 60207 -- (6.42 secs, 5,148,671,368 bytes) -- λ> length (show (ciclopes4 !! (10^5))) -- 60207 -- (0.07 secs, 22,291,480 bytes) -- λ> length (show (ciclopes5 !! (10^5))) -- 60207 -- (0.04 secs, 22,316,216 bytes) -- -- λ> length (show (ciclopes4 !! (5*10^6))) -- 3010301 -- (2.34 secs, 1,116,327,832 bytes) -- λ> length (show (ciclopes5 !! (5*10^6))) -- 3010301 -- (2.39 secs, 1,099,177,056 bytes) -- Definición de graficaCiclopes -- ============================= graficaCiclopes :: Int -> IO () graficaCiclopes n = plotList [ Key Nothing -- , PNG "Numeros_ciclopes.png" ] [x `mod` 10 | x <- take n ciclopes5] |
¿Sabes cuando el agua suena,
si es agua de cumbre o valle,
de plaza, jardín o huerta?
Cantores, dejad
palmas y jaleo
para los demás.Antonio Machado
Definir la función
|
1 |
tieneCombinacionDivisible :: [Int] -> Int -> Bool |
tal que (tieneCombinacionDivisible xs m) se verifica si existe alguna forma de combinar todos los elementos de la lista (con las operaciones suma o resta) de forma que el resultado sea divisible por m. Por ejemplo,
|
1 2 |
tieneCombinacionDivisible [1,3,4,6] 4 == True tieneCombinacionDivisible [1,3,9] 2 == False |
En el primer ejemplo, 1 – 2 + 3 + 4 + 6 = 12 es una combinación divisible por 4. En el segundo ejemplo, las combinaciones de [1,3,9] son
|
1 2 3 4 5 6 7 8 |
1 + 3 + 9 = 13 -1 + 3 + 9 = 11 1 - 3 + 9 = 7 -1 - 3 + 9 = 5 1 + 3 - 9 = -5 -1 + 3 - 9 = -7 1 - 3 - 9 = -11 -1 - 3 - 9 = -13 |
y ninguna de las 4 es divisible por 2.
|
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 |
import Test.QuickCheck -- 1ª solución -- =========== tieneCombinacionDivisible :: [Int] -> Int -> Bool tieneCombinacionDivisible xs m = any esDivisible (valoresCombinaciones xs) where esDivisible x = x `mod` m == 0 -- (valoresCombinaciones xs) es la lista de los valores de todas las -- combinaciones de todos los elementos de la lista con las operaciones -- suma o resta. Por ejemplo, -- λ> valoresCombinaciones [1,3,4,6] -- [14,12,8,6,6,4,0,-2,2,0,-4,-6,-6,-8,-12,-14] -- λ> valoresCombinaciones [1,3,-4,6] -- [6,4,0,-2,14,12,8,6,-6,-8,-12,-14,2,0,-4,-6] valoresCombinaciones :: [Int] -> [Int] valoresCombinaciones [] = [] valoresCombinaciones [x] = [x,-x] valoresCombinaciones (x:xs) = concat [[y + x, y - x] | y <- ys] where ys = valoresCombinaciones xs -- 2ª solución -- =========== tieneCombinacionDivisible2 :: [Int] -> Int -> Bool tieneCombinacionDivisible2 xs m = tieneCombinacionCongruente xs m 0 -- (tieneCombinacionCongruente xs m a) se verifica si existe alguna -- forma de combinar todos los elementos de la lista xs (con las -- operaciones suma o resta) de forma que el resultado sea congruente -- con a módulo m. Por ejemplo, -- tieneCombinacionCongruente [1,3,4,6] 4 0 == True -- tieneCombinacionCongruente [1,3,4,6] 4 1 == False -- tieneCombinacionCongruente [1,3,9] 2 0 == False -- tieneCombinacionCongruente [1,3,9] 2 1 == True tieneCombinacionCongruente :: [Int] -> Int -> Int -> Bool tieneCombinacionCongruente [] _ _ = False tieneCombinacionCongruente [x] m a = (x - a) `mod` m == 0 tieneCombinacionCongruente (x:xs) m a = tieneCombinacionCongruente xs m (a-x) || tieneCombinacionCongruente xs m (a+x) -- Equivalencia -- ============ -- La propiedad es prop_tieneCombinacionDivisible :: [Int] -> Positive Int -> Bool prop_tieneCombinacionDivisible xs (Positive m) = tieneCombinacionDivisible xs m == tieneCombinacionDivisible2 xs m -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=25}) prop_tieneCombinacionDivisible -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> (n,xs,m) = (200,[-n..n],sum [1..n]) -- (0.00 secs, 0 bytes) -- λ> and [tieneCombinacionDivisible xs a | a <- [1..m]] -- True -- (4.74 secs, 6,536,494,976 bytes) -- λ> and [tieneCombinacionDivisible2 xs a | a <- [1..m]] -- True -- (2.97 secs, 3,381,932,664 bytes) |
El que espera desespera,
dice la voz popular.
¡Qué verdad tan verdadera!
La verdad es lo que es,
y sigue siendo verdad
aunque se piense al revés.Antonio Machado
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
|
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:
|
1 2 3 4 5 6 7 8 9 10 |
1, 7, 3, 8, 4, 9 1, 7, 12, 8, 4, 9 1, 7, 12, 3, 4, 9 1, 7, 12, 3, 8, 9 1, 6, 12, 8, 4, 9 1, 6, 12, 3, 4, 9 1, 6, 12, 3, 8, 9 1, 6, 11, 3, 4, 9 1, 6, 11, 3, 8, 9 1, 6, 11, 2, 8, 9 |
Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El camino de máxima suma es el segundo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.
Definir la función
|
1 |
caminoMaxSuma :: Matrix Int -> [Int] |
tal que (caminoMaxSuma m) es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,
|
1 2 3 4 |
λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) [1,7,12,8,4,9] λ> sum (caminoMaxSuma (fromList 800 800 [1..])) 766721999 |
|
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 |
import Data.Matrix import Test.QuickCheck -- 1ª definición -- ============= caminoMaxSuma1 :: Matrix Int -> [Int] caminoMaxSuma1 m = head [c | c <- cs, sum c == k] where cs = caminos1 m k = maximum (map sum cs) caminos1 :: Matrix Int -> [[Int]] caminos1 m = map reverse (caminos1Aux m (nf,nc)) where nf = nrows m nc = ncols m -- (caminos1Aux p x) es la lista de los caminos invertidos en la matriz p -- desde la posición (1,1) hasta la posición x. Por ejemplo, caminos1Aux :: Matrix Int -> (Int,Int) -> [[Int]] caminos1Aux m (1,1) = [[m!(1,1)]] caminos1Aux m (1,j) = [[m!(1,k) | k <- [j,j-1..1]]] caminos1Aux m (i,1) = [[m!(k,1) | k <- [i,i-1..1]]] caminos1Aux m (i,j) = [m!(i,j) : xs | xs <- caminos1Aux m (i,j-1) ++ caminos1Aux m (i-1,j)] -- 2ª definición -- ============= caminoMaxSuma2 :: Matrix Int -> [Int] caminoMaxSuma2 m = head [c | c <- cs, sum c == k] where cs = caminos2 m k = maximum (map sum cs) caminos2 :: Matrix Int -> [[Int]] caminos2 m = map reverse (matrizCaminos m ! (nrows m, ncols m)) matrizCaminos :: Matrix Int -> Matrix [[Int]] matrizCaminos m = q where q = matrix (nrows m) (ncols m) f f (1,y) = [[m!(1,z) | z <- [y,y-1..1]]] f (x,1) = [[m!(z,1) | z <- [x,x-1..1]]] f (x,y) = [m!(x,y) : cs | cs <- q!(x-1,y) ++ q!(x,y-1)] -- 3ª definición (con programación dinámica) -- ========================================= caminoMaxSuma3 :: Matrix Int -> [Int] caminoMaxSuma3 m = reverse (snd (q ! (nf,nc))) where nf = nrows m nc = ncols m q = caminoMaxSumaAux m caminoMaxSumaAux :: Matrix Int -> Matrix (Int,[Int]) caminoMaxSumaAux m = q where nf = nrows m nc = ncols m q = matrix nf nc f where f (1,1) = (m!(1,1),[m!(1,1)]) f (1,j) = (k + m!(1,j), m!(1,j):xs) where (k,xs) = q!(1,j-1) f (i,1) = (k + m!(i,1), m!(i,1):xs) where (k,xs) = q!(i-1,1) f (i,j) | k1 > k2 = (k1 + m!(i,j), m!(i,j):xs) | otherwise = (k2 + m!(i,j), m!(i,j):ys) where (k1,xs) = q!(i,j-1) (k2,ys) = q!(i-1,j) -- Equivalencia de las definiciones -- ================================ -- El generador es instance Arbitrary a => Arbitrary (Matrix a) where arbitrary = do m <- choose (1,7) n <- choose (1,7) xs <- Test.QuickCheck.vector (n*m) return (fromList m n xs) -- Por ejemplo, -- λ> sample' (arbitrary :: Gen (Matrix Int)) -- [( 0 ) -- ( 0 ) -- ( 0 ) -- ( 0 ) -- ,( 1 2 ) -- ( -1 1 ) -- ( -1 -2 ) -- ( 1 -1 ) -- ( 1 0 ) -- ( 2 0 ) -- ( 2 -2 ) -- ,( -4 4 -2 ) -- ( -2 0 -2 ) -- ( 0 -1 -2 ) -- ( -4 -1 2 ) -- ,( -2 7 -3 1 -5 -3 5 ) -- ( 0 2 7 -1 -5 7 -6 ) -- ( 1 7 -8 1 6 -7 5 ) -- ( -4 7 -2 -7 -5 5 -8 ) -- ... -- La propiedad es prop_caminoMaxSuma :: Matrix Int -> Bool prop_caminoMaxSuma m = x1 == x2 && x2 == x3 where x1 = sum (caminoMaxSuma1 m) x2 = sum (caminoMaxSuma2 m) x3 = sum (caminoMaxSuma1 m) -- La comprobación es -- λ> quickCheck prop_caminoMaxSuma -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ------------------------- -- λ> length (caminoMaxSuma1 (fromList 11 11 [1..])) -- 21 -- (10.00 secs, 1,510,120,328 bytes) -- λ> length (caminoMaxSuma2 (fromList 11 11 [1..])) -- 21 -- (3.84 secs, 745,918,544 bytes) -- λ> length (caminoMaxSuma3 (fromList 11 11 [1..])) -- 21 -- (0.01 secs, 0 bytes) |
Caminante, no hay camino,
sino estelas en la mar.Antonio Machado
Los segmentos iniciales de [3,1,2,5] son [3], [3,1], [3,1,2] y [3,1,2,5]. Sus sumas son 3, 4, 6 y 9, respectivamente. La suma de dichas sumas es 24.
Definir la función
|
1 |
sumaSegmentosIniciales :: [Integer] -> Integer |
tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,
|
1 2 |
sumaSegmentosIniciales [3,1,2,5] == 24 sumaSegmentosIniciales3 [1..3*10^6] == 4500004500001000000 |
Comprobar con QuickCheck que la suma de las sumas de los segmentos iniciales de la lista formada por n veces el número uno es el n-ésimo número triangular; es decir que
|
1 |
sumaSegmentosIniciales (genericReplicate n 1) |
es igual a
|
1 |
n * (n + 1) `div` 2 |
|
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 |
import Data.List (genericLength, genericReplicate) import Test.QuickCheck -- 1ª solución -- =========== sumaSegmentosIniciales :: [Integer] -> Integer sumaSegmentosIniciales xs = sum [sum (take k xs) | k <- [1.. length xs]] -- 2ª solución -- =========== sumaSegmentosIniciales2 :: [Integer] -> Integer sumaSegmentosIniciales2 xs = sum (zipWith (*) [n,n-1..1] xs) where n = genericLength xs -- 3ª solución -- =========== sumaSegmentosIniciales3 :: [Integer] -> Integer sumaSegmentosIniciales3 xs = sum (scanl1 (+) xs) -- Comprobación de la equivalencia -- =============================== -- La propiedad es prop_sumaSegmentosInicialesEquiv :: [Integer] -> Bool prop_sumaSegmentosInicialesEquiv xs = all (== sumaSegmentosIniciales xs) [f xs | f <- [ sumaSegmentosIniciales2 , sumaSegmentosIniciales3]] -- La comprobación es -- λ> quickCheck prop_sumaSegmentosInicialesEquiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> sumaSegmentosIniciales [1..10^4] -- 166716670000 -- (2.42 secs, 7,377,926,824 bytes) -- λ> sumaSegmentosIniciales2 [1..10^4] -- 166716670000 -- (0.01 secs, 4,855,176 bytes) -- -- λ> sumaSegmentosIniciales2 [1..3*10^6] -- 4500004500001000000 -- (2.68 secs, 1,424,404,168 bytes) -- λ> sumaSegmentosIniciales3 [1..3*10^6] -- 4500004500001000000 -- (1.54 secs, 943,500,384 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_sumaSegmentosIniciales :: Positive Integer -> Bool prop_sumaSegmentosIniciales (Positive n) = sumaSegmentosIniciales3 (genericReplicate n 1) == n * (n + 1) `div` 2 -- La compronación es -- λ> quickCheck prop_sumaSegmentosIniciales -- +++ OK, passed 100 tests. |
Al andar se hace camino,
y al volver la vista atrás
se ve la senda que nunca
se ha de volver a pisar.Antonio Machado
El número 23 se puede escribir de 4 formas como suma de sus dígitos
|
1 2 3 4 |
2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3 2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3 2 + 3 + 3 + 3 + 3 + 3 + 3 + 3 |
La de menor número de sumando es la última, que tiene 8 sumandos.
Definir las funciones
|
1 2 |
minimoSumandosDigitos :: Integer -> Integer graficaMinimoSumandosDigitos :: Integer -> IO () |
tales que
|
1 2 3 4 |
minimoSumandosDigitos 23 == 8 minimoSumandosDigitos 232 == 78 minimoSumandosDigitos 2323 == 775 map minimoSumandosDigitos [10..20] == [10,11,6,5,5,3,6,5,4,3,10] |
|
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 |
import Data.List (nub, genericLength, sort) import Graphics.Gnuplot.Simple minimoSumandosDigitos :: Integer -> Integer minimoSumandosDigitos n = minimoSumandos (digitos n) n -- (digitos n) es el conjunto de los dígitos no nulos de n. Por ejemplo, -- digitos 2032 == [2,3] digitos :: Integer -> [Integer] digitos n = nub [read [c] | c <- show n, c /= '0'] -- (minimoSumandos xs n) es el menor número de elementos de la lista de -- enteros positivos xs (con posibles repeticiones) cuya suma es n. Por -- ejemplo, -- minimoSumandos [7,2,4] 11 == 2 minimoSumandos :: [Integer] -> Integer -> Integer minimoSumandos xs n = minimum (mapo genericLength (sumas xs n)) -- (sumas xs n) es la lista de elementos de la lista de enteros -- positivos xs (con posibles repeticiones) cuya suma es n. Por ejemplo, -- sumas [7,2,4] 11 == [[7,2,2],[7,4]] sumas :: [Integer] -> Integer -> [[Integer]] sumas [] 0 = [[]] sumas [] _ = [] sumas (x:xs) n | x <= n = map (x:) (sumas (x:xs) (n-x)) ++ sumas xs n | otherwise = sumas xs n graficaMinimoSumandosDigitos :: Integer -> IO () graficaMinimoSumandosDigitos n = plotList [ Key Nothing , PNG "Numero_como_suma_de_sus_digitos.png" ] [minimoSumandosDigitos k | k <- [0..n-1]] |
Caminante, son tus huellas
el camino, y nada más;
caminante no hay camino,
se hace camino al andar.Antonio Machado
Las torres de Hanoi es un rompecabeza que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los N discos en el poste C.
Los postes se pueden representar mediante el siguiente tipo de datos
|
1 2 |
data Poste = A | B | C deriving Show |
Definir las funciones
|
1 2 |
movimientos :: Integer -> [(Integer,Poste,Poste)] hanoi :: Integer -> IO () |
tales que
|
1 2 3 4 5 6 |
λ> movimientos 1 [(1,A,C)] λ> movimientos 2 [(1,A,B),(2,A,C),(1,B,C)] λ> movimientos 3 [(1,A,C),(2,A,B),(1,C,B),(3,A,C),(1,B,A),(2,B,C),(1,A,C)] |
|
1 2 3 4 5 6 7 8 |
λ> hanoi 3 Mueve el disco 1 de A a C Mueve el disco 2 de A a B Mueve el disco 1 de C a B Mueve el disco 3 de A a C Mueve el disco 1 de B a A Mueve el disco 2 de B a C Mueve el disco 1 de A a C |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
data Poste = A | B | C deriving (Eq, Show) movimientos :: Integer -> [(Integer,Poste,Poste)] movimientos n = aux n A B C where aux n a b c | n == 1 = [(1,a,c)] | otherwise = aux (n-1) a c b ++ (n,a,c) : aux (n-1) b a c hanoi :: Integer -> IO () hanoi n = putStrLn (unlines (map mensaje (movimientos n))) -- (mensaje (n.x.y)) es la cadena indicando que el disco n se ha movido -- desde el poste x al poste y. Por ejemplo, -- λ> mensaje (1,A,B) -- "Mueve el disco 1 de A a B" mensaje :: (Integer,Poste,Poste) -> String mensaje (n,x,y) = "Mueve el disco " ++ show n ++ " de " ++ show x ++ " a " ++ show y |
En preguntar lo que sabes
el tiempo no has de perder …
Y a preguntas sin respuesta
¿quién te podrá responder?Antonio Machado