Ir al contenido principal

Grafo complemenario

Misceláneas

El complementario del grafo G es un grafo G' del mismo tipo que G (dirigido o no dirigido), con el mismo conjunto de nodos y tal que dos nodos de G' son adyacentes si y sólo si no son adyacentes en G. Los pesos de todas las aristas del complementario es igual a 0.

Definir la función

complementario :: Grafo Int Int -> Grafo Int Int

tal que (complementario g) es el complementario de g. Por ejemplo,

λ> complementario (creaGrafo D (1,3) [(1,3,0),(3,2,0),(2,2,0),(2,1,0)])
G D (array (1,3) [(1,[(1,0),(2,0)]),(2,[(3,0)]),(3,[(1,0),(3,0)])])
λ> complementario (creaGrafo D (1,3) [(3,2,0),(2,2,0),(2,1,0)])
G D (array (1,3) [(1,[(1,0),(2,0),(3,0)]),(2,[(3,0)]),(3,[(1,0),(3,0)])])

Nota: Se usa el módulo Grafo de la librería de I1M.

Leer más…

El problema de las celebridades

Misceláneas

La celebridad de una reunión es una persona al que todos conocen pero que no conoce a nadie. Por ejemplo, si en la reunión hay tres personas tales que la 1 conoce a la 3 y la 2 conoce a la 1 y a la 3, entonces la celebridad de la reunión es la 3.

La relación de conocimiento se puede representar mediante una lista de pares (x,y) indicando que x conoce a y. Por ejemplo, ka reunioń anterior se puede representar por [(1,3),(2,1),(2,3)].

Definir la función

celebridad :: Ord a => [(a,a)] -> Maybe a

tal que (celebridad r) es el justo la celebridad de r, si en r hay una celebridad y Nothing, en caso contrario. Por ejemplo,

celebridad [(1,3),(2,1),(2,3)]            ==  Just 3
celebridad [(1,3),(2,1),(3,2)]            ==  Nothing
celebridad [(1,3),(2,1),(2,3),(3,1)]      ==  Nothing
celebridad [(x,1) | x <- [2..10^6]]       ==  Just 1
celebridad [(x,10^6) | x <- [1..10^6-1]]  ==  Just 1000000

Leer más…

Pares a distancia dada

Misceláneas

Definir la función

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

tal que (pares xs k) es la lista de pares de elementos de xs que están a distancia k (se supone que los elementos de xs son distintos). Por ejemplo,

pares [1,5,3,4,2,8] 2       ==  [(1,3),(3,5),(2,4)]
length (pares [1..10^6] 3)  ==  999997

Leer más…

Problema de las 3 jarras

Misceláneas

En el problema de las tres jarras (A,B,C) se dispone de tres jarras de capacidades A, B y C litros con A > B > C y A par. Inicialmente la jarra mayor está llena y las otras dos vacías. Queremos, trasvasando adecuadamente el líquido entre las jarras, repartir por igual el contenido inicial entre las dos jarras mayores. Por ejemplo, para el problema (8,5,3) el contenido inicial es (8,0,0) y el final es (4,4,0).

Definir las funciones

solucionesTresJarras :: Problema -> [[Estado]]
tresJarras :: Problema -> Maybe [Estado]

tales que

  • (solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,
λ> mapM_ print (solucionesTresJarras (4,2,1))
[(4,0,0),(2,2,0)]
[(4,0,0),(3,0,1),(1,2,1),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(1,2,1),(2,2,0)]
λ> mapM_ print (solucionesTresJarras (8,6,2))
[(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(6,0,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(2,6,0),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(2,6,0),(2,4,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(2,6,0),(2,4,2),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
λ> length (solucionesTresJarras (8,5,3))
16
λ> head (solucionesTresJarras (8,5,3))
[(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
λ> length (solucionesTresJarras (8,6,5))
0
  • (tresJarras p) es una solución del problema de las tres jarras p con el mínimo mínimo número de trasvase, si p tiene solución y Nothing, en caso contrario. Por ejemplo,
λ> tresJarras (4,2,1)
Just [(4,0,0),(2,2,0)]
λ> tresJarras (8,6,2)
Just [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
λ> tresJarras (8,5,3)
Just [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
λ> tresJarras (8,6,5)
Nothing

Leer más…

Suma de árboles por niveles

Misceláneas

Los árboles binarios con valores enteros se pueden representar con el de tipo de dato algebraico

data Arbol = H
           | N a Arbol Arbol

Por ejemplo, los árboles

    3                7
   / \              / \
  2   4            5   8
 / \   \          / \   \
1   3   5        6   4   10
                    /   /
                   9   1

se representan por

ej1, ej2 :: Arbol
ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))

Definir la función

suma :: Arbol -> Int

tal que (suma a) es la suma de todos los nodos a una distancia par de la raíz del árbol a menos la suma de todos los nodos a una distancia impar de la raíz. Por ejemplo,

suma ej1  ==  6
suma ej2  ==  4

ya que

(3 + 1+3+5) - (2+4)        = 6
(7 + 6+4+10) - (5+8 + 9+1) = 4

Leer más…

Normalización de expresiones aritméticas

Misceláneas

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

data Expr = Var String
          | S Expr Expr
          | P Expr Expre
          deriving (Eq, Show)

Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z")))

Una expresión es un término si es un producto de variables. Por ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x*(y*z) y x+(y*z) están en forma normal; pero x*(y+z) y (x+y)*(x+z) no lo están.

Definir la función

esTermino :: Expr -> Bool
esTermino :: Expr -> Bool
normal    :: Expr -> Expr

tales que

  • (esTermino a) se verifica si a es un término. Por ejemplo,
esTermino (V "x")                         == True
esTermino (P (V "x") (P (V "y") (V "z"))) == True
esTermino (P (V "x") (S (V "y") (V "z"))) == False
esTermino (S (V "x") (P (V "y") (V "z"))) == False
  • (esNormal a) se verifica si a está en forma normal. Por ejemplo,
esNormal (V "x")                                     == True
esNormal (P (V "x") (P (V "y") (V "z")))             == True
esNormal (S (V "x") (P (V "y") (V "z")))             == True
esNormal (P (V "x") (S (V "y") (V "z")))             == False
esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False
esNormal (S (P (V "x") (V "y")) (S (V "z") (V "x"))) == True
  • (normal e) es la forma normal de la expresión e obtenida aplicando, mientras que sea posible, las propiedades distributivas:
(a+b)*c = a*c+b*c
c*(a+b) = c*a+c*b

Por ejemplo,

λ> normal (P (S (V "x") (V "y")) (V "z"))
S (P (V "x") (V "z")) (P (V "y") (V "z"))
λ> normal (P (V "z") (S (V "x") (V "y")))
S (P (V "z") (V "x")) (P (V "z") (V "y"))
λ> normal (P (S (V "x") (V "y")) (S (V "u") (V "v")))
S (S (P (V "x") (V "u")) (P (V "x") (V "v")))
   (S (P (V "y") (V "u")) (P (V "y") (V "v")))
λ> normal (S (P (V "x") (V "y")) (V "z"))
S (P (V "x") (V "y")) (V "z")
λ> normal (V "x")
V "x"

Comprobar con QuickCheck que para cualquier expresión e, (normal e) está en forma normal y que (normal (normal e)) es igual a (normal e).

Nota. Para la comprobación se usará el siguiente generador de expresiones aritméticas

import Test.QuickCheck
import Control.Monad

instance Arbitrary Expr where
  arbitrary = sized arb
    where
      arb 0         = liftM V arbitrary
      arb n | n > 0 = oneof [liftM V arbitrary,
                             liftM2 S sub sub,
                             liftM2 P sub sub]
        where sub = arb (n `div` 2)

Leer más…

Recorrido en ZigZag

Misceláneas

El recorrido en ZigZag de una matriz consiste en pasar de la primera fila hasta la última, de izquierda a derecha en las filas impares y de derecha a izquierda en las filas pares, como se indica en la figura.

/             \
| 1 -> 2 -> 3 |
|           | |
|           v |
| 4 <- 5 <- 6 |   =>  Recorrido ZigZag: [1,2,3,6,5,4,7,8,9]
| |           |
| v           |
| 7 -> 8 -> 9 |
\             /

Definir la función

recorridoZigZag :: Matrix a -> [a]

tal que (recorridoZigZag m) es la lista con los elementos de la matriz m cuando se recorre esta en ZigZag. Por ejemplo,

λ> recorridoZigZag (fromLists [[1,2,3],[4,5,6],[7,8,9]])
[1,2,3,6,5,4,7,8,9]
λ> recorridoZigZag (fromLists [[1,2],[3,4],[5,6],[7,8]])
[1,2,4,3,5,6,8,7]
λ> recorridoZigZag (fromLists [[1,2,3,4],[5,6,7,8],[9,10,11,12]])
[1,2,3,4,8,7,6,5,9,10,11,12]
λ> recorridoZigZag (fromList 5 4 "Cada paso es la meta")
"Cadasap o es al meta"
λ> recorridoZigZag (fromList 4 5 "Cada paso es la meta")
"Cada  osapes laatem "
λ> recorridoZigZag (fromList 10 2 "Cada paso es la meta")
"Caad psao se l ameat"
λ> recorridoZigZag (fromList 2 10 "Cada paso es la meta")
"Cada paso atem al se"

Leer más…

Sucesión de Recamán

Misceláneas

La sucesión de Recamán está definida como sigue:

a(0) = 0
a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión
a(n) = a(n-1) + n, en caso contrario.

Definir las funciones

sucRecaman :: [Int]
invRecaman :: Int -> Int
graficaSucRecaman :: Int -> IO ()
graficaInvRecaman :: Int -> IO ()

tales que

  • sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,
λ> take 25 sucRecaman3
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]
λ> sucRecaman !! 1000
3686
λ> sucRecaman !! 1000001
1057163
  • (invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,
invRecaman 10       ==  12
invRecaman 3686     ==  1000
invRecaman 1057163  ==  1000001
  • (graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja

Sucesión de Recamán

  • (graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja

Sucesión de Recamán

y (graficaInvRecaman 100) dibuja

Sucesión de Recamán

Leer más…

Operaciones con series de potencias

Misceláneas

Una serie de potencias es una serie de la forma

a₀ + a₁x + a₂x² + a₃x³ + ...

Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es

e^x = 1 + x + x²/2! + x³/3! + ...

y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, ...]

Las operaciones con series se pueden ver como una generalización de las de los polinomios.

En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es

type Serie a = [a]

Definir las siguientes funciones

opuesta      :: Num a => Serie a -> Serie a
suma         :: Num a => Serie a -> Serie a -> Serie a
resta        :: Num a => Serie a -> Serie a -> Serie a
producto     :: Num a => Serie a -> Serie a -> Serie a
cociente     :: Fractional a => Serie a -> Serie a -> Serie a
derivada     :: (Num a, Enum a) => Serie a -> Serie a
integral     :: (Fractional a, Enum a) => Serie a -> Serie a
expx         :: Serie Rational

tales que

  • (opuesta xs) es la opuesta de la serie xs. Por ejemplo,
λ> take 7 (opuesta [-6,-4..])
[6,4,2,0,-2,-4,-6]
  • (suma xs ys) es la suma de las series xs e ys. Por ejemplo,
λ> take 7 (suma [1,3..] [2,4..])
[3,7,11,15,19,23,27]
  • (resta xs ys) es la resta de las series xs es ys. Por ejemplo,
λ> take 7 (resta [3,5..] [2,4..])
[1,1,1,1,1,1,1]
λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
[2,4,6,8,10,12,14]
  • (producto xs ys) es el producto de las series xs e ys. Por ejemplo,
λ> take 7 (producto [3,5..] [2,4..])
[6,22,52,100,170,266,392]
  • (cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,
λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
[2.0,4.0,6.0,8.0,10.0,12.0,14.0]
  • (derivada xs) es la derivada de la serie xs. Por ejemplo,
λ> take 7 (derivada [2,4..])
[4,12,24,40,60,84,112]
  • (integral xs) es la integral de la serie xs. Por ejemplo,
λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
[0.0,4.0,6.0,8.0,10.0,12.0,14.0]
  • expx es la serie de la función exponencial. Por ejemplo,
λ> take 8 expx
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (derivada expx)
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (integral expx)
[0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Leer más…

Operaciones con polinomios como diccionarios

Misceláneas

Los polinomios se pueden representar mediante diccionarios con los exponentes como claves y los coeficientes como valores.

El tipo de los polinomios con coeficientes de tipo a se define por

type Polinomio a = M.Map Int a

Dos ejemplos de polinomios (que usaremos en los ejemplos) son

3 + 7x - 5x^3
4 + 5x^3 + x^5

se definen por

ejPol1, ejPol2 :: Polinomio Int
ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
ejPol2 = M.fromList [(0,4),(3,5),(5,1)]

Definir las funciones

sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a

tales que

  • (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,
λ> sumaPol ejPol1 ejPol2
fromList [(0,7),(1,7),(5,1)]
λ> sumaPol ejPol1 ejPol1
fromList [(0,6),(1,14),(3,-10)]
  • (multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo,
λ> multPorTerm (2,3) (M.fromList [(0,4),(2,1)])
fromList [(2,12),(4,3)]
  • (multPol p q) es el producto de los polinomios p y q. Por ejemplo,
λ> multPol ejPol1 ejPol2
fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
λ> multPol ejPol1 ejPol1
fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
λ> multPol ejPol2 ejPol2
fromList [(0,16),(3,40),(5,8),(6,25),(8,10),(10,1)]

Leer más…