Triángulo de Euler
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
- (numeroEuler n k) es el número de Euler A(n,k). Por ejemplo,
|
1 2 3 |
numeroEuler 8 3 == 15619 numeroEuler 20 6 == 21598596303099900 length (show (numeroEuler 1000 500)) == 2567 |
- (filaTrianguloEuler n) es la n-ésima fila del triángulo de Euler. Por ejemplo,
|
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 |
- trianguloEuler es la lista con las filas del triángulo de Euler
|
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 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 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) |
Pensamiento
Señor San Jerónimo,
suelte usted la piedra
con que se machaca.
Me pegó con ella.Antonio Machado
4 Comentarios