I1M2014: Resolución de una ecuación con factoriales en Haskell
En la segunda 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 21, 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 |
-- I1M 2014-15: Relación 21 (26 de febrero de 2015) -- Ecuación con factoriales. -- Departamento de Ciencias de la Computación e I.A. -- Universidad de Sevilla -- ===================================================================== -- --------------------------------------------------------------------- -- 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..]] -- 2ª definición factoriales2 :: [Integer] factoriales2 = scanl (*) 1 [1..] -- Comparación de eficiencia: -- ghci> let n = factoriales !! 30000 in n-n -- 0 -- (3.20 secs, 723071452 bytes) -- ghci> let n = factoriales2 !! 30000 in n-n -- 0 -- (3.16 secs, 721944872 bytes) -- ghci> let n = factoriales3 !! 30000 in n-n -- 0 -- (1.74 secs, 720384724 bytes) -- Usaremos como factoriales 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 -- +++ OK, passed 100 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 -- --------------------------------------------------------------------- |