Matrices marco y transiciones

PorJosé A. Alonso 21-mayo-201513-junio-2015

Las posiciones frontera de una matriz de orden mxn son aquellas que están en la fila 1 o la fila m o la columna 1 o la columna n. El resto se dirán posiciones interiores. Observa que cada elemento en una posición interior tiene exactamente 8 vecinos en la matriz.

Dada una matriz, un paso de transición genera una nueva matriz de la misma dimensión pero en la que se ha sustituido cada elemento interior por la suma de sus 8 vecinos. Los elementos frontera no varían.

Definir las funciones

   marco      :: Int -> Int -> Integer -> Matrix Integer
   paso       :: Matrix Integer -> Matrix Integer
   itPasos    :: Int -> Matrix Integer -> Matrix Integer
   pasosHasta :: Integer -> Int

marco :: Int -> Int -> Integer -> Matrix Integer

paso :: Matrix Integer -> Matrix Integer

itPasos :: Int -> Matrix Integer -> Matrix Integer

pasosHasta :: Integer -> Int

tales que

(marco m n z) genera la matriz de dimensión mxn que contiene el entero z en las posiciones frontera y 0 en las posiciones interiores. Por ejemplo,

     ghci> marco 5 5 1
     ( 1 1 1 1 1 )
     ( 1 0 0 0 1 )
     ( 1 0 0 0 1 )
     ( 1 0 0 0 1 )
     ( 1 1 1 1 1 )

ghci> marco 5 5 1

( 1 1 1 1 1 )

( 1 0 0 0 1 )

( 1 1 1 1 1 )

(paso t) calcula la matriz generada tras aplicar un paso de transición a la matriz t. Por ejemplo,

     ghci> paso (marco 5 5 1)
     ( 1 1 1 1 1 )
     ( 1 5 3 5 1 )
     ( 1 3 0 3 1 )
     ( 1 5 3 5 1 )
     ( 1 1 1 1 1 )

ghci> paso (marco 5 5 1)

( 1 1 1 1 1 )

( 1 5 3 5 1 )

( 1 3 0 3 1 )

( 1 5 3 5 1 )

( 1 1 1 1 1 )

(itPasos k t) es la matriz obtenida tras aplicar k pasos de transición a partir de la matriz t. Por ejemplo,

     ghci> itPasos 10 (marco 5 5 1)
     (       1       1       1       1       1 )
     (       1 4156075 5878783 4156075       1 )
     (       1 5878783 8315560 5878783       1 )
     (       1 4156075 5878783 4156075       1 )
     (       1       1       1       1       1 )

ghci> itPasos 10 (marco 5 5 1)

( 1 1 1 1 1 )

( 1 4156075 5878783 4156075 1 )

( 1 5878783 8315560 5878783 1 )

( 1 4156075 5878783 4156075 1 )

( 1 1 1 1 1 )

(pasosHasta k) es el número de pasos de transición a partir de la matriz (marco 5 5 1) necesarios para que en la matriz resultante aparezca un elemento mayor que k. Por ejemplo,

     pasosHasta 4         ==  1
     pasosHasta 6         ==  2
     pasosHasta (2^2015)  ==  887

pasosHasta 4 == 1

pasosHasta 6 == 2

pasosHasta (2^2015) == 887

Soluciones

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer
marco m n z  = matrix m n f
    where f (i,j) | frontera m n (i,j) = z
                  | otherwise          = 0 

-- (frontera m n (i,j)) se verifica si (i,j) es una posición de la
-- frontera de las matrices de dimensión mxn.
frontera :: Int -> Int -> (Int,Int) -> Bool
frontera m n (i,j) = or [i == 1, i == m, j == 1, j == n]

paso :: Matrix Integer -> Matrix Integer
paso p = matrix m n f where
    m = nrows p
    n = ncols p
    f (i,j) 
        | frontera m n (i,j) = p!(i,j)
        | otherwise          = sum [p!(u,v) | (u,v) <- vecinos m n (i,j)]
    
-- (vecinos m n (i,j)) es la lista de las posiciones de los vecinos del
-- punto interior (i,j) en las matrices de dimensión mxn.
vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]
vecinos m n (i,j) = [(a,b) | a <- [i-1..i+1]
                           , b <- [j-1..j+1]
                           , (a,b) /= (i,j)]

itPasos :: Int -> Matrix Integer -> Matrix Integer 
itPasos k t = (iterate paso t) !! k 

pasosHasta :: Integer -> Int
pasosHasta k =
    length (takeWhile (\t -> menores t k) (iterate paso (marco 5 5 1)))

-- (menores p k) se verifica si los elementos de p son menores o
-- iguales que k. Por ejemplo, 
--    menores (itPasos 1 (marco 5 5 1)) 6  ==  True
--    menores (itPasos 1 (marco 5 5 1)) 4  ==  False
menores :: Matrix Integer -> Integer -> Bool
menores p k = all (<=k) (toList p)

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer

marco m n z = matrix m n f

where f (i,j) | frontera m n (i,j) = z

| otherwise = 0

-- (frontera m n (i,j)) se verifica si (i,j) es una posición de la

-- frontera de las matrices de dimensión mxn.

frontera :: Int -> Int -> (Int,Int) -> Bool

frontera m n (i,j) = or [i == 1, i == m, j == 1, j == n]

paso :: Matrix Integer -> Matrix Integer

paso p = matrix m n f where

m = nrows p

n = ncols p

f (i,j)

| frontera m n (i,j) = p!(i,j)

| otherwise = sum [p!(u,v) | (u,v) <- vecinos m n (i,j)]

-- (vecinos m n (i,j)) es la lista de las posiciones de los vecinos del

-- punto interior (i,j) en las matrices de dimensión mxn.

vecinos :: Int -> Int -> (Int,Int) -> [(Int,Int)]

vecinos m n (i,j) = [(a,b) | a <- [i-1..i+1]

, b <- [j-1..j+1]

, (a,b) /= (i,j)]

itPasos :: Int -> Matrix Integer -> Matrix Integer

itPasos k t = (iterate paso t) !! k

pasosHasta :: Integer -> Int

pasosHasta k =

length (takeWhile (\t -> menores t k) (iterate paso (marco 5 5 1)))

-- (menores p k) se verifica si los elementos de p son menores o

-- iguales que k. Por ejemplo,

-- menores (itPasos 1 (marco 5 5 1)) 6 == True

-- menores (itPasos 1 (marco 5 5 1)) 4 == False

menores :: Matrix Integer -> Integer -> Bool

menores p k = all (<=k) (toList p)

4 Comentarios

import           Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer
marco m n z = matrix m n f
    where f (i,j) | esInterior (m,n) (i,j)  = 0
                  | otherwise               = z

paso :: Matrix Integer -> Matrix Integer
paso t = matrix m n suma
    where
        (m,n) = (nrows t, ncols t)
        vecinos (i,j) = [ t!(i+x,j+y) | x <- [-1..1], y <- [-1..1], (x,y) /= (0,0)]
        suma (i,j) | esInterior (m,n) (i,j) = sum $ vecinos (i,j)
                   | otherwise              = t!(i,j)

itPasos :: Int -> Matrix Integer -> Matrix Integer
itPasos k = foldr1 (.) (replicate k paso)

pasosHasta :: Integer -> Int
pasosHasta k = aux (marco 5 5 1)
    where aux t | any (> k) (toList t) = 0
                | otherwise            = 1 + aux (paso t)

esInterior :: (Int, Int) -> (Int, Int) -> Bool
esInterior (m,n) (i,j) = 1 < i && i < m && 1 < j && j < n

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer

marco m n z = matrix m n f

where f (i,j) | esInterior (m,n) (i,j) = 0

| otherwise = z

paso :: Matrix Integer -> Matrix Integer

paso t = matrix m n suma

where

(m,n) = (nrows t, ncols t)

vecinos (i,j) = [ t!(i+x,j+y) | x <- [-1..1], y <- [-1..1], (x,y) /= (0,0)]

suma (i,j) | esInterior (m,n) (i,j) = sum $ vecinos (i,j)

| otherwise = t!(i,j)

itPasos :: Int -> Matrix Integer -> Matrix Integer

itPasos k = foldr1 (.) (replicate k paso)

pasosHasta :: Integer -> Int

pasosHasta k = aux (marco 5 5 1)

where aux t | any (> k) (toList t) = 0

| otherwise = 1 + aux (paso t)

esInterior :: (Int, Int) -> (Int, Int) -> Bool

esInterior (m,n) (i,j) = 1 < i && i < m && 1 < j && j < n

Responder

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer
marco n m z = matrix n m (\(i,j) -> f (i,j))
    where f (i,j) | i == 1 || i == n = z
                  | j == 1 || j == m = z
                  | otherwise = 0

paso :: Matrix Integer -> Matrix Integer 
paso p = matrix n m (\(i,j) -> f (i,j)) where  
    f (i,j) | i == 1 || i == n = p!(i,j)
            | j == 1 || j == m = p!(i,j)
            | otherwise = sumaVecinos (i,j)
    sumaVecinos (a,b) = sum[p!(x,y) | x <- [a-1,a,a+1]
                                    , y <- [b-1,b,b+1]
                                    , (x,y) /= (a,b)]
    n = nrows p
    m = ncols p

itPasos :: Integer -> Matrix Integer -> Matrix Integer
itPasos 0 t = t
itPasos k t = paso (itPasos (k-1) t)

pasosHasta :: Integer -> Int
pasosHasta k = aux 0 t
    where aux v t | any (>k) [t!(i,j) | i <- [1..n], j <- [1..m]] = v
                  | otherwise = aux (v+1) (paso t)
          n = nrows t
          m = ncols t
          t = marco 5 5 1

-- PasosHasta' realiza lo mismo que pasosHasta, solo que para
-- cualquier matriz, no solo para la matriz (marco 5 5 1). 

pasosHasta' :: Integer -> Matrix Integer -> Int
pasosHasta' k t = aux 0 t
    where aux v t | any (>k) [t!(i,j) | i <- [1..n], j <- [1..m]] = v
                  | otherwise = aux (v+1) (paso t)
          n = nrows t
          m = ncols t

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer

marco n m z = matrix n m (\(i,j) -> f (i,j))

where f (i,j) | i == 1 || i == n = z

| j == 1 || j == m = z

| otherwise = 0

paso :: Matrix Integer -> Matrix Integer

paso p = matrix n m (\(i,j) -> f (i,j)) where

f (i,j) | i == 1 || i == n = p!(i,j)

| j == 1 || j == m = p!(i,j)

| otherwise = sumaVecinos (i,j)

sumaVecinos (a,b) = sum[p!(x,y) | x <- [a-1,a,a+1]

, y <- [b-1,b,b+1]

, (x,y) /= (a,b)]

n = nrows p

m = ncols p

itPasos :: Integer -> Matrix Integer -> Matrix Integer

itPasos 0 t = t

itPasos k t = paso (itPasos (k-1) t)

pasosHasta :: Integer -> Int

pasosHasta k = aux 0 t

where aux v t | any (>k) [t!(i,j) | i <- [1..n], j <- [1..m]] = v

| otherwise = aux (v+1) (paso t)

n = nrows t

m = ncols t

t = marco 5 5 1

-- PasosHasta' realiza lo mismo que pasosHasta, solo que para

-- cualquier matriz, no solo para la matriz (marco 5 5 1).

pasosHasta' :: Integer -> Matrix Integer -> Int

pasosHasta' k t = aux 0 t

where aux v t | any (>k) [t!(i,j) | i <- [1..n], j <- [1..m]] = v

| otherwise = aux (v+1) (paso t)

n = nrows t

m = ncols t

Responder

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer
marco m n z = matrix m n f
    where f (i,j) | or [i == 1, i == m, j == 1, j == n] = z
                  | otherwise = 0
          
paso :: Matrix Integer -> Matrix Integer
paso t = matrix m n f
     where vecinos (i,j) = [t!(i+x,j+y) | x <- [-1,0,1]
                                        , y <- [-1,0,1]
                                        , (x,y) /= (0,0)]
           (m,n) = (nrows t,nrows t)
           exterior (i,j) = or [i == 1, i == m, j == 1, j == n]
           f k | exterior k = t!k
               | otherwise = sum $ vecinos k

itPasos :: Int -> Matrix Integer -> Matrix Integer
itPasos k t= (iterate paso t)!!k

pasosHasta :: Integer -> Int
pasosHasta n = length $ takeWhile p (iterate paso t)
        where p t = all (<=n) [getElem i j t | i <- [1..nrows t]
                                             , j <- [1..ncols t]] 
              t = marco 5 5 1

import Data.Matrix

marco :: Int -> Int -> Integer -> Matrix Integer

marco m n z = matrix m n f

where f (i,j) | or [i == 1, i == m, j == 1, j == n] = z

| otherwise = 0

paso :: Matrix Integer -> Matrix Integer

paso t = matrix m n f

where vecinos (i,j) = [t!(i+x,j+y) | x <- [-1,0,1]

, y <- [-1,0,1]

, (x,y) /= (0,0)]

(m,n) = (nrows t,nrows t)

exterior (i,j) = or [i == 1, i == m, j == 1, j == n]

f k | exterior k = t!k

| otherwise = sum $ vecinos k

itPasos :: Int -> Matrix Integer -> Matrix Integer

itPasos k t= (iterate paso t)!!k

pasosHasta :: Integer -> Int

pasosHasta n = length $ takeWhile p (iterate paso t)

where p t = all (<=n) [getElem i j t | i <- [1..nrows t]

, j <- [1..ncols t]]

t = marco 5 5 1

Responder

import Data.Matrix

actualiza :: Matrix Integer -> [((Int,Int),Integer)] -> Matrix Integer
actualiza t [] = t
actualiza t ((p,k):xs) = actualiza (setElem k p t) xs

marco :: Int -> Int -> Integer -> Matrix Integer
marco m n z =
    actualiza (zero m n) ([((i,j),z) | i <- [1,m], j <- [1..n]] ++
                          [((i,j),z) | j <- [1,n], i <- [1..n]])

paso :: Matrix Integer -> Matrix Integer
paso t = actualiza t [((i,j),vecinos i j) | i <- [2..m-1],
                                            j <- [2..n-1]]
    where (m,n) = (nrows t, ncols t)
          vecinos i j = sum [t ! (k,l) | k <- [i-1..i+1],
                                         l <- [j-1..j+1],
                                         (k,l) /= (i,j)]

itPasos :: Int -> Matrix Integer -> Matrix Integer
itPasos k t = iterate paso t !! k

pasosHasta :: Integer -> Int
pasosHasta k | elem k [0,1]   = 0
             | elem k [2,3,4] = 1
             | otherwise      = elementoCentral 2
             where elementoCentral n
                       | k < itPasos n (marco 5 5 1) ! (3,3) = n
                       | otherwise = elementoCentral (n+1)

import Data.Matrix

actualiza :: Matrix Integer -> [((Int,Int),Integer)] -> Matrix Integer

actualiza t [] = t

actualiza t ((p,k):xs) = actualiza (setElem k p t) xs

marco :: Int -> Int -> Integer -> Matrix Integer

marco m n z =

actualiza (zero m n) ([((i,j),z) | i <- [1,m], j <- [1..n]] ++

[((i,j),z) | j <- [1,n], i <- [1..n]])

paso :: Matrix Integer -> Matrix Integer

paso t = actualiza t [((i,j),vecinos i j) | i <- [2..m-1],

j <- [2..n-1]]

where (m,n) = (nrows t, ncols t)

vecinos i j = sum [t ! (k,l) | k <- [i-1..i+1],

l <- [j-1..j+1],

(k,l) /= (i,j)]

itPasos :: Int -> Matrix Integer -> Matrix Integer

itPasos k t = iterate paso t !! k

pasosHasta :: Integer -> Int

pasosHasta k | elem k [0,1] = 0

| elem k [2,3,4] = 1

| otherwise = elementoCentral 2

where elementoCentral n

| k < itPasos n (marco 5 5 1) ! (3,3) = n

| otherwise = elementoCentral (n+1)

Responder

Matrices marco y transiciones

Soluciones

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico