Menu Close

Triángulo de Euler

El triángulo de Euler se construye a partir de las siguientes relaciones

   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 
   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:

  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,
     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,
     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
     λ> 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

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

Avanzado

4 soluciones de “Triángulo de Euler

  1. frahidzam
    import Data.Array
     
    matrizEuler :: Integer -> Integer -> Array (Integer,Integer) Integer
    matrizEuler n m = p
      where p = array ((1,1),(n,m)) [((i,j),f i j) | i <- [1..n], j <- [1..m]]
            f i j | j == 1    = 1
                  | i == j    = 1
                  | i < j     = 0
                  | otherwise = (i-j+1)*(p!(i-1,j-1)) + (j*(p!(i-1,j)))
     
    numeroEuler :: Integer -> Integer -> Integer
    numeroEuler n k = (matrizEuler n (k+1)) ! (n,k+1)
     
    filaTrianguloEuler :: Integer -> [Integer]
    filaTrianguloEuler n = [p!(n,a) | a <- [1..n]]
      where p = matrizEuler n n
     
    trianguloEuler :: [[Integer]]
    trianguloEuler = [filaTrianguloEuler a | a <- [1..]]
  2. adogargon
    import Data.Array
     
    numeroEuler :: Integer -> Integer -> Integer
    numeroEuler n m = sum [((-1)^k)*(comb (n+1) k)*(m+1-k)^n | k <- [0..m]]
     
    comb ::  Integer -> Integer -> Integer
    comb n k = div (fact n) ((fact(n-k))*(fact k))
     
    fact :: Integer -> Integer
    fact 0 = 1
    fact n = product [1..n]
     
    filaTrianguloEuler :: Integer -> [Integer]
    filaTrianguloEuler n = [ numeroEuler n k | k <- [0..(n-1)]]
     
    trianguloEuler :: [[Integer]]
    trianguloEuler = map filaTrianguloEuler $! [1..]
  3. luipromor
    import Data.Array
     
    numeroEuler :: Integer -> Integer -> Integer
    numeroEuler x c = v ! (x-1,c)
      where v = array ((0,0),(x,c)) [((i,j),f (i,j)) | i <- [0..x], j <- [0..c]]
            f (n,0) = 1
            f (0,0) = 1                
            f (n,m) | m   == n  = 1
                    | m > n     = 0
                    | otherwise = (n-m+1) * v ! (n-1,m-1) + (m+1) * v ! (n-1,m)
     
    filaTrianguloEuler :: Integer -> [Integer]
    filaTrianguloEuler x = [v ! (x-1,c) | c <- [0..x-1]]
       where v  = array ((0,0),(x,x-1)) [((i,j),f (i,j)) | i <- [0..x], j <- [0..x-1]]
             f (n,0) = 1
             f (0,0) = 1                
             f (n,m) | m   == n = 1
                     | m > n = 0
                     | otherwise = (n-m+1) * v ! (n-1,m-1) + (m+1) * v ! (n-1,m)
     
    trianguloEuler :: [[Integer]]
    trianguloEuler =  [filaTrianguloEuler n | n <- [1..]]
  4. javmarcha1
    import Data.Vector as V
    import Data.Matrix as M
     
    numeroEuler :: Int -> Int -> Integer 
    numeroEuler i j = matrizEuler2 (i+1) (j+1) M.! (i,j+1)      
     
    filaTrianguloEuler :: Int -> [Integer]
    filaTrianguloEuler i = V.toList(M.getRow i (matrizEuler2 i i))
     
    trianguloEuler :: [[Integer]]
    trianguloEuler = [filaTrianguloEuler i | i <- [1..]]
     
    matrizEuler2 :: Int -> Int -> Matrix Integer
    matrizEuler2 a b = m
      where m = matrix a b ((i,j) -> toInteger(f i j))
            f i j | i == j || j == 1 = 1
                  | j > i = 0 
                  | otherwise = (toInteger(1+i-j))*(m M.!((i-1),(j-1)))
                    + (toInteger(j))*(m M.!((i-1),j))

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.