Menu Close

Reconocimiento de camino en un grafo

 

Dado un grafo no dirigido G, un camino en G es una secuencia de nodos [v(1),v(2),v(3),…,v(n)] tal que para todo i entre 1 y n-1, (v(i),v(i+1)) es una arista de G. Por ejemplo, dados los grafos

   g1, g2 :: Grafo Int Int
   g1 = creaGrafo ND (1,3) [(1,2,0),(1,3,0),(2,3,0)]
   g2 = creaGrafo ND (1,4) [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(3,4,0)]

la lista [1,2,3] es un camino en g1, pero no es un camino en g2 puesto que la arista (2,3) no existe en g2.

Definir la función

   camino :: Grafo Int Int -> [Int] -> Bool

tal que (camino g vs) se verifica si la lista de nodos vs es un camino en el grafo g. Por ejemplo,

   camino g1 [1,2,3]  ==  True
   camino g2 [1,2,3]  ==  False

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

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 31 de mayo.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

Dijo el árbol: teme al hacha,
palo clavado en el suelo:
contigo la poda es tala.

Antonio Machado

Diccionario de frecuencias

 

Definir la función

   frecuencias :: Ord a => [a] -> Map a Int

tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,

   λ> frecuencias "sosos"
   fromList [('o',2),('s',3)]
   λ> frecuencias (show (10^100))
   fromList [('0',100),('1',1)]
   λ> frecuencias (take (10^6) (cycle "abc"))
   fromList [('a',333334),('b',333333),('c',333333)]
   λ> size (frecuencias (take (10^6) (cycle [1..10^6])))
   1000000

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 30 de mayo.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

Siempre en alto, siempre en alto.
¿Renovación? Desde arriba.
Dijo la cucaña al árbol.

Antonio Machado

Polinomios de Bell

 

Los polinomios de Bell forman una sucesión de polinomios, definida como sigue:

   B₀(x) = 1 (polinomio unidad)
   Bₙ(x) = x·[Bₙ(x) + Bₙ'(x)]

Por ejemplo,

   B₀(x) = 1                     = 1
   B₁(x) = x·(1+0)               = x     
   B₂(x) = x·(x+1)               = x²+x         
   B₃(x) = x·(x²+x+2x+1)         = x³+3x²+x    
   B₄(x) = x·(x³+3x²+x+3x²+6x+1) = x⁴+6x³+7x²+x

Definir la función

   polBell :: Integer -> Polinomio Integer

tal que (polBell n) es el polinomio de Bell de grado n. Por ejemplo,

   polBell 4                    ==  x^4 + 6*x^3 + 7*x^2 + 1*x
   coeficiente 2 (polBell 4)    ==  7
   coeficiente 2 (polBell 30)   ==  536870911
   coeficiente 1 (polBell 1000) == 1
   length (show (coeficiente 9 (polBell 1000)))  ==  949

Notas: Se usa la librería I1M.PolOperaciones que se encuentra aquí y se describe aquí. Además, en el último ejemplo se usa la función coeficiente tal que (coeficiente k p) es el coeficiente del término de grado k en el polinomio p definida por

   coeficiente :: Num a => Int -> Polinomio a -> a
   coeficiente k p | k == n                 = coefLider p
                   | k > grado (restoPol p) = 0
                   | otherwise              = coeficiente k (restoPol p)
                   where n = grado p

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 29 de mayo.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

El pensamiento barroco
pinta virutas de fuego,
hincha y complica el decoro.

Antonio Machado

Suma de los elementos de las diagonales de las matrices espirales

 

Empezando con el número 1 y moviéndose en el sentido de las agujas del reloj se obtienen las matrices espirales

   |1 2|   |7 8 9|   | 7  8  9 10|   |21 22 23 24 25|
   |4 3|   |6 1 2|   | 6  1  2 11|   |20  7  8  9 10|
           |5 4 3|   | 5  4  3 12|   |19  6  1  2 11|
                     |16 15 14 13|   |18  5  4  3 12|
                                     |17 16 15 14 13|

La suma los elementos de sus diagonales es

   + en la 2x2: 1+3+2+4               =  10
   + en la 3x3: 1+3+5+7+9             =  25
   + en la 4x4: 1+2+3+4+7+10+13+16    =  56
   + en la 5x5: 1+3+5+7+9+13+17+21+25 = 101

Definir la función

   sumaDiagonales :: Integer -> Integer

tal que (sumaDiagonales n) es la suma de los elementos en las diagonales de la matriz espiral de orden nxn. Por ejemplo.

   sumaDiagonales 1         ==  1
   sumaDiagonales 2         ==  10
   sumaDiagonales 3         ==  25
   sumaDiagonales 4         ==  56
   sumaDiagonales 5         ==  101
   sumaDiagonales (10^6)    ==  666667166668000000
   sumaDiagonales (1+10^6)  ==  666669166671000001
 
   sumaDiagonales (10^2)  ==         671800
   sumaDiagonales (10^3)  ==        667168000
   sumaDiagonales (10^4)  ==       666716680000
   sumaDiagonales (10^5)  ==      666671666800000
   sumaDiagonales (10^6)  ==     666667166668000000
   sumaDiagonales (10^7)  ==    666666716666680000000
   sumaDiagonales (10^8)  ==   666666671666666800000000
   sumaDiagonales (10^9)  ==  666666667166666668000000000
 
   length (show (sumaDiagonales (10^(10^4))))  == 30000
   length (show (sumaDiagonales (10^(10^5))))  == 300000
   length (show (sumaDiagonales (10^(10^6))))  == 3000000

Comprobar con QuickCheck que el último dígito de (sumaDiagonales n) es 0, 4 ó 6 si n es par y es 1, 5 ó 7 en caso contrario.

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 28 de mayo.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

Sobre el olivar,
se vio al la lechuza
volar y volar.
Campo, campo, campo.
Entre los olivos,
los cortijos blancos.

Antonio Machado

Descomposiciones con sumandos 1 o 2

 

Definir la funciones

   sumas  :: Int -> [[Int]]
   nSumas :: Int -> Integer

tales que

  • (sumas n) es la lista de las descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,
      sumas 1            ==  [[1]]
      sumas 2            ==  [[1,1],[2]]
      sumas 3            ==  [[1,1,1],[1,2],[2,1]]
      sumas 4            ==  [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]]
      length (sumas 26)  ==  196418
      length (sumas 33)  ==  5702887
  • (nSumas n) es el número de descomposiciones de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,
      nSumas 4                      ==  5
      nSumas 123                    ==  36726740705505779255899443
      length (show (nSumas 123456)) ==  25801

Soluciones

  • Las soluciones se pueden escribir en los comentarios hasta el 27 de mayo.
  • El código se debe escribir entre una línea con <pre lang=”haskell”> y otra con </pre>

Pensamiento

Concepto mondo y lirondo
suele ser cáscara hueca;
puede ser caldera al rojo.

Antonio Machado

Matriz zigzagueante

 

La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n² primeros números naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es

    0  1  5  6 14
    2  4  7 13 15
    3  8 12 16 21
    9 11 17 20 22
   10 18 19 23 24

La colocación de los elementos se puede ver gráficamente en
Matriz zigzagueante

Definir la función

   zigZag :: Int -> Array (Int,Int) Int

tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,

   ghci> elems (zigZag 3)
   [0,1,5, 2,4,6, 3,7,8]
   ghci> elems (zigZag 4)
   [0,1,5,6, 2,4,7,12, 3,8,11,13, 9,10,14,15]
   ghci> elems (zigZag 5)
   [0,1,5,6,14, 2,4,7,13,15, 3,8,12,16,21, 9,11,17,20,22, 10,18,19,23,24]
   ghci> take 15 (elems (zigZag 1000))
   [0,1,5,6,14,15,27,28,44,45,65,66,90,91,119]

Soluciones

Densidades de números abundantes, perfectos y deficientes

 

La n-ésima densidad de un tipo de número es el cociente entre la cantidad de los números entre 1 y n que son del tipo considerado y n. Por ejemplo, la 7-ésima densidad de los múltiplos de 3 es 2/7 ya que entre los 7 primeros números sólo 2 son múltiplos de 3.

Definir las funciones

   densidades :: Int -> (Double,Double,Double)
   graficas   :: Imt -> IO ()

tales que

  • (densidades n) es la terna formada por la n-ésima densidad de los números abundantes (es decir, para los que la suma de sus divisores propios es mayor que el número), de los números perfectos (es decir, para los que la suma de sus divisores propios es mayor que el número) y de los números deficientes[http://bit.ly/1BniQ9h] (es decir, para los que la suma de sus divisores propios es menor que el número). Por ejemplo,
     densidades 100     ==  (0.22,    2.0e-2, 0.76)
     densidades 1000    ==  (0.246,   3.0e-3, 0.751)
     densidades 10000   ==  (0.2488,  4.0e-4, 0.7508)
     densidades 100000  ==  (0.24795, 4.0e-5, 0.75201)
  • (graficas n) dibuja las gráficas de las k-ésimas densidades (para k entre 1 y n) de los números abundantes, de los números perfectos y de los números deficientes. Por ejemplo, (graficas 100) dibuja

    y (graficas 400) dibuja

Soluciones

Las sucesiones de Loomis

 

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

  • f(0) es x
  • f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

  • Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, …
  • Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
  • Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
  • Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, …
  • Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, …

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

  • la generada por 2 converge a 2
  • la generada por 3 converge a 26
  • la generada por 4 converge a 4
  • la generada por 5 converge a 26

Definir las siguientes funciones

   sucLoomis           :: Integer -> [Integer]
   convergencia        :: Integer -> Integer
   graficaConvergencia :: [Integer] -> IO ()

tales que

  • (sucLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,
     λ> take 15 (sucLoomis 1)
     [1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 2)
     [2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 3)
     [3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 4)
     [4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
     λ> take 15 (sucLoomis 5)
     [5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 20)
     [20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
     λ> take 15 (sucLoomis 100)
     [100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
     λ> sucLoomis 1 !! (2*10^5)
     235180736652
  • (convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,
     convergencia  2      ==  2
     convergencia  3      ==  26
     convergencia  4      ==  4
     convergencia 17      ==  38
     convergencia 19      ==  102
     convergencia 43      ==  162
     convergencia 27      ==  202
     convergencia 58      ==  474
     convergencia 63      ==  150056
     convergencia 81      ==  150056
     convergencia 89      ==  150056
     convergencia (10^12) ==  1000101125092
  • (graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja
    Las_sucesiones_de_Loomis_1
    y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja
    Las_sucesiones_de_Loomis_2

Soluciones

Mayor producto de n dígitos consecutivos de un número

 

Definir la función

   mayorProducto :: Int -> Integer -> Integer

tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,

   mayorProducto 2 325                  ==  10
   mayorProducto 5 11111                ==  1
   mayorProducto 5 113111               ==  3
   mayorProducto 5 110111               ==  0
   mayorProducto 5 10151112             ==  10
   mayorProducto 5 101511124            ==  10
   mayorProducto 5 (product [1..1000])  ==  41472

Soluciones

Productos simultáneos de dos y tres números consecutivos

 

Definir la función

   productos :: Integer -> Integer -> [[Integer]]

tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,

   productos 2 6     ==  [[2,3]]
   productos 3 6     ==  [[1,2,3]]
   productos 4 1680  ==  [[5,6,7,8]]
   productos 2 5     ==  []

Comprobar con QuickCheck que si n > 0 y x > 0, entonces

   productos n (product [x..x+n-1]) == [[x..x+n-1]]

Usando productos, definir la función

   productosDe2y3consecutivos :: [Integer]

cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,

   head productosDe2y3consecutivos  ==  6

Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.

Soluciones

import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
productos1 :: Integer -> Integer -> [[Integer]]
productos1 n x =
  [[y..y+n-1] | y <- [1..x]
              , product [y..y+n-1] == x]
 
-- 2ª solución
-- ===========
 
productos2 :: Integer -> Integer -> [[Integer]]
productos2 n x =
  [[z..z+n-1] | z <- [1..y]
              , product [z..z+n-1] == x]
  where y = head (filter (\y -> y^n >= x) [2..])
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> let (n,x) = (3,200) in productos1 n (product [x..x+n-1])
--    [[200,201,202]]
--    (7.38 secs, 7,235,956,440 bytes)
--    λ> let (n,x) = (3,200) in productos2 n (product [x..x+n-1])
--    [[200,201,202]]
--    (0.01 secs, 451,928 bytes)
--
--    λ> productos2 3 1000018000107000210
--    [[1000005,1000006,1000007]]
--    (1.57 secs, 1,560,159,144 bytes)
 
-- En lo que sigue se usa la 2ª definición
productos :: Integer -> Integer -> [[Integer]]
productos = productos2
 
-- La propiedad es
prop_productos :: Integer -> Integer -> Property
prop_productos n x =
  n > 0 && x > 0 ==> productos n (product [x..x+n-1]) == [[x..x+n-1]]
 
-- La comprobación es
--    λ> quickCheck prop_productos
--    +++ OK, passed 100 tests.
 
productosDe2y3consecutivos :: [Integer]
productosDe2y3consecutivos =
  [x | x <- [1..]
     , let ys = productos 2 x
     , not (null ys)
     , let zs = productos 3 x
     , not (null zs)] 
 
-- El cálculo es
--    λ> take 2 productosDe2y3consecutivos
--    [6,210]

Pensamiento

Mis ojos en el espejo
son ojos ciegos que miran
los ojos con que los veo.

Antonio Machado