Menu Close

Matrices de Pascal

El triángulo de Pascal es un triángulo de números

         1
        1 1
       1 2 1
     1  3 3  1
    1 4  6  4 1
   1 5 10 10 5 1
  ...............

construido de la siguiente forma

  • la primera fila está formada por el número 1;
  • las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

La matriz de Pascal es la matriz cuyas filas son los elementos de la
correspondiente fila del triángulo de Pascal completadas con ceros. Por ejemplo, la matriz de Pascal de orden 6 es

   |1 0  0  0 0 0|
   |1 1  0  0 0 0|
   |1 2  1  0 0 0|
   |1 3  3  1 0 0|
   |1 4  6  4 1 0|
   |1 5 10 10 5 1|

Definir la función

   matrizPascal :: Int -> Matrix Integer

tal que (matrizPascal n) es la matriz de Pascal de orden n. Por ejemplo,

   λ> matrizPascal 6
   (  1  0  0  0  0  0 )
   (  1  1  0  0  0  0 )
   (  1  2  1  0  0  0 )
   (  1  3  3  1  0  0 )
   (  1  4  6  4  1  0 )
   (  1  5 10 10  5  1 )

Soluciones

import Data.Matrix
 
-- 1ª solución
-- ===========
 
matrizPascal :: Int -> Matrix Integer 
matrizPascal 1 = fromList 1 1 [1]
matrizPascal n = matrix n n f 
  where f (i,j) | i < n && j <  n  = p!(i,j)
                | i < n && j == n  = 0
                | j == 1 || j == n = 1
                | otherwise        = p!(i-1,j-1) + p!(i-1,j)
        p = matrizPascal (n-1)
 
-- 2ª solución
-- ===========
 
matrizPascal2 :: Int -> Matrix Integer
matrizPascal2 n = fromLists xss
  where yss = take n pascal
        xss = map (take n) (map (++ repeat 0) yss)
 
pascal :: [[Integer]]
pascal = [1] : map f pascal
    where f xs = zipWith (+) (0:xs) (xs ++ [0])
 
-- 3ª solución
-- ===========
 
matrizPascal3 :: Int -> Matrix Integer
matrizPascal3 n =  matrix n n f
  where f (i,j) | i >=  j   = comb (i-1) (j-1)
                | otherwise = 0
 
-- (comb n k) es el número de combinaciones (o coeficiente binomial) de
-- n sobre k. Por ejemplo,
comb :: Int -> Int -> Integer
comb n k = product [n',n'-1..n'-k'+1] `div` product [1..k']
  where n' = fromIntegral n
        k' = fromIntegral k
 
-- 4ª solución
-- ===========
 
matrizPascal4 :: Int -> Matrix Integer
matrizPascal4 n = p
  where p = matrix n n (\(i,j) -> f i j)
        f i 1 = 1
        f i j
          | j >  i    = 0
          | i == j    = 1
          | otherwise = p!(i-1,j) + p!(i-1,j-1)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> maximum (matrizPascal 150)
--    46413034868354394849492907436302560970058760
--    (2.58 secs, 394,030,504 bytes)
--    λ> maximum (matrizPascal2 150)
--    46413034868354394849492907436302560970058760
--    (0.03 secs, 8,326,784 bytes)
--    λ> maximum (matrizPascal3 150)
--    46413034868354394849492907436302560970058760
--    (0.38 secs, 250,072,360 bytes)
--    λ> maximum (matrizPascal4 150)
--    46413034868354394849492907436302560970058760
--    (0.10 secs, 13,356,360 bytes)
--    
--    λ> length (show (maximum (matrizPascal2 300)))
--    89
--    (0.06 secs, 27,286,296 bytes)
--    λ> length (show (maximum (matrizPascal3 300)))
--    89
--    (2.74 secs, 2,367,037,536 bytes)
--    λ> length (show (maximum (matrizPascal4 300)))
--    89
--    (0.36 secs, 53,934,792 bytes)
--    
--    λ> length (show (maximum (matrizPascal2 700)))
--    209
--    (0.83 secs, 207,241,080 bytes)
--    λ> length (show (maximum (matrizPascal4 700)))
--    209
--    (2.22 secs, 311,413,008 bytes)

4 soluciones de “Matrices de Pascal

  1. angruicam1
    import Data.Matrix (Matrix, fromLists)
     
    matrizPascal :: Int -> Matrix Integer
    matrizPascal n =
      fromLists (take n (iterate ((1:) . aux) (1: replicate (n-1) 0)))
      where aux (x:y:xs) = x+y : aux (y:xs)
            aux _        = []
    • angruicam1

      Otra solución usando la programación dinámica:

      import Data.Matrix (Matrix, matrix, (!))
       
      matrizPascal :: Int -> Matrix Integer
      matrizPascal n = p
        where p = matrix n n ((i,j) -> f i j)
              f i 1 = 1
              f i j
                | j >  i    = 0
                | i == j    = 1
                | otherwise = p!(i-1,j) + p!(i-1,j-1)
  2. jaiturrod
     
    import Data.Matrix
     
    matrizPascal :: Int -> Matrix Integer
    matrizPascal n = fromLists [(filaPascal t) ++ (replicate (n-t) 0)| t <- [1..n]]
     
    filaPascal :: Int -> [Integer]
    filaPascal 1 = [1]
    filaPascal 2 = [1,1]
    filaPascal n = [1] ++ zipWith (+) (filaPascal (n-1)) (tail(filaPascal(n-1))) ++ [1]
  3. carriomon1

    Una solución en Maxima

    matrizPascal (n) := block (local (f),
      f[i,j] := if     j = 1 then 1
                elseif i < j then 0
                elseif i = j then 1
                else              f[i-1,j-1] + f[i-1,j],
      genmatrix (f,n,n))$

Escribe tu solución

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