junio 2017 – Exercitium

Ancestro común más bajo

PorJosé A. Alonso 9-junio-201725-abril-2021

El tipo de los árboles binarios se define por

   data Arbol = H Int
              | N Int Arbol Arbol

1 2	data Arbol = H Int \| N Int Arbol Arbol

Por ejemplo, el árbol

        5
       / \
      /   \
     3     7
    / \   / \
   1   4 6   9

/ \

3 7

/ \ / \

1 4 6 9

se define por

   ejArbol :: Arbol
   ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

1 2	ejArbol :: Arbol ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

Un árbol ordenado es un árbol binario tal que para cada nodo, los elementos de su subárbol izquierdo son menores y los de su subárbol derecho son mayores. El árbol anterior es un árbol ordenado.

Los ancestros de un nodo x son los nodos y tales que x está en alguna de las ramas de x. Por ejemplo, en el árbol anterior los ancestros de 9 son 5 y 7.

El ancestro común más bajo de dos elementos x e y de un árbol a es el ancestro de x e y de menor profundidad. Por ejemplo, en el árbol anterior el ancestro común más bajo de 6 y 9 es 7.

Definir la función

   ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

1	ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

tal que (ancestroComunMasBajo a x y) es el ancestro de menor profundidad de los nodos x e y en el árbol ordenado a, donde x e y son dos elementos distintos del árbol a. Por ejemplo,

   ancestroComunMasBajo ejArbol 4 1  ==  3
   ancestroComunMasBajo ejArbol 1 6  ==  5
   ancestroComunMasBajo ejArbol 6 9  ==  7

ancestroComunMasBajo ejArbol 4 1 == 3

ancestroComunMasBajo ejArbol 1 6 == 5

ancestroComunMasBajo ejArbol 6 9 == 7

Soluciones

[schedule expon=’2017-06-16′ expat=»06:00″]

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

[/schedule]

[schedule on=’2017-06-16′ at=»06:00″]

data Arbol = H Int
           | N Int Arbol Arbol

ejArbol :: Arbol
ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

-- 1ª definición
-- =============

ancestroComunMasBajo1 :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo1 a x y =
  head [u | u <- xs, u `elem` ys]
  where xs = ancestros a x
        ys = ancestros a y

-- (ancestros a x) es la lista de los ancestros de x en el árbol
-- ordenado a, ordenada por profundidad. Por ejemplo,
--    ancestros ejArbol 1 ==  [3,5]
--    ancestros ejArbol 3 ==  [5]
--    ancestros ejArbol 5 ==  []
--    ancestros ejArbol 9 ==  [7,5]
ancestros :: Arbol -> Int -> [Int]
ancestros a y = aux a y []
  where aux (H _)     _ zs = zs
        aux (N x i d) y zs 
          | x == y    = zs
          | y < x     = aux i y (x:zs)
          | otherwise = aux d y (x:zs)

-- 2ª definición
-- =============

ancestroComunMasBajo2 :: Arbol -> Int -> Int -> Int
ancestroComunMasBajo2 (N z i d) x y 
  | x < z && y < z = ancestroComunMasBajo2 i x y 
  | x > z && y > z = ancestroComunMasBajo2 d x y 
  | otherwise      = z

data Arbol = H Int

| N Int Arbol Arbol

ejArbol :: Arbol

ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

-- 1ª definición

-- =============

ancestroComunMasBajo1 :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo1 a x y =

head [u | u <- xs, u `elem` ys]

where xs = ancestros a x

ys = ancestros a y

-- (ancestros a x) es la lista de los ancestros de x en el árbol

-- ordenado a, ordenada por profundidad. Por ejemplo,

-- ancestros ejArbol 1 == [3,5]

-- ancestros ejArbol 3 == [5]

-- ancestros ejArbol 5 == []

-- ancestros ejArbol 9 == [7,5]

ancestros :: Arbol -> Int -> [Int]

ancestros a y = aux a y []

where aux (H _) _ zs = zs

aux (N x i d) y zs

| x == y = zs

| y < x = aux i y (x:zs)

| otherwise = aux d y (x:zs)

-- 2ª definición

-- =============

ancestroComunMasBajo2 :: Arbol -> Int -> Int -> Int

ancestroComunMasBajo2 (N z i d) x y

| x < z && y < z = ancestroComunMasBajo2 i x y

| x > z && y > z = ancestroComunMasBajo2 d x y

| otherwise = z

[/schedule]

La regla de los signos de Descartes

PorJosé A. Alonso 8-junio-201725-abril-2021

Los polinomios pueden representarse mediante listas. Por ejemplo, el polinomio x^5+3x^4-5x^2+x-7 se representa por [1,3,0,-5,1,-7]. En dicha lista, obviando el cero, se producen tres cambios de signo: del 3 al -5, del -5 al 1 y del 1 al -7. Llamando C(p) al número de cambios de signo en la lista de coeficientes del polinomio p(x), tendríamos entonces que en este caso C(p)=3.

La regla de los signos de Descartes dice que el número de raíces reales positivas de una ecuación polinómica con coeficientes reales igualada a cero es, como mucho, igual al número de cambios de signo que se produzcan entre sus coeficientes (obviando los ceros). Por ejemplo, en el caso anterior la ecuación tendría como mucho tres soluciones reales positivas, ya que C(p)=3.

Además, si la cota C(p) no se alcanza, entonces el número de raíces positivas de la ecuación difiere de ella un múltiplo de dos. En el ejemplo anterior esto significa que la ecuación puede tener tres raíces positivas o tener solamente una, pero no podría ocurrir que tuviera dos o que no tuviera ninguna.

Definir las funciones

   cambios :: [Int] -> [(Int,Int)]
   nRaicesPositivas :: [Int] -> [Int]

1 2	cambios :: [Int] -> [(Int,Int)] nRaicesPositivas :: [Int] -> [Int]

tales que

(cambios xs) es la lista de los pares de elementos de xs con signos distintos, obviando los ceros. Por ejemplo,

     cambios [1,3,0,-5,1,-7]  ==  [(3,-5),(-5,1),(1,-7)]

1	cambios [1,3,0,-5,1,-7] == [(3,-5),(-5,1),(1,-7)]

(nRaicesPositivas p) es la lista de los posibles números de raíces positivas del polinomio p (representado mediante una lista) según la regla de los signos de Descartes. Por ejemplo,

     nRaicesPositivas [1,3,0,-5,1,-7]  ==  [3,1]

1	nRaicesPositivas [1,3,0,-5,1,-7] == [3,1]

que significa que la ecuación x^5+3x^4-5x^2+x-7=0 puede tener 3 ó 1 raíz positiva.

Soluciones

[schedule expon=’2017-06-15′ expat=»06:00″]

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

[/schedule]

[schedule on=’2017-06-15′ at=»06:00″]

-- 1ª definición (por comprensión)
-- ===============================

cambios1 :: [Int] -> [(Int,Int)]
cambios1 xs = [(x,y) | (x,y) <- consecutivos (noCeros xs), x*y < 0]
  where consecutivos xs = zip xs (tail xs)

-- (noCeros xs) es la lista de los elementos de xs distintos de cero. 
-- Por ejemplo,  
--    noCeros [1,3,0,-5,1,-7]  ==  [1,3,-5,1,-7]
noCeros :: [Int] -> [Int]
noCeros = filter (/=0)

-- 2ª definición (por recursión)
-- =============================

cambios2 :: [Int] -> [(Int,Int)]
cambios2 xs = cambios2' (noCeros xs)
  where cambios2' (x:y:xs)
          | x*y < 0   = (x,y) : cambios2' (y:xs)
          | otherwise = cambios2' (y:xs)
        cambios2' _ = []

nRaicesPositivas :: [Int] -> [Int]
nRaicesPositivas xs = [n,n-2..0]
  where n = length (cambios1 xs)

-- 1ª definición (por comprensión)

-- ===============================

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

cambios1 xs = [(x,y) | (x,y) <- consecutivos (noCeros xs), x*y < 0]

where consecutivos xs = zip xs (tail xs)

-- (noCeros xs) es la lista de los elementos de xs distintos de cero.

-- Por ejemplo,

-- noCeros [1,3,0,-5,1,-7] == [1,3,-5,1,-7]

noCeros :: [Int] -> [Int]

noCeros = filter (/=0)

-- 2ª definición (por recursión)

-- =============================

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

cambios2 xs = cambios2' (noCeros xs)

where cambios2' (x:y:xs)

| x*y < 0 = (x,y) : cambios2' (y:xs)

| otherwise = cambios2' (y:xs)

cambios2' _ = []

nRaicesPositivas :: [Int] -> [Int]

nRaicesPositivas xs = [n,n-2..0]

where n = length (cambios1 xs)

[/schedule]

Valores de polinomios y de expresiones

PorJosé A. Alonso 7-junio-201725-abril-2021

Las expresiones aritméticas construidas con una variables, los números enteros y las operaciones de sumar y multiplicar se pueden representar mediante el tipo de datos Exp definido por

   data Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp
              deriving Show

1 2	data Exp = Var \| Const Int \| Sum Exp Exp \| Mul Exp Exp deriving Show

Por ejemplo, la expresión 3+5x^2 se puede representar por

   exp1 :: Exp
   exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

1 2	exp1 :: Exp exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

Por su parte, los polinomios se pueden representar por la lista de sus coeficientes. Por ejemplo, el polinomio 3+5x^2 se puede representar por [3,0,5].

Definir las funciones

   valorE :: Exp -> Int -> Int
   expresion :: [Int] -> Exp
   valorP :: [Int] -> Int -> Int

valorE :: Exp -> Int -> Int

expresion :: [Int] -> Exp

valorP :: [Int] -> Int -> Int

tales que

(valorE e n) es el valor de la expresión e cuando se sustituye su variable por n. Por ejemplo,

     λ> valorE (Sum (Const 3) (Mul Var (Mul Var (Const 5)))) 2
     23

1 2	λ> valorE (Sum (Const 3) (Mul Var (Mul Var (Const 5)))) 2 23

(expresion p) es una expresión aritmética equivalente al polinomio p. Por ejemplo,

     λ> expresion [3,0,5]
     Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5))))

1 2	λ> expresion [3,0,5] Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5))))

(valorP p n) es el valor del polinomio p cuando se sustituye su variable por n. Por ejemplo,

     λ> valorP [3,0,5] 2
     23

1 2	λ> valorP [3,0,5] 2 23

Comprobar con QuickCheck que, para todo polinomio p y todo entero n,

   valorP p n == valorE (expresion p) n

1	valorP p n == valorE (expresion p) n

Soluciones

[schedule expon=’2017-06-14′ expat=»06:00″]

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

[/schedule]

[schedule on=’2017-06-14′ at=»06:00″]

import Test.QuickCheck

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp
           deriving Show
 
exp1 :: Exp
exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))
 
valorE :: Exp -> Int -> Int
valorE Var         n = n
valorE (Const a)   n = a
valorE (Sum e1 e2) n = valorE e1 n + valorE e2 n
valorE (Mul e1 e2) n = valorE e1 n * valorE e2 n
 
expresion :: [Int] -> Exp
expresion [a]   = Const a
expresion (a:p) = Sum (Const a) (Mul Var (expresion p))
 
valorP :: [Int] -> Int -> Int
valorP [a] _ = a
valorP (a:p) n = a + n * valorP p n
 
-- La propiedad es
prop_valor :: [Int] -> Int -> Property
prop_valor p n =
    not (null p) ==> 
    valorP p n == valorE (expresion p) n
 
-- La comprobación es
--    λ> quickCheck prop_valor
--    +++ OK, passed 100 tests.

import Test.QuickCheck

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp Exp

deriving Show

exp1 :: Exp

exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

valorE :: Exp -> Int -> Int

valorE Var n = n

valorE (Const a) n = a

valorE (Sum e1 e2) n = valorE e1 n + valorE e2 n

valorE (Mul e1 e2) n = valorE e1 n * valorE e2 n

expresion :: [Int] -> Exp

expresion [a] = Const a

expresion (a:p) = Sum (Const a) (Mul Var (expresion p))

valorP :: [Int] -> Int -> Int

valorP [a] _ = a

valorP (a:p) n = a + n * valorP p n

-- La propiedad es

prop_valor :: [Int] -> Int -> Property

prop_valor p n =

not (null p) ==>

valorP p n == valorE (expresion p) n

-- La comprobación es

-- λ> quickCheck prop_valor

-- +++ OK, passed 100 tests.

[/schedule]

Problema de Ullman

PorJosé A. Alonso 6-junio-20175-junio-2017

Definir la función

   ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool

1	ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool

tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k elementos cuya suma sea menor que t. Por ejemplo,

   ullman  9 3 [1..10]    ==  True
   ullman  5 3 [1..10]    ==  False
   ullman  9 5 [1..10^6]  ==  False
   ullman 29 5 [1..10^6]  ==  True

ullman 9 3 [1..10] == True

ullman 5 3 [1..10] == False

ullman 9 5 [1..10^6] == False

ullman 29 5 [1..10^6] == True

Soluciones

[schedule expon=’2017-06-13′ expat=»06:00″]

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

[/schedule]

[schedule on=’2017-06-13′ at=»06:00″]

import Data.List (sort, subsequences)

-- 1ª solución
ullman1 :: (Num a, Ord a) => a -> Int -> [a] -> Bool
ullman1 t k xs = 
  (not . null) [ys | ys <- subsequences xs, length ys == k, sum ys < t]

-- 2ª solución
ullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool
ullman2 t k xs = sum (take k (sort xs)) < t

-- Comparación de eficiencia
--    λ> ullman1 9 5 [1..23]
--    False
--    (10.73 secs, 1,761,726,376 bytes)
--    λ> ullman2 9 5 [1..23]
--    False
--    (0.01 secs, 0 bytes)

import Data.List (sort, subsequences)

-- 1ª solución

ullman1 :: (Num a, Ord a) => a -> Int -> [a] -> Bool

ullman1 t k xs =

(not . null) [ys | ys <- subsequences xs, length ys == k, sum ys < t]

-- 2ª solución

ullman2 :: (Ord a, Num a) => a -> Int -> [a] -> Bool

ullman2 t k xs = sum (take k (sort xs)) < t

-- Comparación de eficiencia

-- λ> ullman1 9 5 [1..23]

-- False

-- (10.73 secs, 1,761,726,376 bytes)

-- λ> ullman2 9 5 [1..23]

-- False

-- (0.01 secs, 0 bytes)

[/schedule]

Subsucesiones cuya suma de sus cuadrados es divisible por la longitud de la sucesión

PorJosé A. Alonso 5-junio-20175-junio-2017

El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1966 es

Sea a(1),…,a(n) (n ≥ 2) una sucesión de enteros. Demostrar que existe una subsucesión 1 ≤ k(1) < k(2) < ··· < k(m) ≤ n, tal que a(k(1))^2 + ... + a(k(m))^2 es divisible por n.

Definir la función

   subsucesionesE :: [Int] -> [[Int]]

1	subsucesionesE :: [Int] -> [[Int]]

tal que (subsucesionesE xs) es la lista de las subsucesiones de xs tales que la suma de sus cuadrados es divisible por la longitud de xs. Por ejemplo,

   subsucesionesE [3,2,9]     ==  [[3],[9],[3,9]]
   subsucesionesE [3,2,1]     ==  [[3]]
   subsucesionesE [5,2,1]     ==  [[5,2,1]]
   subsucesionesE [3,9,6,4,1] ==  [[3,9],[3,6],[3,4],[3,1]]
   subsucesionesE [1,9,6,4,3] ==  [[1,3],[9,3],[6,3],[4,3]]

subsucesionesE [3,2,9] == [[3],[9],[3,9]]

subsucesionesE [3,2,1] == [[3]]

subsucesionesE [5,2,1] == [[5,2,1]]

subsucesionesE [3,9,6,4,1] == [[3,9],[3,6],[3,4],[3,1]]

subsucesionesE [1,9,6,4,3] == [[1,3],[9,3],[6,3],[4,3]]

Comprobar con QuickCheck que toda lista no vacía xs tiene alguna subsucesión ys tal que la suma de los cuadrados de los elementos de ys es divisible por la longitud de xs.

Soluciones

[schedule expon=’2017-06-12′ expat=»06:00″]

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

[/schedule]

[schedule on=’2017-06-12′ at=»06:00″]

import Data.List (subsequences)
import Test.QuickCheck

subsucesionesE :: [Int] -> [[Int]]
subsucesionesE xs = [ys | ys <- tail (subsequences xs),
                          sum [y^2 | y <- ys] `rem` length xs == 0]

-- La propiedad es
prop_subsucesionesE :: [Int] -> Property
prop_subsucesionesE xs =
  not (null xs) ==> not (null (subsucesionesE xs))

-- La comprobación es
--    λ> quickCheck prop_subsucesionesE
--    +++ OK, passed 100 tests.

import Data.List (subsequences)

import Test.QuickCheck

subsucesionesE :: [Int] -> [[Int]]

subsucesionesE xs = [ys | ys <- tail (subsequences xs),

sum [y^2 | y <- ys] `rem` length xs == 0]

-- La propiedad es

prop_subsucesionesE :: [Int] -> Property

prop_subsucesionesE xs =

not (null xs) ==> not (null (subsucesionesE xs))

-- La comprobación es

-- λ> quickCheck prop_subsucesionesE

-- +++ OK, passed 100 tests.

[/schedule]

Suma de los cuadrados de los divisores

PorJosé A. Alonso 2-junio-20171-junio-2017

Dado un entero positivo n, consideremos la suma de los cuadrados de sus divisores. Por ejemplo,

   f(10) = 1 + 4 + 25 + 100 = 130
   f(42) = 1 + 4 +  9 +  36 + 49 + 196 + 441 + 1764 = 2500

1 2	f(10) = 1 + 4 + 25 + 100 = 130 f(42) = 1 + 4 + 9 + 36 + 49 + 196 + 441 + 1764 = 2500

Decimos que n es especial si f(n) es un cuadrado perfecto. En los ejemplos anteriores, 42 es especial y 10 no lo es.

Definir la función

   especial:: Int -> Bool

1	especial:: Int -> Bool

tal que (especial x) se verifica si x es un número es especial. Por ejemplo,

   especial 42  ==  True
   especial 10  ==  False

1 2	especial 42 == True especial 10 == False

Calcular todos los números especiales de tres cifras.

Nota: El ejercicio está basado en el Problema 211 del proyecto Euler.

Soluciones

[schedule expon=’2017-06-09′ expat=»06:00″]

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

[/schedule]

[schedule on=’2017-06-09′ at=»06:00″]

especial :: Int -> Bool
especial n = esCuadrado (sum (map (^2) (divisores n)))

-- (esCuadrado n) se verifica si n es un cuadrado perfecto. Por ejemplo, 
--    esCuadrado 36  ==  True
--    esCuadrado 40  ==  False
esCuadrado :: Int -> Bool
esCuadrado n = y^2 == n
  where y = floor (sqrt (fromIntegral n))

-- (divisores n) es la lista de los divisores de n. Por ejemplo,
--    divisores 36  ==  [1,2,3,4,6,9,12,18,36]
divisores :: Int -> [Int]        
divisores n = [x | x <- [1..n], rem n x == 0]

especial :: Int -> Bool

especial n = esCuadrado (sum (map (^2) (divisores n)))

-- (esCuadrado n) se verifica si n es un cuadrado perfecto. Por ejemplo,

-- esCuadrado 36 == True

-- esCuadrado 40 == False

esCuadrado :: Int -> Bool

esCuadrado n = y^2 == n

where y = floor (sqrt (fromIntegral n))

-- (divisores n) es la lista de los divisores de n. Por ejemplo,

-- divisores 36 == [1,2,3,4,6,9,12,18,36]

divisores :: Int -> [Int]

divisores n = [x | x <- [1..n], rem n x == 0]

[/schedule]

Mayores sublistas crecientes

PorJosé A. Alonso 1-junio-201730-mayo-2017

Definir las funciones

   mayoresCrecientes :: Ord a => [a] -> [[a]]
   longitudMayorSublistaCreciente :: Ord a => [a] -> Int

1 2	mayoresCrecientes :: Ord a => [a] -> [[a]] longitudMayorSublistaCreciente :: Ord a => [a] -> Int

tales que

(mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo,

     λ> mayoresCrecientes [3,2,6,4,5,1]
     [[3,4,5],[2,4,5]]
     λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]
     [[10,22,33,50,60,80],[10,22,33,41,60,80]]
     λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
     [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]
     λ> length (head (mayoresCrecientes (show (2^70))))
     5

λ> mayoresCrecientes [3,2,6,4,5,1]

[[3,4,5],[2,4,5]]

λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]

[[10,22,33,50,60,80],[10,22,33,41,60,80]]

λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]

[[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]

λ> length (head (mayoresCrecientes (show (2^70))))

(longitudMayorSublistaCreciente xs) es el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

     λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
     3
     λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
     6
     λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
     6
     λ> longitudMayorSublistaCreciente [1..2000]
     2000
     λ> longitudMayorSublistaCreciente [2000,1999..1]
     1

λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]

λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]

λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]

λ> longitudMayorSublistaCreciente [1..2000]

2000

λ> longitudMayorSublistaCreciente [2000,1999..1]

Soluciones

[schedule expon=’2017-06-08′ expat=»06:00″]

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

[/schedule]

[schedule on=’2017-06-08′ at=»06:00″]

import Data.List (nub, sort, subsequences)
import Data.Array

-- 1ª definición de mayoresCrecientes
-- ==================================

mayoresCrecientes1 :: Ord a => [a] -> [[a]]
mayoresCrecientes1 xs =
  [ys | ys <- xss
      , length ys == m]
  where xss = sublistasCrecientes xs
        m   = maximum (map length xss)

-- (sublistasCrecientes1 xs) es la lista de las sublistas crecientes de
-- xs. Por ejemplo,
--    λ> sublistasCrecientes [3,2,5]
--    [[],[3],[2],[5],[3,5],[2,5]]
sublistasCrecientes :: Ord a => [a] -> [[a]]
sublistasCrecientes xs =
  [ys | ys <- subsequences xs
      , esCreciente ys]

-- (esCreciente xs) se verifica si la lista xs es creciente. Por
-- ejemplo,  
--    esCreciente [2,3,5]  ==  True
--    esCreciente [2,3,1]  ==  False
--    esCreciente [2,3,3]  ==  False
esCreciente :: Ord a => [a] -> Bool
esCreciente (x:y:zs) = x < y && esCreciente (y:zs)
esCreciente _        = True

-- 2ª definición de mayoresCrecientes
-- ==================================

mayoresCrecientes2 :: Ord a => [a] -> [[a]]
mayoresCrecientes2 xs =
  [ys | ys <- xss
      , length ys == m]
  where xss = sublistasCrecientes2 xs
        m   = maximum (map length xss)

-- (sublistasCrecientes2 xs) es la lista de las sublistas crecientes de
-- xs. Por ejemplo,
--    λ> sublistasCrecientes2 [3,2,5]
--    [[3,5],[3],[2,5],[2],[5],[]]
sublistasCrecientes2 :: Ord a => [a] -> [[a]]
sublistasCrecientes2 []  = [[]]
sublistasCrecientes2 (x:xs) =
  [x:ys | ys <- yss, null ys || x < head ys] ++ yss
  where yss = sublistasCrecientes2 xs

-- Comparación de eficiencia
-- =========================

--    λ> length (head (mayoresCrecientes1 (show (2^70))))
--    5
--    (10.93 secs, 1,958,822,896 bytes)
--    λ> length (head (mayoresCrecientes2 (show (2^70))))
--    5
--    (0.02 secs, 0 bytes)

-- 1ª definición de longitudMayorSublistaCreciente
-- ===============================================

longitudMayorSublistaCreciente1 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente1 =
  length . head . mayoresCrecientes1

-- 2ª definición de longitudMayorSublistaCreciente
-- ===============================================

longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente2 =
  length . head . mayoresCrecientes2

-- Comparación de eficiencia:
--    λ> longitudMayorSublistaCreciente1 (show (2^70))
--    5
--    (10.78 secs, 1,969,452,328 bytes)
--    λ> longitudMayorSublistaCreciente2 (show (2^70))
--    5
--    (0.02 secs, 0 bytes)

-- 3ª definición de longitudMayorSublistaCreciente
-- ===============================================

longitudMayorSublistaCreciente3 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente3 xs =
  longitudSCM xs (sort (nub xs))
  
-- (longitudSCM xs ys) es la longitud de la subsecuencia máxima de xs e
-- ys. Por ejemplo, 
--   longitudSCM "amapola" "matamoscas" == 4
--   longitudSCM "atamos" "matamoscas"  == 6
--   longitudSCM "aaa" "bbbb"           == 0
longitudSCM :: Eq a => [a] -> [a] -> Int
longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)
  where n = length xs
        m = length ys

-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n
-- y m son los números de elementos de xs e ys, respectivamente) tal que
-- el valor en la posición (i,j) es la longitud de la SCM de los i
-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,
--    λ> elems (matrizLongitudSCM "amapola" "matamoscas")
--    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,
--     0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,
--     0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]
-- Gráficamente,
--       m a t a m o s c a s
--    [0,0,0,0,0,0,0,0,0,0,0,
-- a   0,0,1,1,1,1,1,1,1,1,1,
-- m   0,1,1,1,1,2,2,2,2,2,2,
-- a   0,1,2,2,2,2,2,2,2,3,3,
-- p   0,1,2,2,2,2,2,2,2,3,3,
-- o   0,1,2,2,2,2,3,3,3,3,3,
-- l   0,1,2,2,2,2,3,3,3,3,3,
-- a   0,1,2,2,3,3,3,3,3,4,4]
matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int
matrizLongitudSCM xs ys = q
  where
    n = length xs
    m = length ys
    v = listArray (1,n) xs
    w = listArray (1,m) ys
    q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]
      where f 0 _ = 0
            f _ 0 = 0
            f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)
                  | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))
  
-- Comparación de eficiencia
-- -------------------------

--    λ> longitudMayorSublistaCreciente2 [1..22]
--    22
--    (19.63 secs, 2,271,936,784 bytes)
--    λ> longitudMayorSublistaCreciente3 [1..22]
--    22
--    (0.01 secs, 0 bytes)

-- 4ª definición de longitudMayorSublistaCreciente
-- ===============================================

longitudMayorSublistaCreciente4 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente4 xs =
  maximum (elems (vectorlongitudMayorSublistaCreciente xs))

-- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n
-- tal que el valor i-ésimo es la longitud de la sucesión más largar que
-- termina en el elemento i-ésimo de xs. Por ejemplo, 
--    λ> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1]
--    array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)]
vectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int
vectorlongitudMayorSublistaCreciente xs = v
  where v = array (1,n) [(i,f i) | i <- [1..n]]
        n = length xs
        w = listArray (1,n) xs
        f 1 = 1
        f i | null ls   = 1
            | otherwise = 1 + maximum ls
          where ls = [v ! j | j <- [1..i-1], w ! j < w ! i]

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

import Data.List (nub, sort, subsequences)

import Data.Array

-- 1ª definición de mayoresCrecientes

-- ==================================

mayoresCrecientes1 :: Ord a => [a] -> [[a]]

mayoresCrecientes1 xs =

[ys | ys <- xss

, length ys == m]

where xss = sublistasCrecientes xs

m = maximum (map length xss)

-- (sublistasCrecientes1 xs) es la lista de las sublistas crecientes de

-- xs. Por ejemplo,

-- λ> sublistasCrecientes [3,2,5]

-- [[],[3],[2],[5],[3,5],[2,5]]

sublistasCrecientes :: Ord a => [a] -> [[a]]

sublistasCrecientes xs =

[ys | ys <- subsequences xs

, esCreciente ys]

-- (esCreciente xs) se verifica si la lista xs es creciente. Por

-- ejemplo,

-- esCreciente [2,3,5] == True

-- esCreciente [2,3,1] == False

-- esCreciente [2,3,3] == False

esCreciente :: Ord a => [a] -> Bool

esCreciente (x:y:zs) = x < y && esCreciente (y:zs)

esCreciente _ = True

-- 2ª definición de mayoresCrecientes

-- ==================================

mayoresCrecientes2 :: Ord a => [a] -> [[a]]

mayoresCrecientes2 xs =

[ys | ys <- xss

, length ys == m]

where xss = sublistasCrecientes2 xs

m = maximum (map length xss)

-- (sublistasCrecientes2 xs) es la lista de las sublistas crecientes de

-- xs. Por ejemplo,

-- λ> sublistasCrecientes2 [3,2,5]

-- [[3,5],[3],[2,5],[2],[5],[]]

sublistasCrecientes2 :: Ord a => [a] -> [[a]]

sublistasCrecientes2 [] = [[]]

sublistasCrecientes2 (x:xs) =

[x:ys | ys <- yss, null ys || x < head ys] ++ yss

where yss = sublistasCrecientes2 xs

-- Comparación de eficiencia

-- =========================

-- λ> length (head (mayoresCrecientes1 (show (2^70))))

-- 5

-- (10.93 secs, 1,958,822,896 bytes)

-- λ> length (head (mayoresCrecientes2 (show (2^70))))

-- 5

-- (0.02 secs, 0 bytes)

-- 1ª definición de longitudMayorSublistaCreciente

-- ===============================================

longitudMayorSublistaCreciente1 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente1 =

length . head . mayoresCrecientes1

-- 2ª definición de longitudMayorSublistaCreciente

-- ===============================================

longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente2 =

length . head . mayoresCrecientes2

-- Comparación de eficiencia:

-- λ> longitudMayorSublistaCreciente1 (show (2^70))

-- 5

-- (10.78 secs, 1,969,452,328 bytes)

-- λ> longitudMayorSublistaCreciente2 (show (2^70))

-- 5

-- (0.02 secs, 0 bytes)

-- 3ª definición de longitudMayorSublistaCreciente

-- ===============================================

longitudMayorSublistaCreciente3 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente3 xs =

longitudSCM xs (sort (nub xs))

-- (longitudSCM xs ys) es la longitud de la subsecuencia máxima de xs e

-- ys. Por ejemplo,

-- longitudSCM "amapola" "matamoscas" == 4

-- longitudSCM "atamos" "matamoscas" == 6

-- longitudSCM "aaa" "bbbb" == 0

longitudSCM :: Eq a => [a] -> [a] -> Int

longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)

where n = length xs

m = length ys

-- (matrizLongitudSCM2 xs ys) es la matriz de orden (n+1)x(m+1) (donde n

-- y m son los números de elementos de xs e ys, respectivamente) tal que

-- el valor en la posición (i,j) es la longitud de la SCM de los i

-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,

-- λ> elems (matrizLongitudSCM "amapola" "matamoscas")

-- [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,

-- 0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,

-- 0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]

-- Gráficamente,

-- m a t a m o s c a s

-- [0,0,0,0,0,0,0,0,0,0,0,

-- a 0,0,1,1,1,1,1,1,1,1,1,

-- m 0,1,1,1,1,2,2,2,2,2,2,

-- a 0,1,2,2,2,2,2,2,2,3,3,

-- p 0,1,2,2,2,2,2,2,2,3,3,

-- o 0,1,2,2,2,2,3,3,3,3,3,

-- l 0,1,2,2,2,2,3,3,3,3,3,

-- a 0,1,2,2,3,3,3,3,3,4,4]

matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int

matrizLongitudSCM xs ys = q

where

n = length xs

m = length ys

v = listArray (1,n) xs

w = listArray (1,m) ys

q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]

where f 0 _ = 0

f _ 0 = 0

f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)

| otherwise = max (q ! (i-1,j)) (q ! (i,j-1))

-- Comparación de eficiencia

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

-- λ> longitudMayorSublistaCreciente2 [1..22]

-- 22

-- (19.63 secs, 2,271,936,784 bytes)

-- λ> longitudMayorSublistaCreciente3 [1..22]

-- 22

-- (0.01 secs, 0 bytes)

-- 4ª definición de longitudMayorSublistaCreciente

-- ===============================================

longitudMayorSublistaCreciente4 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente4 xs =

maximum (elems (vectorlongitudMayorSublistaCreciente xs))

-- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n

-- tal que el valor i-ésimo es la longitud de la sucesión más largar que

-- termina en el elemento i-ésimo de xs. Por ejemplo,

-- λ> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1]

-- array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)]

vectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int

vectorlongitudMayorSublistaCreciente xs = v

where v = array (1,n) [(i,f i) | i <- [1..n]]

n = length xs

w = listArray (1,n) xs

f 1 = 1

f i | null ls = 1

| otherwise = 1 + maximum ls

where ls = [v ! j | j <- [1..i-1], w ! j < w ! i]

[/schedule]

Meses: junio 2017

Ancestro común más bajo

Soluciones

La regla de los signos de Descartes

Soluciones

Valores de polinomios y de expresiones

Soluciones

Problema de Ullman

Soluciones

Subsucesiones cuya suma de sus cuadrados es divisible por la longitud de la sucesión

Soluciones

Suma de los cuadrados de los divisores

Soluciones

Mayores sublistas crecientes

Soluciones

Entradas recientes

Buscar

Correo electrónico