I1M2015: Resolución de una ecuación con factoriales en Haskell
En la primera parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los ejercicios de la relación 28, cuyo objetivo es resolver la ecuación a! * b! = a! + b! + c!, donde a, b y c son números naturales.
Los ejercicios, y sus soluciones, se muestran a continuación.
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 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- El objetivo de esta relación de ejercicios es resolver la ecuación -- a! * b! = a! + b! + c! -- donde a, b y c son números naturales. -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- factorial :: Integer -> Integer -- tal que (factorial n) es el factorial de n. Por ejemplo, -- factorial 5 == 120 -- --------------------------------------------------------------------- factorial :: Integer -> Integer factorial n = product [1..n] -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la constante -- factoriales :: [Integer] -- tal que factoriales es la lista de los factoriales de los números -- naturales. Por ejemplo, -- take 7 factoriales == [1,1,2,6,24,120,720] -- --------------------------------------------------------------------- -- 1ª definición factoriales1 :: [Integer] factoriales1 = [factorial n | n <- [0..]] factoriales2 :: [Integer] factoriales2 = 1 : scanl1 (*) [1..] -- Comparación de eficiencia -- λ> length (show (factoriales1 !! 50000)) -- 213237 -- (2.66 secs, 2,623,591,360 bytes) -- λ> length (show (factoriales2 !! 50000)) -- 213237 -- (1.23 secs, 2,610,366,712 bytes) -- Usaremos la 2ª definición factoriales :: [Integer] factoriales = factoriales2 -- --------------------------------------------------------------------- -- Ejercicio 3. Definir, usando factoriales, la función -- esFactorial :: Integer -> Bool -- tal que (esFactorial n) se verifica si existe un número natural m -- tal que n es m!. Por ejemplo, -- esFactorial 120 == True -- esFactorial 20 == False -- --------------------------------------------------------------------- esFactorial :: Integer -> Bool esFactorial n = n == head (dropWhile (<n) factoriales) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la constante -- posicionesFactoriales :: [(Integer,Integer)] -- tal que posicionesFactoriales es la lista de los factoriales con su -- posición. Por ejemplo, -- ghci> take 7 posicionesFactoriales -- [(0,1),(1,1),(2,2),(3,6),(4,24),(5,120),(6,720)] -- --------------------------------------------------------------------- posicionesFactoriales :: [(Integer,Integer)] posicionesFactoriales = zip [0..] factoriales -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- invFactorial :: Integer -> Maybe Integer -- tal que (invFactorial x) es (Just n) si el factorial de n es x y es -- Nothing, en caso contrario. Por ejemplo, -- invFactorial 120 == Just 5 -- invFactorial 20 == Nothing -- --------------------------------------------------------------------- invFactorial :: Integer -> Maybe Integer invFactorial x | esFactorial x = Just (head [n | (n,y) <- posicionesFactoriales, y==x]) | otherwise = Nothing -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la constante -- pares :: [(Integer,Integer)] -- tal que pares es la lista de todos los pares de números naturales. Por -- ejemplo, -- ghci> take 11 pares -- [(0,0),(0,1),(1,1),(0,2),(1,2),(2,2),(0,3),(1,3),(2,3),(3,3),(0,4)] -- --------------------------------------------------------------------- pares :: [(Integer,Integer)] pares = [(x,y) | y <- [0..], x <- [0..y]] -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la constante -- solucionFactoriales :: (Integer,Integer,Integer) -- tal que solucionFactoriales es una terna (a,b,c) que es una solución -- de la ecuación -- a! * b! = a! + b! + c! -- Calcular el valor de solucionFactoriales. -- --------------------------------------------------------------------- solucionFactoriales :: (Integer,Integer,Integer) solucionFactoriales = (a,b,c) where (a,b) = head [(x,y) | (x,y) <- pares, esFactorial (f x * f y - f x - f y)] f = factorial Just c = invFactorial (f a * f b - f a - f b) -- El cálculo es -- ghci> solucionFactoriales -- (3,3,4) -- --------------------------------------------------------------------- -- Ejercicio 8. Comprobar con QuickCheck que solucionFactoriales es la -- única solución de la ecuación -- a! * b! = a! + b! + c! -- con a, b y c números naturales -- --------------------------------------------------------------------- prop_solucionFactoriales :: Integer -> Integer -> Integer -> Property prop_solucionFactoriales x y z = x >= 0 && y >= 0 && z >= 0 && (x,y,z) /= solucionFactoriales ==> not (f x * f y == f x + f y + f z) where f = factorial -- La comprobación es -- ghci> quickCheck prop_solucionFactoriales -- *** Gave up! Passed only 86 tests. -- También se puede expresar como prop_solucionFactoriales1 :: Integer -> Integer -> Integer -> Property prop_solucionFactoriales1 x y z = x >= 0 && y >= 0 && z >= 0 && f x * f y == f x + f y + f z ==> (x,y,z) == solucionFactoriales where f = factorial -- La comprobación es -- ghci> quickCheck prop_solucionFactoriales -- *** Gave up! Passed only 0 tests. -- --------------------------------------------------------------------- -- Nota: El ejercicio se basa en el artículo "Ecuación con factoriales" -- del blog Gaussianos publicado en -- http://gaussianos.com/ecuacion-con-factoriales -- --------------------------------------------------------------------- |