Exercitium

Matrices cruzadas

PorJosé A. Alonso 24-marzo-20151-mayo-2015

Consideramos las matrices representadas como tablas cuyos índices son pares de números naturales.

   type Matriz a = Array (Int,Int) a

1	type Matriz a = Array (Int,Int) a

Una matriz cruzada es una matriz cuadrada en la que sólo hay elementos distintos de 0 en las diagonales principal y secundaria. Por ejemplo,

   | 1 0 0 0 3 |     | 1 0 0 3 |
   | 0 2 0 1 0 |     | 0 2 3 0 |
   | 0 0 3 0 0 |     | 0 4 5 0 |
   | 0 2 0 1 0 |     | 2 0 0 3 |
   | 1 0 0 0 3 |

| 1 0 0 0 3 | | 1 0 0 3 |

| 0 2 0 1 0 | | 0 2 3 0 |

| 0 0 3 0 0 | | 0 4 5 0 |

| 0 2 0 1 0 | | 2 0 0 3 |

| 1 0 0 0 3 |

Definir la función

   creaCruzada :: Int -> Matriz Int

1	creaCruzada :: Int -> Matriz Int

tal que (creaCruzada n) es la siguiente matriz cruzada con n filas y n columnas:

   | 1  0   0  ...  0   0  1 |
   | 0  2   0  ...  0   2  0 |
   | 0  0   3  ...  3   0  0 |
   | ....................... |
   | 0  0  n-2 ... n-2  0  0 |
   | 0 n-1  0  ...  0  n-1 0 |
   | n  0   0  ...  0   0  n |

| 1 0 0 ... 0 0 1 |

| 0 2 0 ... 0 2 0 |

| 0 0 3 ... 3 0 0 |

| ....................... |

| 0 0 n-2 ... n-2 0 0 |

| 0 n-1 0 ... 0 n-1 0 |

| n 0 0 ... 0 0 n |

Es decir, los elementos de la diagonal principal son [1,…,n], en orden desde la primera fila hasta la última; y los elementos de la diagonal secundaria son [1,…,n], en orden desde la primera fila hasta la última. Por ejemplo,

   ghci> elems (creaCruzada 3)
   [1,0,1, 0,2,0, 3,0,3]
   ghci> elems (creaCruzada 4)
   [1,0,0,1, 0,2,2,0, 0,3,3,0, 4,0,0,4]
   ghci> elems (creaCruzada 5)
   [1,0,0,0,1, 0,2,0,2,0, 0,0,3,0,0, 0,4,0,4,0, 5,0,0,0,5]

ghci> elems (creaCruzada 3)

[1,0,1, 0,2,0, 3,0,3]

ghci> elems (creaCruzada 4)

[1,0,0,1, 0,2,2,0, 0,3,3,0, 4,0,0,4]

ghci> elems (creaCruzada 5)

[1,0,0,0,1, 0,2,0,2,0, 0,0,3,0,0, 0,4,0,4,0, 5,0,0,0,5]

Soluciones

import Data.Array

type Matriz a = Array (Int,Int) a

-- 1ª solución
creaCruzada1 :: Int -> Matriz Int
creaCruzada1 n =
    array ((1,1),(n,n))
          [((i,j),f i j) | i <- [1..n], j <- [1..n]]
    where f i j | i == j     = i
                | i+j == n+1 = i
                | otherwise  = 0

-- 2ª solución
creaCruzada2 :: Int -> Matriz Int
creaCruzada2 n = listArray t [f i j| (i,j) <- range t]
    where t = ((1,1),(n,n))
          f i j | i == j     = i
                | i+j == n+1 = i
                | otherwise  = 0

-- 3ª solución
creaCruzada3 :: Int -> Matriz Int
creaCruzada3 n = 
    listArray ((1,1),(n,n)) 
              (replicate (n^2) 0) // ([((i,i),i) | i <- [1..n]] ++ 
                                     [((i,n-i+1),i)| i <- [n,n-1..1]])

creaCruzada4 :: Int -> Matriz Int
creaCruzada4 n = 
    accumArray (\x y -> y) 0 ((1,1),(n,n))
               (concat [[((i,i),i),((i,n+1-i),i)] | i <- [1..n]])

-- Comparación de eficiencia
--    ghci> let n = 2000 in creaCruzada1 n ! (n,n)
--    2000
--    (6.13 secs, 896997468 bytes)
--    
--    ghci> let n = 2000 in creaCruzada2 n ! (n,n)
--    2000
--    (3.83 secs, 433675668 bytes)
--    
--    ghci> let n = 2000 in creaCruzada3 n ! (n,n)
--    2000
--    (0.56 secs, 145741748 bytes)
--    
--    ghci> let n = 2000 in creaCruzada4 n ! (n,n)
--    2000
--    (0.27 secs, 37373392 bytes)

import Data.Array

type Matriz a = Array (Int,Int) a

-- 1ª solución

creaCruzada1 :: Int -> Matriz Int

creaCruzada1 n =

array ((1,1),(n,n))

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

where f i j | i == j = i

| i+j == n+1 = i

| otherwise = 0

-- 2ª solución

creaCruzada2 :: Int -> Matriz Int

creaCruzada2 n = listArray t [f i j| (i,j) <- range t]

where t = ((1,1),(n,n))

f i j | i == j = i

| i+j == n+1 = i

| otherwise = 0

-- 3ª solución

creaCruzada3 :: Int -> Matriz Int

creaCruzada3 n =

listArray ((1,1),(n,n))

(replicate (n^2) 0) // ([((i,i),i) | i <- [1..n]] ++

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

creaCruzada4 :: Int -> Matriz Int

creaCruzada4 n =

accumArray (\x y -> y) 0 ((1,1),(n,n))

(concat [[((i,i),i),((i,n+1-i),i)] | i <- [1..n]])

-- Comparación de eficiencia

-- ghci> let n = 2000 in creaCruzada1 n ! (n,n)

-- 2000

-- (6.13 secs, 896997468 bytes)

-- ghci> let n = 2000 in creaCruzada2 n ! (n,n)

-- 2000

-- (3.83 secs, 433675668 bytes)

-- ghci> let n = 2000 in creaCruzada3 n ! (n,n)

-- 2000

-- (0.56 secs, 145741748 bytes)

-- ghci> let n = 2000 in creaCruzada4 n ! (n,n)

-- 2000

-- (0.27 secs, 37373392 bytes)

Caminos maximales en árboles binarios

PorJosé A. Alonso 23-marzo-20151-mayo-2015

Consideremos los árboles binarios con etiquetas en las hojas y en los nodos. Por ejemplo,

/ \

2 4

/ \

7 1

/ \

2 3

Un camino es una sucesión de nodos desde la raiz hasta una hoja. Por ejemplo, [5,2] y [5,4,1,2] son caminos que llevan a 2, mientras que [5,4,1] no es un camino, pues no lleva a una hoja.

Definimos el tipo de dato Arbol y el ejemplo por

   data Arbol = H Int | N Arbol Int Arbol 
                deriving Show
   
   arb1:: Arbol 
   arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3)))

data Arbol = H Int | N Arbol Int Arbol

deriving Show

arb1:: Arbol

arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3)))

Definir la función

   maxLong :: Int -> Arbol -> Int

1	maxLong :: Int -> Arbol -> Int

tal que (maxLong x a) es la longitud máxima de los caminos que terminan en x. Por ejemplo,

   maxLong 3 arb1 == 4
   maxLong 2 arb1 == 4
   maxLong 7 arb1 == 3

maxLong 3 arb1 == 4

maxLong 2 arb1 == 4

maxLong 7 arb1 == 3

Soluciones

data Arbol = H Int | N Arbol Int Arbol 
             deriving Show

arb1:: Arbol 
arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3)))

-- 1ª solución (calculando los caminos)
-- ------------------------------------

-- (caminos x a) es la lista de los caminos en el árbol a desde la raíz
-- hasta las hojas x. Por ejemplo,
--    caminos 2 arb1 == [[5,2],[5,4,1,2]]
--    caminos 3 arb1 == [[5,4,1,3]]
--    caminos 1 arb1 == []
caminos :: Int -> Arbol -> [[Int]]
caminos x (H y) | x == y    = [[x]]
                | otherwise = []
caminos x (N i r d) = map (r:) (caminos x i ++ caminos x d)

maxLong1 :: Int -> Arbol -> Int
maxLong1 x a = maximum (0: map length (caminos x a))

-- 2ª solución
-- -----------

maxLong2 :: Int -> Arbol -> Int
maxLong2 x a = maximum (0 : aux x a)
    where aux x (H y) | x == y    = [1]
                      | otherwise = []
          aux x (N i r d) = map (+1) (aux x i ++ aux x d)

data Arbol = H Int | N Arbol Int Arbol

deriving Show

arb1:: Arbol

arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3)))

-- 1ª solución (calculando los caminos)

-- ------------------------------------

-- (caminos x a) es la lista de los caminos en el árbol a desde la raíz

-- hasta las hojas x. Por ejemplo,

-- caminos 2 arb1 == [[5,2],[5,4,1,2]]

-- caminos 3 arb1 == [[5,4,1,3]]

-- caminos 1 arb1 == []

caminos :: Int -> Arbol -> [[Int]]

caminos x (H y) | x == y = [[x]]

| otherwise = []

caminos x (N i r d) = map (r:) (caminos x i ++ caminos x d)

maxLong1 :: Int -> Arbol -> Int

maxLong1 x a = maximum (0: map length (caminos x a))

-- 2ª solución

-- -----------

maxLong2 :: Int -> Arbol -> Int

maxLong2 x a = maximum (0 : aux x a)

where aux x (H y) | x == y = [1]

| otherwise = []

aux x (N i r d) = map (+1) (aux x i ++ aux x d)

Máximos locales de una matriz

PorJosé A. Alonso 20-marzo-20151-mayo-2015

Un elemento de una matriz es un máximo local si es mayor que todos sus vecinos. Por ejemplo, en la matriz

    [[1,0,0,8],
     [0,2,0,3],
     [0,0,0,5],
     [3,5,7,6],
     [1,2,3,4]]

[[1,0,0,8],

[0,2,0,3],

[0,0,0,5],

[3,5,7,6],

[1,2,3,4]]

los máximos locales son 8 (en la posición (1,4)), 2 (en la posición (2,2)) y 7 (en la posición (4,3)).

Definimos el tipo de las matrices, mediante

   type Matriz a = Array (Int,Int) Int

1	type Matriz a = Array (Int,Int) Int

y el ejemplo anterior por

   ej1 :: Matriz Int
   ej1 = listArray ((1,1),(5,4)) (concat [[1,0,0,8],
                                          [0,2,0,3],
                                          [0,0,0,5],
                                          [3,5,7,6],
                                          [1,2,3,4]])

ej1 :: Matriz Int

ej1 = listArray ((1,1),(5,4)) (concat [[1,0,0,8],

[0,2,0,3],

[0,0,0,5],

[3,5,7,6],

[1,2,3,4]])

Definir la función

   maximosLocales :: Matriz Int -> [((Int,Int),Int)]

1	maximosLocales :: Matriz Int -> [((Int,Int),Int)]

tal que (maximosLocales p) es la lista de las posiciones en las que hay un máximo local, con el valor correspondiente. Por ejemplo,

   maximosLocales ej1 == [((1,4),8),((2,2),2),((4,3),7)]

1	maximosLocales ej1 == [((1,4),8),((2,2),2),((4,3),7)]

Soluciones

import Data.Array

type Matriz a = Array (Int,Int) a

ej1 :: Matriz Int
ej1 = listArray ((1,1),(5,4)) (concat [[1,0,0,8],
                                       [0,2,0,3],
                                       [0,0,0,5],
                                       [3,5,7,6],
                                       [1,2,3,4]])

maximosLocales :: Matriz Int -> [((Int,Int),Int)]
maximosLocales p = 
    [((i,j),p!(i,j)) | (i,j) <- indices p,
               and [p!(a,b) < p!(i,j) | (a,b) <- vecinos (i,j)]] 
    where (_,(m,n)) = bounds p
          vecinos (i,j) = [(a,b) | a <- [max 1 (i-1)..min m (i+1)],
                                   b <- [max 1 (j-1)..min n (j+1)],
                                   (a,b) /= (i,j)]

import Data.Array

type Matriz a = Array (Int,Int) a

ej1 :: Matriz Int

ej1 = listArray ((1,1),(5,4)) (concat [[1,0,0,8],

[0,2,0,3],

[0,0,0,5],

[3,5,7,6],

[1,2,3,4]])

maximosLocales :: Matriz Int -> [((Int,Int),Int)]

maximosLocales p =

[((i,j),p!(i,j)) | (i,j) <- indices p,

and [p!(a,b) < p!(i,j) | (a,b) <- vecinos (i,j)]]

where (_,(m,n)) = bounds p

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

b <- [max 1 (j-1)..min n (j+1)],

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

Árboles con todas sus ramas con algún elemento que cumple una propiedad

PorJosé A. Alonso 19-marzo-20151-mayo-2015

En lógica temporal, la expresión AFp significa que en algún momento en el futuro se cumple la propiedad p. Trasladado a su interpretación en forma de árbol lo que quiere decir es que en todas las ramas (desde la raíz hasta una hoja) hay un nodo que cumple la propiedad p.

Consideramos el siguiente tipo algebraico de los árboles binarios:

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
                  deriving (Show,Eq)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show,Eq)

y el siguiente árbol

   a1 :: Arbol Int
   a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

1 2	a1 :: Arbol Int a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

En este árbol se cumple (AF par); es decir, en todas las ramas hay un número par; pero no se cumple (AF primo); es decir, hay ramas en las que no hay ningún número primo. Donde una rama es la secuencia de nodos desde el nodo inicial o raíz hasta una hoja.

Definir la función

   propiedadAF :: (a -> Bool) -> Arbol a -> Bool

1	propiedadAF :: (a -> Bool) -> Arbol a -> Bool

tal que (propiedadAF p a) se verifica si se cumple (AF p) en el árbol a; es decir, si en todas las ramas hay un nodo (interno u hoja) que cumple la propiedad p. Por ejemplo

   propiedadAF even a1  ==  True
   propiedadAF (<7) a1  ==  False

1 2	propiedadAF even a1 == True propiedadAF (<7) a1 == False

Soluciones

[schedule expon=’2015-03-26′ expat=»06:00″]

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
             deriving (Show,Eq)

a1 :: Arbol Int
a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

propiedadAF :: (a -> Bool) -> Arbol a -> Bool
propiedadAF p (H a)     = p a
propiedadAF p (N a i d) = p a || (propiedadAF p i && propiedadAF p d)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show,Eq)

a1 :: Arbol Int

a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)

propiedadAF :: (a -> Bool) -> Arbol a -> Bool

propiedadAF p (H a) = p a

propiedadAF p (N a i d) = p a || (propiedadAF p i && propiedadAF p d)

Cociente entero de polinomios

PorJosé A. Alonso 18-marzo-20151-mayo-2015

El cociente entero de un polinomio P(x) por un monomio axⁿ es el polinomio que se obtiene a partir de los términos de P(x) con un grado mayor o igual que n, realizando la división entera entre sus coeficientes y el coeficiente del monomio divisor y restando el valor de n al de sus grados. Por ejemplo,

El cociente entero de 4x⁴ + 6x³ + 7x² + 5x + 2 por el monomio 3x² se obtiene a partir de los términos 4x⁴ + 6x³ + 7x² realizando la división entera entre sus coeficientes y el número 3 y restando 2 a sus grados. De esta forma se obtiene x² + 2x + 2
El cociente entero de 6x⁵ + 2x⁴ + 8x³ + 5x² + 8x + 4 por el monomio 4x³ se obtiene a partir de los términos 6x⁵ + 2x⁴ + 8x³ realizando la división entera entre sus coeficientes y el número 4 y restando 3 a sus grados. De esta forma se obtiene x² + 2

Definir la función

   cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

1	cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

tal que (cocienteEntero p a n) es el cociente entero del polinomio p por el monomio de grado n y coeficiente a. Por ejemplo,

   ghci> let listaApol xs = foldr (\(n,b) -> consPol n b) polCero xs
   ghci> cocienteEntero (listaApol [(4,4),(3,6),(2,7),(1,5),(0,2)]) 3 2
   x^2 + 2*x + 2
   ghci> cocienteEntero (listaApol [(5,6),(4,2),(3,8),(2,5),(1,8),(0,4)]) 4 3
   x^2 + 2

ghci> let listaApol xs = foldr (\(n,b) -> consPol n b) polCero xs

ghci> cocienteEntero (listaApol [(4,4),(3,6),(2,7),(1,5),(0,2)]) 3 2

x^2 + 2*x + 2

ghci> cocienteEntero (listaApol [(5,6),(4,2),(3,8),(2,5),(1,8),(0,4)]) 4 3

x^2 + 2

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.

Soluciones

import I1M.Pol

cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int
cocienteEntero p a n
    | grado p < n = polCero
    | otherwise   = consPol (grado p - n) (coefLider p `div` a)
                            (cocienteEntero (restoPol p) a n)

import I1M.Pol

cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int

cocienteEntero p a n

| grado p < n = polCero

| otherwise = consPol (grado p - n) (coefLider p `div` a)

(cocienteEntero (restoPol p) a n)

Matrices cruzadas

Soluciones

Caminos maximales en árboles binarios

Soluciones

Máximos locales de una matriz

Soluciones

Árboles con todas sus ramas con algún elemento que cumple una propiedad

Soluciones

Cociente entero de polinomios

Soluciones

Entradas recientes

Buscar

Correo electrónico