Ir al contenido principal

Matrices dispersas

Misceláneas

Una matriz es dispersa si la mayoriá de sus elementos son ceros. Por ejemplo, la primera de las siguientes matrices es dispersa y la segunda no lo es

( 0 0 4 )   ( 0 1 4 )
( 0 5 0 )   ( 0 5 1 )
( 0 0 0 )

Usando la librería Data.Matrix, las anteriores matrices se pueden definir por

ej1, ej2 :: Matrix Int
ej1 = fromList 3 3 [0,0,4,0,5,0,0,0,0]
ej2 = fromList 2 3 [0,1,4,0,5,1]

La dispersión de una matriz es el cociente entre el número de ceros de la matriz y el producto de sus números de filas y de columnas.

Definir las siguientes funciones

dispersion :: (Num a, Eq a) => Matrix a -> Double
esDispersa :: (Num a, Eq a) => Matrix a -> Bool

tales que

  • (dispersion p) es la dispersión de la matriz p. Por ejemplo,
dispersion ej1              ==  0.7777777777777778
dispersion ej2              ==  0.3333333333333333
dispersion (fmap (+1) ej1)  ==  0.0
dispersion (identity 3)     ==  0.6666666666666666
dispersion (zero 9 9)       ==  1.0
  • (esDispersa p) se verifica si la matriz p es dispersa. Por ejemplo,
esDispersa ej1              ==  True
esDispersa ej2              ==  False
esDispersa (fmap (+1) ej1)  ==  False
esDispersa (identity 3)     ==  True
esDispersa (zero 9 9)       ==  True

Leer más…

Vértices de un cuadrado

Misceláneas

Definir la función

esCuadrado :: (Num a, Ord a) => (a,a) -> (a,a) -> (a,a) -> (a,a) -> Bool

tal que (esCuadrado p q r s) se verifica si los puntos p, q, r y s son los vértices de un cuadrado. Por ejemplo,

esCuadrado (0,0) (0,1) (1,1) (1,0)    == True
esCuadrado (0,0) (2,1) (3,-1) (1, -2) == True
esCuadrado (0,0) (1,1) (0,1) (1,0)    == True
esCuadrado (1,1) (1,1) (1,1) (1,1)    == True
esCuadrado (0,0) (0,2) (3,2) (3,0)    == False
esCuadrado (0,0) (3,4) (8,4) (5,0)    == False
esCuadrado (0,0) (0,0) (1,1) (0,0)    == False
esCuadrado (0,0) (0,0) (1,0) (0,1)    == False
esCuadrado (0,0) (1,0) (0,1) (-1,-1)  == False

Leer más…

Números que no son cuadrados

Misceláneas

Definir las funciones

noCuadrados :: [Integer]
graficaNoCuadrados :: Integer -> IO ()

tales que

  • noCuadrados es la lista de los números naturales que no son cuadrados. Por ejemplo,
λ> take 25 noCuadrados
[2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27,28,29,30]
  • (graficaNoCuadrados n) dibuja las diferencias entre los n primeros elementos de noCuadrados y sus posiciones. Por ejemplo, (graficaNoCuadrados 300) dibuja

Números que no son cuadrados

(graficaNoCuadrados 3000) dibuja

Números que no son cuadrados

(graficaNoCuadrados 30000) dibuja

Números que no son cuadrados

Comprobar con QuickCheck que el término de noCuadrados en la posición n-1 es (n + floor(1/2 + sqrt(n))).

Leer más…

Árboles binarios completos

Misceláneas

Un árbol binario completo es un árbol en el que cada nodo tiene cero o dos hijos. Por ejemplo, el primero de los siguientes árboles es un árbol binario completo pero los otros no lo son

     1              1            1
   /   \          /   \        / | \
  2     3        2     3      2  7  3
 / \            /            / \
4   5          4            4   5

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
  deriving Show

Por ejemplo, los árboles los árboles anteriores se puede representar por

ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 2 [N 4 [], N 5 []], N 3 []]
ej2 = N 1 [N 2 [N 4 []], N 3 []]
ej3 = N 1 [N 2 [N 4 [], N 5 []], N 7 [], N 3 []]

Definir la función

esBinarioCompleto :: Arbol t -> Bool

tal que (esBinarioCompleto a) se verifica si a es un árbol binario completo. Por ejemplo,

esBinarioCompleto ej1  ==  True
esBinarioCompleto ej2  ==  False
esBinarioCompleto ej3  ==  False

Leer más…

Números trimórficos

Misceláneas

Un número trimórfico es un número cuyo cubo termina en dicho número. Por ejemplo, 24 es trimórfico ya que 24^3 = 13824 termina en 24.

Para cada entero positivo n, la densidad de trimórficos hasta n es el cociente entre la cantidad de números trimórficos menores o iguales que n y el número n. Por ejemplo, hasta 10 hay 6 números trimórficos (0, 1, 4, 5, 6 y 9); por tanto, la densidad hasta 10 es 6/10 = 0.6.

Definir las funciones

trimorficos         :: [Integer]
densidadTrimorficos :: Integer -> Double

tal que

  • trimorficos es la lista de los números trimórficos. Por ejemplo,
λ> take 20 trimorficos
[0,1,4,5,6,9,24,25,49,51,75,76,99,125,249,251,375,376,499,501]
  • (densidadTrimorficos n) es la densidad de trimórficos hasta n. Por ejemplo,
densidadTrimorficos 10      ==  0.6
densidadTrimorficos 100     ==  0.13
densidadTrimorficos 1000    ==  2.6e-2
densidadTrimorficos 10000   ==  3.7e-3
densidadTrimorficos 100000  ==  4.8e-4

Leer más…

Períodos de Fibonacci

Misceláneas

Los primeros términos de la sucesión de Fibonacci son

0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610

Al calcular sus restos módulo 3 se obtiene

0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1

Se observa que es periódica y su período es

0,1,1,2,0,2,2,1

Definir las funciones

fibsMod                   :: Integer -> [Integer]
periodoFibMod             :: Integer -> [Integer]
longPeriodosFibMod        :: [Int]
graficaLongPeriodosFibMod :: Int -> IO ()

tales que

  • (fibsMod n) es la lista de los términos de la sucesión de Fibonacci módulo n. Por ejemplo,
λ> take 24 (fibsMod 3)
[0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1]
λ> take 24 (fibsMod 4)
[0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1]
  • (periodoFibMod n) es la parte perioica de la sucesión de Fibonacci módulo n. Por ejemplo,
periodoFibMod 3  ==  [0,1,1,2,0,2,2,1]
periodoFibMod 4  ==  [0,1,1,2,3,1]
periodoFibMod 7  ==  [0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1]
  • longPeriodosFibMod es la sucesión de las longitudes de los períodos de las sucesiones de Fibonacci módulo n, para n > 0. Por ejemplo,
λ> take 20 longPeriodosFibMod
[1,3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60]
  • (graficaLongPeriodosFibMod n) dibuja la gráfica de los n primeros términos de la sucesión longPeriodosFibMod. Por ejemplo, (graficaLongPeriodosFibMod n) dibuja

Períodos de Fibonacci

Leer más…

Recorrido de árboles en espiral

Misceláneas

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
  deriving Show

Por ejemplo, los árboles

     1             1             1
    /  \          / \           / \
   /    \        8   3         8   3
  2      3          /|\       /|\  |
 / \    / \        4 5 6     4 5 6 7
4   5  6   7

se representan por

ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 2 [N 4 [], N 5 []], N 3 [N 6 [], N 7 []]]
ej2 = N 1 [N 8 [], N 3 [N 4 [], N 5 [], N 6 []]]
ej3 = N 1 [N 8 [N 4 [], N 5 [], N 6 []], N 3 [N 7 []]]

Definir la función

espiral :: Arbol a -> [a]

tal que (espiral x) es la lista de los nodos del árbol x recorridos en espiral; es decir, la raíz de x, los nodos del primer nivel de izquierda a derecha, los nodos del segundo nivel de derecha a izquierda y así sucesivamente. Por ejemplo,

espiral ej1  ==  [1,2,3,7,6,5,4]
espiral ej2  ==  [1,8,3,6,5,4]
espiral ej3  ==  [1,8,3,7,6,5,4]

Leer más…

Huecos binarios

Misceláneas

Los huecos binarios de un número natural n son las listas de cer0 entre dos unos en la representación binaria de n. Por ejemplo, puesto que la representación binaria de 20 es 10100 tiene dos hecos binarios de longitudes 1 y 2. La longitud del mayor hueco binario de 529 es 4 ya que la representación binaria de 529 es 1000010001.

Definir las funciones

longMayorHuecoBinario        :: Int -> Int
graficaLongMayorHuecoBinario :: Int -> IO ()

tales que + (longMayorHuecoBinario n) es la longitud del mayor hueco binario de n. Por ejemplo,

longMayorHuecoBinario 20    ==  2
longMayorHuecoBinario 529   ==  4
longMayorHuecoBinario 2018  ==  3
  • (graficaLongMayorHuecoBinario n) dibuja la gráfica de las longitudes de los mayores huecos binarios de los n primeros números naturales. Por ejemplo, (graficaLongMayorHuecoBinario 200) dibuja

Huecos binarios

Leer más…

División equitativa

Misceláneas

Definir la función

divisionEquitativa :: [Int] -> Maybe ([Int],[Int])

tal que (divisionEquitativa xs) determina si la lista de números enteros positivos xs se puede dividir en dos partes (sin reordenar sus elementos) con la misma suma. Si es posible, su valor es el par formado por las dos partes. Si no lo es, su valor es Nothing. Por ejemplo,

divisionEquitativa [1,2,3,4,5,15]  ==  Just ([1,2,3,4,5],[15])
divisionEquitativa [15,1,2,3,4,5]  ==  Just ([15],[1,2,3,4,5])
divisionEquitativa [1,2,3,4,7,15]  ==  Nothing
divisionEquitativa [1,2,3,4,15,5]  ==  Nothing

Leer más…

Celdas interiores de una retícula

Misceláneas

Las celdas de una retícula cuadrada se numeran consecutivamente. Por ejemplo, la numeración de la retícula cuadrada de lado 4 es

 1, 2, 3, 4
 5, 6, 7, 8
 9,10,11,12
13,14,15,16

Los números de sus celdas interiores son 6,7,10,11.

Definir la función

interiores :: Int -> [Int]

tal que (interiores n) es la lista de los números de las celdas interiores de la retícula cuadrada de lado n. Por ejemplo,

interiores 4  == [6,7,10,11]
interiores 5  == [7,8,9,12,13,14,17,18,19]
interiores 6  == [8,9,10,11,14,15,16,17,20,21,22,23,26,27,28,29]
interiores 2  == []
length (interiores 2018)  == 4064256

Comprobar con QuickCheck que el número de celdas interiores de la retícula cuadrada de lado n, con n > 1, es (n-2)^2.

Leer más…

Dígitos iniciales

Misceláneas

Definir las funciones

digitosIniciales        :: [Int]
graficaDigitosIniciales :: Int -> IO ()

tales que

  • digitosIniciales es la lista de los dígitos iniciales de los números naturales. Por ejemplo,
λ> take 100 digitosIniciales
[0,1,2,3,4,5,6,7,8,9,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,
 3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,
 6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,
 9,9,9,9,9,9,9,9,9,9]
  • (graficaDigitosIniciales n) dibuja la gráfica de los primeros n términos de la sucesión digitosIniciales. Por ejemplo, (graficaDigitosIniciales 100) dibuja

Dígitos iniciales

y (graficaDigitosIniciales 1000) dibuja

Dígitos iniciales

Leer más…

Exponentes de Hamming

Misceláneas

Los números de Hamming forman una sucesión estrictamente creciente de números que cumplen las siguientes condiciones:

  • El número 1 está en la sucesión.
  • Si x está en la sucesión, entonces 2x, 3x y 5x también están.
  • Ningún otro número está en la sucesión.

Los primeros números de Hamming son 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, ...

Los exponentes de un número de Hamming n es una terna (x,y,z) tal que n = 2^x*3^y*5^z. Por ejemplo, los exponentes de 600 son (3,1,2) ya que 600 = 2^x*3^1*5^z.

Definir la sucesión

sucExponentesHamming :: [(Int,Int,Int)]

cuyos elementos son los exponentes de los números de Hamming. Por ejemplo,

λ> take 20 sucExponentesHamming
[(0,0,0),(1,0,0),(0,1,0),(2,0,0),(0,0,1),(1,1,0),(3,0,0),
 (0,2,0),(1,0,1),(2,1,0),(0,1,1),(4,0,0),(1,2,0),(2,0,1),
 (3,1,0),(0,0,2),(0,3,0),(1,1,1),(5,0,0),(2,2,0),(3,0,1)]
λ> sucExponentesHamming !! (5*10^5)
(74,82,7)

Leer más…

Recorrido del robot

Misceláneas

Los puntos de una retícula se representan mediante pares de enteros

type Punto = (Int,Int)

y los movimientos de un robot mediante el tipo

data Movimiento = N Int
                | S Int
                | E Int
                | O Int

donde (N x) significa que se mueve x unidades en la dirección norte y análogamente para las restantes direcciones (S es sur, E es este y O es oeste).

Definir la función

posicion :: [Movimiento] -> Punto

tal que (posicion ms) es la posición final de un robot que inicialmente está en el el punto (0,0) y realiza los movimientos ms. Por ejemplo,

posicion [N 3]                           ==  (0,3)
posicion [N 3, E 5]                      ==  (5,3)
posicion [N 3, E 5, S 1]                 ==  (5,2)
posicion [N 3, E 5, S 1, O 4]            ==  (1,2)
posicion [N 3, E 5, S 1, O 4, N 3]       ==  (1,5)
posicion [N 3, E 5, S 1, O 4, N 3, S 3]  ==  (1,2)

Leer más…

Relaciones arbóreas

Misceláneas

Como se explica en el ejercicio Relación definida por un árbol, cada árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y.

Una relación binaria es arbórea si

  • hay exactamente un elemento que no tiene ningún (la raíz del árbol) y
  • todos los elementos tienen dos hijos (los nodos internos) o ninguno (las hojas del árbol).

Definir la función

arborea :: Eq a => [(a,a)] -> Bool

tal que (arborea r) se verifica si la relación r es arbórea. Por ejemplo,

arborea [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]  ==  True
arborea [(8,3),(8,5),(10,2),(2,2),(2,0)]         ==  False
arborea [(10,8),(8,3),(8,5),(10,2),(8,2),(2,0)]  ==  False

Leer más…

Máxima distancia en árbol

Misceláneas

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

     10
    /  \
   /    \
  8      1
 / \    / \
3   9  2   6

se puede representar por

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 9))
               (N 1 (H 2) (H 6))

La distancia entre un padre y un hijo en el árbol es el valor absoluto de la diferencia de sus valores. Por ejemplo, la distancia de 10 a 8 es 2 y de 1 a 6 es 5.

Definir la función

maximaDistancia :: (Num a, Ord a) => Arbol a -> a

tal que (maximaDistancia a) es la máxima distancia entre un padre y un hijo del árbol a. Por ejemplo,

maximaDistancia ejArbol                                     ==  9
maximaDistancia (N 1 (N 8 (H 3) (H 9)) (N 1  (H 2) (H 6)))  ==  7
maximaDistancia (N 8 (N 8 (H 3) (H 9)) (N 10 (H 2) (H 6)))  ==  8

Leer más…

Relación definida por un árbol

Misceláneas

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

     10
    /  \
   /    \
  8      2
 / \    / \
3   5  2   0

se pueden representar por

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 5))
               (N 2 (H 2) (H 0))

Un árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y. Por ejemplo, la relación definida por el árbol anterior es [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)].

Definir la función

relacionDelArbol :: Arbol a -> [(a,a)]

tal que (relacionDelArbol a) es la relación binaria definida por el árbol a. Por ejemplo,

λ> relacionDelArbol ejArbol
[(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]
λ> relacionDelArbol (N 10 (H 8) (N 2 (H 2) (H 0)))
[(10,8),(10,2),(2,2),(2,0)]
λ> relacionDelArbol (N 10 (N 8 (H 3) (H 5)) (H 2))
[(10,8),(8,3),(8,5),(10,2)]
λ> relacionDelArbol (H 10)
[]

Leer más…

Sucesión de Lichtenberg

Misceláneas

La sucesión de Lichtenberg esta formada por la representación decimal de los números binarios de la sucesión de dígitos 0 y 1 alternados. Los primeros términos de ambas sucesiones son

Alternada ..... Lichtenberg
0 ....................... 0
1 ....................... 1
10 ...................... 2
101 ..................... 5
1010 ................... 10
10101 .................. 21
101010 ................. 42
1010101 ................ 85
10101010 .............. 170
101010101 ............. 341
1010101010 ............ 682
10101010101 .......... 1365
101010101010 ......... 2730

Definir las funciones

lichtenberg        :: [Integer]
graficaLichtenberg :: Int -> IO ()

tales que

  • lichtenberg es la lista cuyos elementos son los términos de la sucesión de Lichtenberg. Por ejemplo,
λ> take 17 lichtenberg
[0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690]
  • (graficaLichtenberg n) dibuja la gráfica del número de dígitos de los n primeros términos de la sucesión de Lichtenberg. Por ejemlo, (graficaLichtenberg 100) dibuja

Sucesión de Lichtenberg

Comprobar con QuickCheck que todos los términos de la sucesión de Lichtenberg, a partir del 4º, son números compuestos.

Leer más…

Sucesión de dígitos 0 y 1 alternados

Misceláneas

Los primeros términos de la sucesión de los dígitos 0 y 1 alternados son

0
1
10
101
1010
10101
101010
1010101
10101010
101010101

Definir la lista

sucAlternada :: [Integer]

tal que sus elementos son los términos de la sucesión de los dígitos 0 y 1 alternados. Por ejemplo,

λ> take 10 sucAlternada
[0,1,10,101,1010,10101,101010,1010101,10101010,101010101]

Leer más…

Sumas parciales de Juzuk

Misceláneas

En 1939 Dov Juzuk extendió el método de Nicómaco del cálculo de los cubos. La extensión se basaba en los siguientes pasos:

  • se comienza con la lista de todos los enteros positivos
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
  • se agrupan tomando el primer elemento, los dos siguientes, los tres siguientes, etc.
[[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15], ...
  • se seleccionan los elementos en posiciones pares
[[1],         [4, 5, 6],                [11, 12, 13, 14, 15], ...
  • se suman los elementos de cada grupo
[1,           15,                       65,                   ...
  • se calculan las sumas acumuladas
[1,           16,                       81,                   ...

Las sumas obtenidas son las cuantas potencias de los números enteros positivos.

Definir las funciones

listasParcialesJuzuk :: [a] -> [[a]]
sumasParcialesJuzuk  :: [Integer] -> [Integer]

tal que

  • (listasParcialesJuzuk xs) es lalista de ls listas parciales de Juzuk; es decir, la selección de los elementos en posiciones pares de la agrupación de los elementos de xs tomando el primer elemento, los dos siguientes, los tres siguientes, etc. Por ejemplo,
λ> take 4 (listasParcialesJuzuk [1..])
[[1],[4,5,6],[11,12,13,14,15],[22,23,24,25,26,27,28]]
λ> take 4 (listasParcialesJuzuk [1,3..])
[[1],[7,9,11],[21,23,25,27,29],[43,45,47,49,51,53,55]]
  • (sumasParcialesJuzuk xs) es la lista de las sumas acumuladas de los elementos de las listas de Juzuk generadas por xs. Por ejemplo,
take 4 (sumasParcialesJuzuk [1..])  ==  [1,16,81,256]
take 4 (sumasParcialesJuzuk [1,3..])  ==  [1,28,153,496]

Comprobar con QuickChek que, para todo entero positivo n,

  • el elemento de (sumasParcialesJuzuk [1..]) en la posición (n-1) es n^4.
  • el elemento de (sumasParcialesJuzuk [1,3..]) en la posición (n-1) es n^2*(2*n^2 - 1).
  • el elemento de (sumasParcialesJuzuk [1,5..]) en la posición (n-1) es 4*n^4-3*n^2.
  • el elemento de (sumasParcialesJuzuk [2,3..]) en la posición (n-1) es n^2*(n^2+1).

Leer más…

Complemento potencial

Misceláneas

El complemento potencial de un número entero positivo x es el menor número y tal que el producto de x por y es un una potencia perfecta. Por ejemplo,

  • el complemento potencial de 12 es 3 ya que 12 y 24 no son potencias perfectas pero 36 sí lo es;
  • el complemento potencial de 54 es 4 ya que 54, 108 y 162 no son potencias perfectas pero 216 = 6^3 sí lo es.

Definir las funciones

complemento                 :: Integer -> Integer
graficaComplementoPotencial :: Integer -> IO ()

tales que

  • (complemento x) es el complemento potencial de x; por ejemplo,
complemento 12     ==  3
complemento 54     ==  4
complemento 720    ==  5
complemento 24000  ==  9
complemento 2018   ==  2018
  • (graficaComplementoPotencial n) dibuja la gráfica de los complementos potenciales de los n primeros números enteros positivos. Por ejemplo, (graficaComplementoPotencial 100) dibuja

Complemento potencial

y (graficaComplementoPotencial 500) dibuja

Complemento potencial

Comprobar con QuickCheck que (complemento x) es menor o igual que x.

Leer más…

Terna pitagorica a partir de un lado

Misceláneas

Una terna pitagórica con primer lado x es una terna (x,y,z) tal que x^2 + y^2 = z^2. Por ejemplo, las ternas pitagóricas con primer lado 16 son (16,12,20), (16,30,34) y (16,63,65).

Definir las funciones

ternasPitagoricas      :: Integer -> [(Integer,Integer,Integer)]
mayorTernaPitagorica   :: Integer -> (Integer,Integer,Integer)
graficaMayorHipotenusa :: Integer -> IO ()

tales que

  • (ternasPitgoricas x) es la lista de las ternas pitagóricas con primer lado x. Por ejemplo,
ternasPitagoricas 16 == [(16,12,20),(16,30,34),(16,63,65)]
ternasPitagoricas 20 == [(20,15,25),(20,21,29),(20,48,52),(20,99,101)]
ternasPitagoricas 25 == [(25,60,65),(25,312,313)]
ternasPitagoricas 26 == [(26,168,170)]
  • (mayorTernaPitagorica x) es la mayor de las ternas pitagóricas con primer lado x. Por ejemplo,
mayorTernaPitagorica 16     ==  (16,63,65)
mayorTernaPitagorica 20     ==  (20,99,101)
mayorTernaPitagorica 25     ==  (25,312,313)
mayorTernaPitagorica 26     ==  (26,168,170)
mayorTernaPitagorica3 2018  ==  (2018,1018080,1018082)
mayorTernaPitagorica3 2019  ==  (2019,2038180,2038181)
  • (graficaMayorHipotenusa n) dibuja la gráfica de las sucesión de las mayores hipotenusas de las ternas pitagóricas con primer lado x, para x entre 3 y n. Por ejemplo, (graficaMayorHipotenusa 100) dibuja

Terna pitagorica a partir de un lado

Leer más…

Escalada hasta un primo

Misceláneas

Este ejercicio está basado en el artículo La conjetura de la "escalada hasta un primo" publicado esta semana por Miguel Ángel Morales en su blog Gaussianos.

La conjetura de escalada hasta un primo, propuesta por John Horton Conway, es sencilla de plantear, pero primero vamos a ver qué es eso de escalar hasta un primo. Tomamos un número cualquiera y lo descomponemos en factores primos (colocados en orden ascendente). Si el número era primo, ya hemos acabado; si no era primo, construimos el número formado por los factores primos y los exponentes de los mismos colocados tal cual salen en la factorización. Con el número obtenido hacemos lo mismo que antes. La escalada finaliza cuando obtengamos un número primo. Por ejemplo, para obtener la escalada prima de 1400, como no es primo, se factoriza (obteniéndose 2^3 * 5^2 * 7) y se unen bases y exponentes (obteniéndose 23527). Con el 23527 se repite el proceso obteniéndose la factorización (7 * 3361) y su unión (73361). Como el 73361 es primo, termina la escalada. Por tanto, la escalada de 1400 es [1400,23527,73361].

La conjetura de Conway sobre "escalada hasta un primo" dice que todo número natural mayor o igual que 2 termina su escalada en un número primo.

Definir las funciones

escaladaPrima                :: Integer -> [Integer]
longitudEscaladaPrima        :: Integer -> Integer
longitudEscaladaPrimaAcotada :: Integer -> Integer -> Integer
graficaEscalada              :: Integer -> Integer -> IO ()

tales que

  • (escaladaPrima n) es la escalada prima de n. Por ejemplo,
λ> escaladaPrima 1400
[1400,23527,73361]
λ> escaladaPrima 333
[333,3237,31383,3211317,3217139151,39722974813]
λ> take 10 (escaladaPrima 20)
[20,225,3252,223271,297699,399233,715623,3263907,32347303,160720129]
λ> take 3 (escaladaPrima 13532385396179)
[13532385396179,13532385396179,13532385396179]
λ> take 2 (escaladaPrima 45214884853168941713016664887087462487)
[45214884853168941713016664887087462487,13532385396179]
  • (longitudEscaladaPrima n) es la longitud de la escalada prima de n. Por ejemplo,
longitudEscaladaPrima 1400  ==  3
longitudEscaladaPrima 333   ==  6
  • (longitudEscaladaPrimaAcotada n k) es el mínimo entre la longitud de la escalada prima de n y k. Por ejemplo,
longitudEscaladaPrimaAcotada 333 10  ==  6
longitudEscaladaPrimaAcotada 333 4   ==  4
longitudEscaladaPrimaAcotada 20 4    ==  4
  • (graficaEscalada n k) dibuja la gráfica de (longitudEscaladaPrimaAcotada x k) para x entre 2 y n. Por ejemplo, (graficaEscalada 120 15) dibuja

Escalada hasta un primo

Leer más…

Números como diferencias de potencias

Misceláneas

El número 45 se puede escribir de tres formas como diferencia de los cuadrados de dos números naturales:

45 =  7^2 -  2^2
   =  9^2 -  6^2
   = 23^2 - 22^2

Definir la función

   diferencias :: Integer -> Integer -> [(Integer,Integer)]

tal que (diferencias x n) es la lista de pares tales que la diferencia de sus potencias n-ésima es x. Por ejemplo,

   diferencias 45 2    ==  [(7,2),(9,6),(23,22)]
   diferencias 50 2    ==  []
   diferencias 19 3    ==  [(3,2)]
   diferencias 8 3     ==  [(2,0)]
   diferencias 15 4    ==  [(2,1)]
   diferencias 4035 2  ==  [(142,127),(406,401),(674,671),(2018,2017)]
   head (diferencias 1161480105172255454401 5)  ==  (123456,123455)

Leer más…

Sumas parciales de Nicómaco

Misceláneas

Nicómaco de Gerasa vivió en Palestina entre los siglos I y II de nuestra era. Escribió Arithmetike eisagoge (Introducción a la aritmética) que es el primer trabajo en donde se trata la Aritmética de forma separada a la Geometría. En el tratado se encuentra la siguiente proposición: "si se escriben los números impares

1, 3, 5, 7, 9, 11, 13, 15, 17, ...

entonces el primero es el cubo de 1; la suma de los dos siguientes, el cubo de 2; la suma de los tres siguientes, el cubo de 3; y así sucesivamente."

Definir las siguientes funciones

listasParciales :: [a] -> [[a]]
sumasParciales  :: [Int] -> [Int]

tales que

  • (listasParciales xs) es la lista obtenido agrupando los elementos de la lista infinita xs de forma que la primera tiene 0 elementos; la segunda, el primer elemento de xs; la tercera, los dos siguientes; y así sucesivamente. Por ejemplo,
λ> take 7 (listasParciales [1..])
[[],[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15],[16,17,18,19,20,21]]
λ> take 7 (listasParciales [1,3..])
[[],[1],[3,5],[7,9,11],[13,15,17,19],[21,23,25,27,29],[31,33,35,37,39,41]]
  • (sumasParciales xs) es la lista de las sumas parciales de la lista infinita xs. Por ejemplo,
λ> take 15 (sumasParciales [1..])
[0,1,5,15,34,65,111,175,260,369,505,671,870,1105,1379]
λ> take 15 (sumasParciales [1,3..])
[0,1,8,27,64,125,216,343,512,729,1000,1331,1728,2197,2744]

Comprobar con QuickChek la propiedad de Nicómaco; es decir, que para todo número natural n, el término n-ésimo de (sumasParciales [1,3..]) es el cubo de n.

Leer más…

Números malvados y odiosos

Misceláneas

Un número malvado es un número natural cuya expresión en base 2 (binaria) contiene un número par de unos.

Un número odioso es un número natural cuya expresión en base 2 (binaria) contiene un número impar de unos.

Podemos representar los números malvados y odiosos mediante el siguiente tipo de dato

data MalvadoOdioso = Malvado | Odioso deriving Show

Definir la función

malvadoOdioso :: Integer -> MalvadoOdioso

tal que (malvadoOdioso n) devuelve el tipo de número que es n. Por ejemplo,

λ> malvadoOdioso 11
Odioso
λ> malvadoOdioso 12
Malvado
λ> malvadoOdioso3 (10^20000000)
Odioso
λ> malvadoOdioso3 (1+10^20000000)
Malvado

Leer más…

Ordenación por frecuencia

Misceláneas

Definir la función

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

tal que (ordPorFrecuencia xs) es la lista obtenidas ordenando los elementos de xs por su frecuencia, de los que aparecen más a los que aparecen menos, y los que aparecen el mismo número de veces se ordenan de manera creciente según su valor. Por ejemplo,

ordPorFrecuencia "canalDePanama"      ==  "aaaaannmlecPD"
ordPorFrecuencia "11012018"           ==  "11110082"
ordPorFrecuencia [2,3,5,3,7,9,5,3,7]  ==  [3,3,3,7,7,5,5,9,2]

Leer más…

Números somirp

Misceláneas

Un número omirp es un número primo que forma un primo distinto al invertir el orden de sus dígitos.

Definir las funciones

esOmirp            :: Integer -> Bool
omirps             :: [Integer]
nOmirpsIntermedios :: Int -> Int

tales que

  • (esOmirp n) se verifica si n es un número omirp. Por ejemplo,
esOmirp 13      ==  True
esOmirp 11      ==  False
esOmirp 112207  ==  True
  • omirps es la lista de los números omirps. Por ejemplo,
take 15 omirps  ==  [13,17,31,37,71,73,79,97,107,113]
omirps !! 2000  ==  112207
  • (nOmirpsIntermedios n) es la cantidad de números omirps entre el n-ésimo número omirp y el obtenido al invertir el orden de sus dígitos. Por ejemplo,
nOmirpsIntermedios 2000  ==  4750

Leer más…

Enumeración de los números enteros

Misceláneas

Definir la sucesión

enteros :: [Int]

tal que sus elementos son los números enteros comenzando en el 0 e intercalando los positivos y los negativos. Por ejemplo,

λ> take 23 enteros
[0,1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10,11,-11]

Comprobar con QuickCheck que el n-ésimo término de la sucesión es (1-(2*n+1)*(-1)^n)/4.

Nota. En la comprobación usar

quickCheckWith (stdArgs {maxSize=7}) prop_enteros

Leer más…

Números apocalípticos

Misceláneas

Un número apocalíptico es aquel número natural n tal que 2^n contiene la secuencia 666.

Definir las funciones

esApocaliptico           :: Integer -> Bool
apocalipticos            :: [Integer]
mayorNoApocalipticoMenor :: Integer -> Maybe Integer
grafica                  :: Integer -> IO ()

tales que

  • (esApocaliptico n) se verifica si n es un número apocalíptico. Por ejemplo,
esApocaliptico 666    ==  True
esApocaliptico 29784  ==  False
  • apocalipticos es la lista de los números apocalípticos. Por ejemplo,
take 9 apocalipticos  ==  [157,192,218,220,222,224,226,243,245]
apocalipticos !! 55   ==  666
  • (mayorNoApocalipticoMenor n) es justo el mayor número no apocalíptico menor que n. Por ejemplo,
mayorNoApocalipticoMenor  40000  ==  Just 29784
mayorNoApocalipticoMenor  29784  ==  Just 26667
  • (grafica n) dibuja las gráficas de los n primeros términos de la sucesión de los números apocalípticos junto con los de la sucesión a(n) = 3715+n. Por ejemplo, (grafica 3000) dibuja

Números apocalípticos

y (grafica 30000) dibuja

Números apocalípticos

Leer más…

Padres como sumas de hijos

Misceláneas

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

     10
    /  \
   /    \
  8      2
 / \    / \
3   5  2   0

se pueden representar por

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 5))
               (N 2 (H 2) (H 0))

Un árbol cumple la propiedad de la suma si el valor de cada nodo es igual a la suma de los valores de sus hijos. Por ejemplo, el árbol anterior cumple la propiedad de la suma.

Definir la función

propSuma :: Arbol Int -> Bool

tal que (propSuma a) se verifica si el árbol a cumple la propiedad de la suma. Por ejemplo,

λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 0)))
True
λ> propSuma (N 10 (N 8 (H 4) (H 5)) (N 2 (H 2) (H 0)))
False
λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 1)))
False

Leer más…

Problema del cambio de monedas

Misceláneas

El problema del cambio de monedas consiste en dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el número de formas de obtener y usando los tipos de monedas de ms. Por ejemplo, con monedas de 1, 5 y 10 céntimos se puede obtener 12 céntimos de 4 formas

1,1,1,1,1,1,1,1,1,1,1,1
1,1,1,1,1,1,1,5
1,1,5,5
1,1,10

Definir las funciones

numeroCambios :: [Int] -> Int -> Int
sucCambios :: [Int]
grafica_cambios :: Int -> IO ()

tales que

  • (numeroCambios ms x) es el número de formas de obtener x usando los tipos de monedas de ms. Por ejemplo,
numeroCambios [1,5,10] 12  ==  4
numeroCambios [4,1,3] 6    ==  4
numeroCambios [1,5,10] 50  ==  36
  • sucCambios es la sucesión cuyo k-ésimo término es el número de cambios de k usando monedas de 1, 2, 5 y 10 céntimos. Por ejemplo,
λ> take 20 sucCambios
[1,1,2,2,3,4,5,6,7,8,11,12,15,16,19,22,25,28,31,34]
  • (grafica_cambios n) dibuja la gráfica de los n primeros términos de la sucesión sucCambios. Por ejemplo, (grafica_cambios 50) dibuja

Problema del cambio de monedas

Leer más…

Ofertas 3 por 2

Misceláneas

En una tienda tienen la "oferta 3 por 2" de forma que cada cliente que elige 3 artículos obtiene el más barato de forma gratuita. Por ejemplo, si los precios de los artículos elegidos por un cliente son 10, 2, 4, 5 euros pagará 19 euros si agrupa los artículos en (10,2,4) y (5) o pagará 17 si lo agupa en (5,10,4) y (2).

Definir la función

minimoConOferta :: [Int] -> Int

tal que (minimoConOferta xs) es lo mínimo que pagará el cliente si los precios de la compra son xs; es decir, lo que pagará agrupando los artículos de forma óptima para aplicar la oferta 3 por 2. Por ejemplo,

minimoConOferta [10,2,4,5]     ==  17
minimoConOferta [3,2,3,2]      ==  8
minimoConOferta [6,4,5,5,5,5]  ==  21

Leer más…

El problema 3SUM

Misceláneas

El problem 3SUM consiste en dado una lista xs, decidir si xs posee tres elementos cuya suma sea cero. Por ejemplo, en [7,5,-9,5,2] se puede elegir los elementos 7, -9 y 2 que suman 0.

Definir las funciones

sols3Sum :: [Int] -> [[Int]]
pb3Sum :: [Int] -> Bool

tales que

  • (sols3Sum xs) son las listas de tres elementos de xs cuya suma sea cero. Por ejemplo,
sols3Sum [8,10,-10,-7,2,-3]   ==  [[-10,2,8],[-7,-3,10]]
sols3Sum [-2..3]              ==  [[-2,-1,3],[-2,0,2],[-1,0,1]]
sols3Sum [1,-2]               ==  []
sols3Sum [-2,1]               ==  []
sols3Sum [1,-2,1]             ==  [[-2,1,1]]
length (sols3Sum [-100..100]) ==  5000
  • (pb3Sum xs) se verifica si xs posee tres elementos cuya suma sea cero. Por ejemplo,
pb3Sum [8,10,-10,-7,2,-3]  ==  True
pb3Sum [1,-2]              ==  False
pb3Sum [-2,1]              ==  False
pb3Sum [1,-2,1]            ==  True
pb3Sum [1..400]            ==  False

Leer más…

De hexadecimal a decimal

Misceláneas

El sistema hexadecimal es el sistema de numeración posicional que tiene como base el 16.

En principio, dado que el sistema usual de numeración es de base decimal y, por ello, sólo se dispone de diez dígitos, se adoptó la convención de usar las seis primeras letras del alfabeto latino para suplir los dígitos que nos faltan. El conjunto de símbolos es el siguiente: {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. En ocasiones se emplean letras minúsculas en lugar de mayúsculas. Se debe notar que A = 10, B = 11, C = 12, D = 13, E = 14 y F = 15.

Como en cualquier sistema de numeración posicional, el valor numérico de cada dígito es alterado dependiendo de su posición en la cadena de dígitos, quedando multiplicado por una cierta potencia de la base del sistema, que en este caso es 16. Por ejemplo, el valor decimal del número hexadecimal 3E0A es

  3×16^3 + E×16^2 + 0×16^1 + A×16^0
= 3×4096 + 14×256 + 0×16   + 10×1
= 15882

Definir la función

hexAdec :: String -> Int

tal que (hexAdec cs) es el valor decimal del número hexadecimal representado meiante la cadena cs. Por ejemplo,

hexAdec "3E0A"   == 15882
hexAdec "ABCDEF" == 11259375
hexAdec "FEDCBA" == 16702650

Leer más…

Ordenación según una cadena

Misceláneas

Dada una lista xs y una cadena cs de la misma longitud, la ordenación de xs según cs consiste en emparejar los elementos de cs con los de xs (de forma que al menor elemento de cs le corresponde el menor de xs, al segundo de cs el segundo de xs, etc.) y ordenar los elementos de xs en el mismo orden que sus correspondientes elementos de cs. Por ejemplo, si xs es [6,4,2] y cs es "CAB" entonces a 'A' le corresponde el 2, a 'B' el 4 y a 'C' el 6; luego la ordenación es [6,2,4].

Definir la función

ordenacion :: Ord a => [a] -> String -> [a]

tal que (ordenacion xs ys) es la ordenación de la lista xs según la cadena cs. Por ejemplo,

ordenacion [6,4,2] "CAB"     ==  [6,2,4]
ordenacion [1,5,3] "ABC"     ==  [1,3,5]
ordenacion [1,5,3,7] "ABEC"  ==  [1,3,7,5]

Leer más…

Factorial módulo

Misceláneas

Definir la función

factorialMod :: Integer -> Integer -> Integer

tal que (factorialMod n x) es el factorial de x módulo n. Por ejemplo,

factorialMod (7+10^9) 100       ==  437918130
factorialMod (7+10^9) (5*10^6)  ==  974067448

Leer más…

Recorrido por niveles de árboles binarios

Misceláneas

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

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

se pueden representar por

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

Definir la función

recorrido :: Arbol t -> [t]

tal que (recorrido a) es el recorrido del árbol a por niveles desde la raíz a las hojas y de izquierda a derecha. Por ejemplo,

λ> recorrido (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
[1,2,3,4,5,6,7,8,9]
λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (N 5 (H 8) (H 9))))
[1,3,2,6,7,4,5,8,9]
λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (H 5)))
[1,3,2,6,7,4,5]
λ> recorrido (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))
[1,2,3,4,5,6,7]
λ> recorrido (N 1 (N 2 (H 4) (H 5)) (H 3))
[1,2,3,4,5]
λ> recorrido (N 1 (H 4) (H 3))
[1,4,3]
λ> recorrido (H 3)
[3]

Leer más…

Sucesión de raíces enteras de los números primos

Misceláneas

Definir las siguientes funciones

raicesEnterasPrimos :: [Integer]
posiciones :: Integer -> (Int,Int)
frecuencia :: Integer -> Int
grafica_raicesEnterasPrimos :: Int -> IO ()
grafica_posicionesIniciales :: Integer -> IO ()
grafica_frecuencias :: Integer -> IO ()

tales que

  • raicesEnterasPrimos es la sucesión de las raíces enteras (por defecto) de los números primos. Por ejemplo,
λ> take 20 raicesEnterasPrimos
[1,1,2,2,3,3,4,4,4,5,5,6,6,6,6,7,7,7,8,8]
λ> raicesEnterasPrimos !! 2500000
6415
  • (posiciones x) es el par formado por la menor y la mayor posición de x en la sucesión de las raíces enteras de los números primos. Por ejemplo,
posiciones 2     ==  (2,3)
posiciones 4     ==  (6,8)
posiciones 2017  ==  (287671,287931)
posiciones 2018  ==  (287932,288208)
  • (frecuencia x) es el número de veces que aparece x en la sucesión de las raíces enteras de los números primos. Por ejemplo,
frecuencia 2     ==  2
frecuencia 4     ==  3
frecuencia 2017  ==  261
frecuencia 2018  ==  277
  • (grafica_raicesEnterasPrimos n) dibuja la gráfica de los n primeros términos de la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_raicesEnterasPrimos 200) dibuja

Sucesión de raíces enteras de los números primos

  • (grafica_posicionesIniciales n) dibuja la gráfica de las menores posiciones de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_posicionesIniciales 200) dibuja

Sucesión de raíces enteras de los números primos

  • (grafica_frecuencia n) dibuja la gráfica de las frecuencia de los n primeros números en la sucesión de las raíces enteras de los números primos. Por ejemplo, (grafica_frecuencia 200) dibuja

Sucesión de raíces enteras de los números primos

Leer más…

Posiciones de las mayúsculas

Misceláneas

Definir la función

posicionesMayusculas :: String -> [Int]

tal que (posicionesMayusculas cs) es la lista de las posiciones de las mayúsculas de la cadena cs. Por ejemplo,

posicionesMayusculas "SeViLLa"  == [0,2,4,5]
posicionesMayusculas "aAbB"     == [1,3]
posicionesMayusculas "ABCDEF"   == [0,1,2,3,4,5]
posicionesMayusculas "4ysdf4"   == []
posicionesMayusculas ""         == []

Leer más…

Rotaciones divisibles por 8

Misceláneas

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816 de las que 3 son divisibles por 8 (928160, 160928 y 92816).

Definir la función

nRotacionesDivisiblesPor8 :: Integer -> Int

tal que (nRotacionesDivisiblesPor8 x) es el número de rotaciones de x divisibles por 8. Por ejemplo,

nRotacionesDivisiblesPor8 928160       ==  3
nRotacionesDivisiblesPor8 43262488612  ==  4
nRotacionesDivisiblesPor8 (read (take (10^4) (cycle "248")))  ==  6666

Leer más…

Sumable sin vecinos

Misceláneas

En la lista [3,2,5,7,4] el número 12 se puede escribir como una suma de elementos de la lista sin incluir sus vecinos (ya que es la suma de 3, 5 y 4); en cambio, 14 no lo es (porque es la suma de 3, 7 y 4, pero 7 y 4 son vecinos).

Definir la función

esSumableSinVecinos :: [Int] -> Int -> Bool

tal que (esSumableSinVecinos xs n) se verifica si n se puede escribir como una suma de elementos de xs que no incluye a ninguno de sus vecinos. Por ejemplo,

esSumableSinVecinos [3,2,5,7,4] 12  ==  True
esSumableSinVecinos [3,2,5,7,4] 9   ==  True
esSumableSinVecinos [3,2,5,7,4] 6   ==  True
esSumableSinVecinos [3,2,5,7,4] 14  ==  False
esSumableSinVecinos [3,2,5,7,4] 1   ==  False

Leer más…

Suma de las hojas de mínimo nivel

Misceláneas

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

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

se pueden representar por

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

En el árbol anterior, los valores de las hojas de menor nivel son 4, 6 y 7 cuya suma es 17.

Definir la función

suma :: Num t => Arbol t -> t

tal que (suma a) es la suma de los valores de las hojas de menor nivel del árbol a. Por ejemplo,

suma ejArbol                                    ==  17
suma (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))  ==  22
suma (N 1 (H 2) (N 3 (H 6) (H 7)))              ==  2
suma (N 1 (H 2) (H 3))                          ==  5
suma (H 2)                                      ==  2

Leer más…

Vecino en lista circular

Misceláneas

En la lista circular [3,2,5,7,9]

  • el vecino izquierdo de 5 es 2 y su vecino derecho es 7,
  • el vecino izquierdo de 9 es 7 y su vecino derecho es 3,
  • el vecino izquierdo de 3 es 9 y su vecino derecho es 2,
  • el elemento 4 no tiene vecinos (porque no está en la lista).

Para indicar las direcciones se define el tipo de datos

data Direccion = I | D deriving Eq

Definir la función

vecino :: Eq a => Direccion -> [a] -> a -> Maybe a

tal que (vecino d xs x) es el vecino de x en la lista de elementos distintos xs según la dirección d. Por ejemplo,

vecino I [3,2,5,7,9] 5  ==  Just 2
vecino D [3,2,5,7,9] 5  ==  Just 7
vecino I [3,2,5,7,9] 9  ==  Just 7
vecino D [3,2,5,7,9] 9  ==  Just 3
vecino I [3,2,5,7,9] 3  ==  Just 9
vecino D [3,2,5,7,9] 3  ==  Just 2
vecino I [3,2,5,7,9] 4  ==  Nothing
vecino D [3,2,5,7,9] 4  ==  Nothing

Leer más…

Cadenas opuestas

Misceláneas

La opuesta de una cadena de letras es la cadena obtenida cambiando las minúsculas por mayúsculas y las minúsculas por mayúsculas. Por ejemplo, la opuesta de "SeViLLa" es "sEvIllA".

Definir la función

esOpuesta :: String -> String -> Bool

tal que (esOpuesta s1 s2) se verifica si las cadenas de letras s1 y s2 son opuestas. Por ejemplo,

esOpuesta "ab" "AB"      `== True
esOpuesta "aB" "Ab"      `== True
esOpuesta "aBcd" "AbCD"  `== True
esOpuesta "aBcde" "AbCD" `== False
esOpuesta "AB" "Ab"      `== False
esOpuesta "" ""          `== True

Leer más…

Menor con suma de dígitos dada

Misceláneas

Definir la función

minSumDig :: Integer -> Integer

tal que (minSumDig n) es el menor número x tal que la suma de los dígitos de x es n. Por ejemplo,

minSumDig 1   ==  1
minSumDig 12  ==  39
minSumDig 21  ==  399
(length . show . minSumDig) (3*10^5)  ==  33334
(length . show . minSumDig) (3*10^6)  ==  333334
(length . show . minSumDig) (3*10^7)  ==  3333334
(length . show . minSumDig) (4*10^7)  ==  4444445
(length . show . minSumDig) (5*10^7)  ==  5555556

Leer más…

Aplicaciones biyectivas

Misceláneas

Definir las funciones

biyectivas  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
nBiyectivas :: (Ord a, Ord b) => [a] -> [b] -> Integer

tales que

  • (biyectivas xs ys) es el conjunto de las aplicaciones biyectivas del conjunto xs en el conjunto ys. Por ejemplo,
λ> biyectivas [1,3] [2,4]
[[(1,2),(3,4)],[(1,4),(3,2)]]
λ> biyectivas [1,3,5] [2,4,6]
[[(1,2),(3,4),(5,6)],[(1,4),(3,2),(5,6)],[(1,6),(3,4),(5,2)],
 [(1,4),(3,6),(5,2)],[(1,6),(3,2),(5,4)],[(1,2),(3,6),(5,4)]]
λ> biyectivas [1,3] [2,4,6]
[]
  • (nBiyectivas xs ys) es el número de aplicaciones biyectivas del conjunto xs en el conjunto ys. Por ejemplo,
nBiyectivas [1,3] [2,4]      ==  2
nBiyectivas [1,3,5] [2,4,6]  ==  6
λ> nBiyectivas [1,3] [2,4,6] ==  0
length (show (nBiyectivas2 [1..2*10^4] [1..2*10^4]))  ==  77338

Nota: En este ejercicio los conjuntos se representan mediante listas ordenadas de elementos distintos.

Leer más…

Bosque de recorridos del autobús

Misceláneas

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ejArbol1 = Node 3 [Node 5 [Node 9 []], Node 7 []]
ejArbol2 = Node 8 [Node 4 []]

También se pueden definir bosques. Por ejemplo,

ejBosque = [ejArbol1, ejArbol2]

Se pueden dibujar los bosques con la función drawForest. Por ejemplo,

λ> putStrLn (drawForest (map (fmap show) ejBosque))
3
|
+- 5
|  |
|  `- 9
|
`- 7

8
|
`- 4

Usando la notación de los ejercicios anteriores para las subidas y bajadas en el autobús, definir la función

bosqueRecorridos :: Int -> Int -> Forest (Int,Int)

tal que (bosqueRecorridos n m) es el bosque cuyas ramas son los recorridos correctos en un autobús de capacidad n y usando m paradas. Por ejemplo,

λ> putStrLn (drawForest (map (fmap show) (bosqueRecorridos 2 3)))
(0,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (1,0)
|  |
|  `- (2,0)
|
+- (1,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
`- (2,0)
   |
   +- (0,0)
   |
   +- (0,1)
   |
   `- (0,2)

(1,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
+- (0,1)
|  |
|  +- (0,0)
|  |
|  +- (1,0)
|  |
|  `- (2,0)
|
+- (1,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  `- (0,2)
|
`- (1,1)
   |
   +- (0,0)
   |
   +- (0,1)
   |
   +- (1,0)
   |
   `- (1,1)

(2,0)
|
+- (0,0)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  `- (0,2)
|
+- (0,1)
|  |
|  +- (0,0)
|  |
|  +- (0,1)
|  |
|  +- (1,0)
|  |
|  `- (1,1)
|
`- (0,2)
   |
   +- (0,0)
   |
   +- (1,0)
   |
   `- (2,0)

en donde la última rama representa el recorrido [(2,0),(0,2),(2,0)].

Leer más…

Reconocimiento de recorridos correctos

Misceláneas

Se usará la misma representación del ejercicio anterior para las subidas y bajadas en el autobús; es decir, una lista de pares donde los primeros elementos es el número de viajeros que suben y los segundo es el de los que bajan.

Un recorrido es correcto si en cada bajada tanto el número de viajeros que suben como los que bajan son positivos, el número de viajeros en el autobús no puede ser mayor que su capacidad y el número de viajeros que bajan no puede ser mayor que el número de viajeros en el autobús. Se supone que en la primera parada el autobús no tiene viajeros.

Definir la función

recorridoCorrecto :: Int -> [(Int,Int)] -> Bool

tal que (recorridoCorrecto n ps) se verifica si ps es un recorrido correcto en un autobús cuya capacidad es n. Por ejemplo,

recorridoCorrecto 20 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  True
recorridoCorrecto 15 [(3,0),(9,1),(4,10),(12,2),(6,1)]  ==  False
recorridoCorrecto 15 [(3,2),(9,1),(4,10),(12,2),(6,1)]  ==  False
recorridoCorrecto 15 [(3,0),(2,7),(4,10),(12,2),(6,1)]  ==  False

el segundo ejemplo es incorrecto porque en la última para se supera la capacidad del autobús; el tercero, porque en la primera para no hay viajeros en el autobús que se puedan bajar y el cuarto, porque en la 2ª parada el autobús tiene 3 viajeros por lo que es imposible que se bajen 7.

Leer más…

Número de viajeros en el autobús

Misceláneas

Un autobús inicia su recorrido con 0 viajeros. El número de viajeros que se suben y bajan en cada parada se representa por un par (x,y) donde x es el número de las que suben e y el de las que bajan. Un recorrido del autobús se representa por una lista de pares representando los números de viajeros que suben o bajan en cada parada.

Definir la función

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

tal que (nViajerosEnBus ps) es el número de viajeros en el autobús tras el recorrido ps. Por ejemplo,

nViajerosEnBus []                                        ==  0
nViajerosEnBus [(10,0),(3,5),(5,8)]                      ==  5
nViajerosEnBus [(3,0),(9,1),(4,10),(12,2),(6,1),(7,10)]  ==  17
nViajerosEnBus [(3,0),(9,1),(4,8),(12,2),(6,1),(7,8)]    ==  21

Leer más…

Ordenación valle

Misceláneas

La ordenación valle de la lista [79,35,54,19,35,25,12] es la lista [79,35,25,12,19,35,54] ya que es una permutación de la primera y cumple las siguientes condiciones

  • se compone de una parte decreciente ([79,35,25]), un elemento mínimo (12) y una parte creciente ([19,35,54]);
  • las dos partes tienen el mismo número de elementos;
  • cada elemento de la primera parte es mayor o igual que su correspondiente en la segunda parte; es decir. 79 ≥ 54, 35 ≥ 35 y 25 ≥ 19;
  • además, la diferencia entre dichos elementos es la menor posible.

En el caso, de que la longitud de la lista sea par, la división tiene sólo dos partes (sin diferenciar el menor elemento). Por ejemplo, el valle de [79,35,54,19,35,25] es [79,35,25,19,35,54].

Definir la función

valle :: [Int] -> [Int]

tal que (valle xs) es la ordenación valle de la lista xs. Por ejemplo,

valle [79,35,54,19,35,25,12]       ==  [79,35,25,12,19,35,54]
valle [79,35,54,19,35,25]          ==  [79,35,25,19,35,54]
valle [67,93,100,-16,65,97,92]     ==  [100,93,67,-16,65,92,97]
valle [14,14,14,14,7,14]           ==  [14,14,14,7,14,14]
valle [14,14,14,14,14]             ==  [14,14,14,14,14]
valle [17,17,15,14,8,7,7,5,4,4,1]  ==  [17,15,8,7,4,1,4,5,7,14,17]

En el último ejemplo se muestra cómo la última condición descarta la posibilidad de que la lista [17,17,15,14,8,1,4,4,5,7,7] también sea solución ya que aunque se cumplen se cumplen las tres primeras condiciones la diferencia entre los elementos correspondientes es mayor que en la solución; por ejemplo, 17 - 7 > 17 - 17.

Leer más…

Caminos minimales en un arbol numérico

Misceláneas

En la librería Data.Tree se definen los árboles y los bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

λ> putStrLn (drawTree (fmap show ej))
3
|
+- 5
|  |
|  `- 9
|
`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u*v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

    6
   / \
  5   3
  |   |
  4   2
 / \  |
3   2 1
|   |
2   1
|
1

Definir las siguientes funciones

mayoresDivisores :: Int -> [Int]
arbol            :: Int -> Tree Int
caminos          :: Int -> [[Int]]
caminosMinimales :: Int -> [[Int]]

tales que

  • (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,
mayoresDivisores 24  ==  [12,8,6]
mayoresDivisores 16  ==  [8,4]
mayoresDivisores 10  ==  [5]
mayoresDivisores 17  ==  []
  • (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> putStrLn (drawTree (fmap show (arbol 6)))
6
|
+- 5
|  |
|  `- 4
|     |
|     +- 3
|     |  |
|     |  `- 2
|     |     |
|     |     `- 1
|     |
|     `- 2
|        |
|        `- 1
|
`- 3
|
`- 2
|
`- 1
  • (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> caminos 6
[[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
  • (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> caminosMinimales 6
[[6,3,2,1]]
λ> caminosMinimales 17
[[17,16,4,2,1]]
λ> caminosMinimales 50
[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Leer más…

Máximo de las rotaciones restringidas

Misceláneas

Rotar un número a la iquierda significa pasar su primer dígito al final. Por ejemplo, rotando a la izquierda el 56789 se obtiene 67895.

Las rotaciones restringidas del número 56789 se obtienen como se indica a continución:

  • Se inicia con el propio número: 56789
  • El anterior se rota a la izquierda y se obtiene el 67895.
  • Del anterior se fija el primer dígito y se rota a la iquierda los otros. Se obtiene 68957.
  • Del anterior se fijan los 2 primeros dígito y se rota a la iquierda los otros. Se obtiene 68579.
  • Del anterior se fijan los 3 primeros dígito y se rota a la iquierda los otros. Se obtiene 68597.

El proceso ha terminado ya que conservando los cuatro primeros queda sólo un dígito que al girar es él mismo. Por tanto, la sucesión de las rotaciones restringidas de 56789 es

56789 -> 67895 -> 68957 -> 68579 -> 68597

y su mayor elemento es 68957.

Definir la función

maxRotaciones :: Integer -> Integer

tal que (maxRotaciones n) es el máximo de las rotaciones restringidas del número n. Por ejemplo,

maxRotaciones 56789       ==  68957
maxRotaciones 1347902468  ==  3790246814
maxRotaciones 6           ==  6
maxRotaciones 2017        ==  2017

Leer más…

Aplicación de lista de funciones a lista de elementos

Misceláneas

Definir la función

aplicaLista :: [a -> b] -> [a] -> [b]

tal que (aplicaLista fs xs) es la lista de los valores de las funciones de fs aplicadas a los correspondientes elementos de xs. Por ejemplo,

aplicaLista [(+2),(`div` 3),(*5)] [4,6,2]    ==  [6,2,10]
aplicaLista [(+2),(`div` 3),(*5)] [4,6,2,8]  ==  [6,2,10]
aplicaLista [(>2),(==3),(<5)]     [4,6,2,9]  ==  [True,False,True]

Leer más…

Mayúsculas y minúsculas alternadas

Misceláneas

Definir la función

alternadas :: String -> (String,String)

tal que (alternadas cs) es el par de cadenas (xs,ys) donde xs es la cadena obtenida escribiendo alternativamente en mayuscula o minúscula las letras de la palabra cs (que se supone que es una cadena de letras minúsculas) e ys se obtiene análogamente pero empezando en minúscula. Por ejemplo,

λ> alternadas "salamandra"
("SaLaMaNdRa","sAlAmAnDrA")
λ> alternadas "solosequenosenada"
("SoLoSeQuEnOsEnAdA","sOlOsEqUeNoSeNaDa")
λ> alternadas (replicate 30 'a')
("AaAaAaAaAaAaAaAaAaAaAaAaAaAaAa","aAaAaAaAaAaAaAaAaAaAaAaAaAaAaA")

Leer más…

Conjunto de funciones entre dos conjuntos

Misceláneas

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

  • [(1,2),(3,6)] es una función de [1,3] en [2,4,6];
  • [(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
  • [(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir las funciones

funciones  :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]
nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer

tales que

  • (funciones xs ys) es el conjunto de las funciones del conjunto xs en el conjunto ys. Por ejemplo,
λ> funciones [1] [2]
[[(1,2)]]
λ> funciones [1] [2,4]
[[(1,2)],[(1,4)]]
λ> funciones [1,3] [2]
[[(1,2),(3,2)]]
λ> funciones [1,3] [2,4]
[[(1,2),(3,2)],[(1,2),(3,4)],[(1,4),(3,2)],[(1,4),(3,4)]]
λ> funciones [1,3] [2,4,6]
[[(1,2),(3,2)],[(1,2),(3,4)],[(1,2),(3,6)],
[(1,4),(3,2)],[(1,4),(3,4)],[(1,4),(3,6)],
[(1,6),(3,2)],[(1,6),(3,4)],[(1,6),(3,6)]]
λ> funciones [1,3,5] [2,4]
[[(1,2),(3,2),(5,2)],[(1,2),(3,2),(5,4)],[(1,2),(3,4),(5,2)],
[(1,2),(3,4),(5,4)],[(1,4),(3,2),(5,2)],[(1,4),(3,2),(5,4)],
[(1,4),(3,4),(5,2)],[(1,4),(3,4),(5,4)]]
λ> funciones [] []
[[]]
λ> funciones [] [2]
[[]]
λ> funciones [1] []
[]
  • (nFunciones xs ys) es el número de funciones del conjunto xs en el conjunto ys. Por ejemplo,
nFunciones [1,3] [2,4,6]  ==  9
nFunciones [1,3,5] [2,4]  ==  8
length (show (nFunciones2 [1..10^6] [1..10^3]))  ==  3000001

Leer más…

Expresiones equilibradas

Misceláneas

Una cadena de paréntesis abiertos y cerrados está equilibrada si a cada paréntesis abierto le corresponde uno cerrado y los restantes están equilibrados. Por ejemplo, "(()())" está equilibrada, pero "())(()" no lo está.

Definir la función

equilibrada :: String -> Bool

tal que (equilibrada cs) se verifica si la cadena cs está equilibrada. Por ejemplo,

equilibrada "(()())"          ==  True
equilibrada "())(()"          ==  False
equilibrada "()"              ==  True
equilibrada ")(()))"          ==  False
equilibrada "("               ==  False
equilibrada "(())((()())())"  == True

Leer más…

Reconocimiento de relaciones funcionales entre dos conjuntos

Misceláneas

Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Una relación R entre A y B es funcional si cada elemento de A está relacionado mediante R como máximo con un elemento de B. Por ejemplo, [(2,4),(1,5),(3,4)] es funcional, pero [(3,4),(1,4),(1,2),(3,4)] no lo es.

Definir la función

esFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool

tal que (esFuncional r) r se verifica si la relación r es funcional. Por ejemplo,

esFuncional [(2,4),(1,5),(3,4)]        ==  True
esFuncional [(3,4),(1,4),(1,2),(3,4)]  ==  False

Leer más…

Menor x tal que los x múltiplos de n contienen todos los dígitos

Misceláneas

Definir la función

menorX :: Integer -> Integer

tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, ... y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que

92                                    contiene  [2,9]
92 y 92×2                             contienen [1,2,4,8,9]
92,  92×2 y 92×3                      contienen [1,2,4,6,7,8,9]
92,  92×2,  92×3 y 92×4               contienen [1,2,3,4,6,7,8,9]
92,  92×2,  92×3,  92×4 y 92×5        contienen [0,1,2,3,4,6,7,8,9]
92,  92×2,  92×3,  92×4,  92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

Otros ejemplos

menorX 92          ==  6
menorX 2967        ==  3
menorX 266         ==  4
menorX 18          ==  5
menorX 2           ==  45
menorX 125         ==  72
menorX 1234567890  ==  1
maximum [menorX n | n <- [1..3000]]  ==  72
minimum [menorX n | n <- [1..3000]]  ==  3

Leer más…

Conjunto de relaciones binarias entre dos conjuntos

Misceláneas

Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Definir las funciones

relaciones  :: [a] -> [b] -> [[(a,b)]]
nRelaciones :: [a] -> [b] -> Integer

tales que

  • (relaciones xs ys) es el conjunto de las relaciones del conjunto xs en el conjunto ys. Por ejemplo,
λ> relaciones [1] [2]
[[],[(1,2)]]
λ> relaciones [1] [2,4]
[[],[(1,2)],[(1,4)],[(1,2),(1,4)]]
λ> relaciones [1,3] [2]
[[],[(1,2)],[(3,2)],[(1,2),(3,2)]]
λ> relaciones [1,3] [2,4]
[[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)],
 [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)],
 [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)],
 [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)],
 [(1,2),(1,4),(3,2),(3,4)]]
λ> relaciones [] []
[[]]
λ> relaciones [] [2]
[[]]
λ> relaciones [1] []
[[]]
  • (nRelaciones xs ys) es el número de relaciones del conjunto xs en el conjunto ys. Por ejemplo,
nRelaciones [1,2] [4,5]    ==  16
nRelaciones [1,2] [4,5,6]  ==  64
nRelaciones [0..9] [0..9]  ==  1267650600228229401496703205376

Leer más…

Sumas de dos cuadrados

Misceláneas

Definir la función

sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]

tal que (sumasDe2Cuadrados n) es la lista de los pares de números tales que la suma de sus cuadrados es n y el primer elemento del par es mayor o igual que el segundo. Por ejemplo,

sumasDe2Cuadrados 25                ==  [(5,0),(4,3)]
sumasDe2Cuadrados 32                ==  [(4,4)]
sumasDe2Cuadrados 55                ==  []
sumasDe2Cuadrados 850               ==  [(29,3),(27,11),(25,15)]
length (sumasDe2Cuadrados (10^12))  ==  7

Leer más…

Mayor producto de las ramas de un árbol

Misceláneas

Los árboles se pueden representar mediante el siguiente tipo de datos

data Arbol a = N a [Arbol a]
               deriving Show

Por ejemplo, los árboles

   1              3
 /  \            /|\
2   3           / | \
    |          5  4  7
    4          |     /\
               6    2  1

se representan por

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [],N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]

Definir la función

mayorProducto :: (Ord a, Num a) => Arbol a -> a

tal que (mayorProducto a) es el mayor producto de las ramas del árbol a. Por ejemplo,

λ> mayorProducto (N 1 [N 2 [], N  3 []])
3
λ> mayorProducto (N 1 [N 8 [], N  4 [N 3 []]])
12
λ> mayorProducto (N 1 [N 2 [],N 3 [N 4 []]])
12
λ> mayorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
90
λ> mayorProducto (N (-8) [N 0 [N (-9) []],N 6 []])
0
λ> a = N (-4) [N (-7) [],N 14 [N 19 []],N (-1) [N (-6) [],N 21 []],N (-4) []]
λ> mayorProducto a
84

Leer más…

Sucesión contadora

Misceláneas

Definir las siguientes funciones

numeroContado           :: Integer -> Integer
contadora               :: Integer -> [Integer]
lugarPuntoFijoContadora :: Integer -> Integer -> Maybe Integer

tales que

  • (numeroContado n) es el número obtenido al contar las repeticiones de cada una de las cifras de n. Por ejemplo,
numeroContado 1                 == 11
numeroContado 114213            == 31121314
numeroContado 1111111111111111  == 161
  • (contadora n) es la sucesión cuyo primer elemento es n y los restantes se obtienen contando el número anterior de la sucesión. Por ejemplo,
λ> take 14 (contadora 1)
[1,11,21,1112,3112,211213,312213,212223,114213,31121314,41122314,
31221324,21322314,21322314]
λ> take 14 (contadora 5)
[5,15,1115,3115,211315,31121315,41122315,3122131415,4122231415,
3132132415,3122331415,3122331415,3122331415,3122331415]
  • (lugarPuntoFijoContadora n k) es el menor i <= k tal que son iguales los elementos en las posiciones i e i+1 de la sucesión contadora que cominza con n. Por ejemplo,
λ> lugarPuntoFijoContadora 1 100
Just 12
λ> contadora 1 !! 11
31221324
λ> contadora 1 !! 12
21322314
λ> contadora 1 !! 13
21322314
λ> lugarPuntoFijoContadora 1 10
Nothing
λ> lugarPuntoFijoContadora 5 20
Just 10
λ> lugarPuntoFijoContadora 40 200
Nothing

Nota: Este ejercicio ha sido propuesto por Ángel Ruiz.

Leer más…

Punto de inflexión

Misceláneas

Definir la función

inflexion :: Ord a => [a] -> Maybe a

tal que (inflexion xs) es el primer elemento de la lista en donde se cambia de creciente a decreciente o de decreciente a creciente y Nothing si no se cambia. Por ejemplo,

inflexion [2,2,3,5,4,6]    ==  Just 4
inflexion [9,8,6,7,10,10]  ==  Just 7
inflexion [2,2,3,5]        ==  Nothing
inflexion [5,3,2,2]        ==  Nothing

Leer más…

Número de divisores

Misceláneas

Definir la función

numeroDivisores :: Integer -> Integer

tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,

numeroDivisores 12  ==  6
numeroDivisores 25  ==  3
length (show (numeroDivisores (product (take 20000 primes)))) == 6021

Leer más…

Cadenas de sumas de factoriales de los dígitos

Misceláneas

Dado un número n se considera la sucesión cuyo primer término es n y los restantes se obtienen sumando los factoriales de los dígitos del anterior. Por ejemplo, la sucesión que empieza en 69 es

    69
363600  (porque 6! + 9! = 363600)
  1454  (porque 3! + 6! + 3! + 6! + 0! + 0! = 1454)
   169  (porque 1! + 4! + 5! + 4! = 169)
363601  (porque 1! + 6! + 9! = 363601)
  1454  (porque 3! + 6! + 3! + 6! + 0! + 1! = 1454)
......

La cadena correspondiente a un número n son los términos de la sucesión que empieza en n hasta la primera repetición de un elemento en la sucesión. Por ejemplo, la cadena de 69 es

[69,363600,1454,169,363601,1454]

Consta de una parte no periódica ([69,363600]) y de una periódica ([1454,169,363601]).

Definir las funciones

cadena  :: Integer -> [Integer]
periodo :: Integer -> [Integer]

tales que

  • (cadena n es la cadena correspondiente al número n. Por ejemplo,
cadena 69    ==  [69,363600,1454,169,363601,1454]
cadena 145   ==  [145,145]
cadena 78    ==  [78,45360,871,45361,871]
cadena 569   ==  [569,363720,5775,10320,11,2,2]
cadena 3888  ==  [3888,120966,364324,782,45362,872,45362]
maximum [length (cadena n) | n <- [1..5000]]  ==  61
length (cadena 1479)                          ==  61
  • (periodo n) es la parte periódica de la cadena de n. Por ejemplo,
periodo 69    ==  [169,363601,1454]
periodo 145   ==  [145]
periodo 78    ==  [45361,871]
periodo 569   ==  [2]
periodo 3888  ==  [872,45362]
maximum [length (periodo n) | n <- [1..5000]]  ==  3
length (periodo 1479)                          ==  3

Leer más…

Suma de divisores

Misceláneas

Definir las funciones

divisores     :: Integer -> [Integer]
sumaDivisores :: Integer -> Integer

tales que

  • (divisores x) es la lista de los divisores de x. Por ejemplo,
divisores 12  ==  [1,2,3,4,6,12]
divisores 25  ==  [1,5,25]
length (divisores (product [1..12]))  ==  792
length (divisores 131535436245601)    ==  32
  • (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
sumaDivisores 12  ==  28
sumaDivisores 25  ==  31
sumaDivisores (product [1..12])  ==  2217441408
sumaDivisores 131535436245601    ==  132534784471040

Leer más…

Números dígito potenciales

Misceláneas

Un número entero x es dígito potencial de orden n si x es la suma de los dígitos de x elevados a n. Por ejemplo,

  • 153 es un dígito potencial de orden 3 ya que 153 = 1^3+5^3+3^3
  • 4150 es un dígito potencial de orden 5 ya que 4150 = 4^5+1^5+5^5+0^5

Un número x es dígito auto potencial si es un dígito potencial de orden n, donde n es el número de dígitos de n. Por ejemplo, 153 es un número dígito auto potencial.

Definir las funciones

digitosPotencialesOrden :: Integer -> [Integer]
digitosAutoPotenciales  :: [Integer]

tales que

  • (digitosPotencialesOrden n) es la lista de los números dígito potenciales de orden n. Por ejemplo,
take 6 (digitosPotencialesOrden 3)  ==  [0,1,153,370,371,407]
take 5 (digitosPotencialesOrden 4)  ==  [0,1,1634,8208,9474]
take 8 (digitosPotencialesOrden 5)  ==  [0,1,4150,4151,54748,92727,93084,194979]
take 3 (digitosPotencialesOrden 6)  ==  [0,1,548834]
  • digitosAutoPotenciales es la lista de los números dígito auto potenciales. Por ejemplo,
λ> take 20 digitosAutoPotenciales
[0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

Leer más…

Mayor número equidigital

Misceláneas

Definir la función

mayorEquidigital :: Integer -> Integer

tal que (mayorEquidigital x) es el mayor número que se puede contruir con los dígitos de x. Por ejemplo,

mayorEquidigital 13112017  ==  73211110
mayorEquidigital2 (2^100)  ==  9987776666655443322222211000000

Leer más…

Números oblongos

Misceláneas

Un número oblongo es un número que es el producto de dos números naturales consecutivos; es decir, n es un número oblongo si existe un número natural x tal que n = x(x+1). Por ejemplo, 42 es un número oblongo porque 42 = 6 x 7.

Definir las funciones

esOblongo :: Integer -> Bool
oblongos  :: [Integer]

tales que

  • (esOblongo n) se verifica si n es oblongo. Por ejemplo,
esOblongo 42               ==  True
esOblongo 40               ==  False
esOblongo 100000010000000  ==  True
  • oblongos es la suceción de los números oblongos. Por ejemplo,
take 15 oblongos   == [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210]
oblongos !! 50     == 2550
oblongos !! (10^7) == 100000010000000

Leer más…

Pares definidos por su MCD y su MCM

Misceláneas

Definir las siguientes funciones

pares  :: Integer -> Integer -> [(Integer,Integer)]
nPares :: Integer -> Integer -> Integer

tales que

  • (pares a b) es la lista de los pares de números enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,
pares 3 3  == [(3,3)]
pares 4 12 == [(4,12),(12,4)]
pares 2 12 == [(2,12),(4,6),(6,4),(12,2)]
pares 2 60 == [(2,60),(4,30),(6,20),(10,12),(12,10),(20,6),(30,4),(60,2)]
pares 2 7  == []
pares 12 3 == []
length (pares 3 (product [3,5..91]))  ==  8388608
  • (nPares a b) es el número de pares de enteros positivos tales que su máximo común divisor es a y su mínimo común múltiplo es b. Por ejemplo,
nPares 3 3   ==  1
nPares 4 12  ==  2
nPares 2 12  ==  4
nPares 2 60  ==  8
nPares 2 7   ==  0
nPares 12 3  ==  0
nPares 3 (product [3..3*10^4]) `mod` (10^12)  ==  477999992832
length (show (nPares 3 (product [3..3*10^4])))  ==  977

Leer más…

Biparticiones de un número

Misceláneas

Definir la función

biparticiones :: Integer -> [(Integer,Integer)]

tal que (biparticiones n) es la lista de pares de números formados por las primeras cifras de n y las restantes. Por ejemplo,

biparticiones  2025  ==  [(202,5),(20,25),(2,25)]
biparticiones 10000  ==  [(1000,0),(100,0),(10,0),(1,0)]

Leer más…

Producto cartesiano de una familia de conjuntos

Misceláneas

Definir la función

producto :: [[a]] -> [[a]]

tal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,

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

Comprobar con QuickCheck que para toda lista de listas de números enteros, xss, se verifica que el número de elementos de (producto xss) es igual al producto de los números de elementos de cada una de las listas de xss.

Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación

quickCheckWith (stdArgs {maxSize=9}) prop_producto

Leer más…

Primos equidistantes

Misceláneas

Definir la función

primosEquidistantes :: Integer -> [(Integer,Integer)]

tal que (primosEquidistantes k) es la lista de los pares de primos consecutivos cuya diferencia es k. Por ejemplo,

take 3 (primosEquidistantes 2)     ==  [(3,5),(5,7),(11,13)]
take 3 (primosEquidistantes 4)     ==  [(7,11),(13,17),(19,23)]
take 3 (primosEquidistantes 6)     ==  [(23,29),(31,37),(47,53)]
take 3 (primosEquidistantes 8)     ==  [(89,97),(359,367),(389,397)]
(primosEquidistantes 30) !! 14000  ==  (6557303,6557333)

Leer más…

Números completos

Misceláneas

Las descomposiciones de un número n son las parejas de números (x,y) tales que x >= y y la suma de las cuatro operaciones básicas (suma, producto, resta (el mayor menos el menor) y cociente (el mayor entre el menor)) es el número n. Por ejemplo, (8,2) es una descomposición de 36 ya que

(8 + 2) + (8 - 2) + (8 * 2) + (8 / 2) = 36

Un número es completo si tiene alguna descomposición como las anteriores. Por ejemplo, el 36 es completo pero el 21 no lo es.

Definir las siguientes funciones

descomposiciones :: Integer -> [(Integer,Integer)]
completos        :: [Integer]

tales que

  • (descomposiciones n) es la lista de las descomposiones de n. Por ejemplo,
descomposiciones 12   ==  [(3,1)]
descomposiciones 16   ==  [(3,3),(4,1)]
descomposiciones 36   ==  [(5,5),(8,2),(9,1)]
descomposiciones 288  ==  [(22,11),(40,5),(54,3),(64,2),(72,1)]
descomposiciones 21   ==  []
  • completos es la lista de los números completos. Por ejemplo,
take 15 completos  ==  [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44]
completos !! 100   ==  261

Leer más…

Números libres de cuadrados

Misceláneas

Un número entero positivo es libre de cuadrados si no es divisible el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

libreDeCuadrados :: Integer -> Bool

tal que (libreDeCuadrados x) se verifica si x es libre de cuadrados. Por ejemplo,

libreDeCuadrados 70                    ==  True
libreDeCuadrados 40                    ==  False
libreDeCuadrados 510510                ==  True
libreDeCuadrados (((10^10)^10)^10)     ==  False

Otro ejemplo,

λ> filter (not . libreDeCuadrados) [1..50]
[4,8,9,12,16,18,20,24,25,27,28,32,36,40,44,45,48,49,50]

Leer más…

Ancestro común más bajo

Misceláneas

El tipo de los árboles binarios se define por

data Arbol = H Int
           | N Int Arbol Arbol

Por ejemplo, el árbol

     5
    / \
   /   \
  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))

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

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

Leer más…

La regla de los signos de Descartes

Misceláneas

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]

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)]
  • (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]

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

Leer más…

Valores de polinomios y de expresiones

Misceláneas

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

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

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

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
  • (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))))
  • (valorP p n) es el valor del polinomio p cuando se sustituye su variable por n. Por ejemplo,
λ> 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

Leer más…

Suma de los cuadrados de los divisores

Misceláneas

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

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

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

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.

Leer más…

Mayores sublistas crecientes

Misceláneas

Definir las funciones

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
  • (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

Leer más…

Sin ceros consecutivos

Misceláneas

Definir la función

sinDobleCero :: Int -> [[Int]]

tal que (sinDobleCero n) es la lista de las listas de longitud n formadas por el 0 y el 1 tales que no contiene dos ceros consecutivos. Por ejemplo,

λ> sinDobleCero 2
[[1,0],[1,1],[0,1]]
λ> sinDobleCero 3
[[1,1,0],[1,1,1],[1,0,1],[0,1,0],[0,1,1]]
λ> sinDobleCero 4
[[1,1,1,0],[1,1,1,1],[1,1,0,1],[1,0,1,0],[1,0,1,1],
 [0,1,1,0],[0,1,1,1],[0,1,0,1]]

Leer más…

Extremos locales

Misceláneas

Un mínimo local de una lista es un elemento de la lista que es menor que su predecesor y que su sucesor en la lista. Por ejemplo, 1 es un mínimo local de [8,2,1,3,7,6,4,0,5] ya que es menor que 2 (su predecesor) y que 3 (su sucesor).

Análogamente se definen los máximos locales. Por ejemplo, 7 es un máximo local de [8,2,1,3,7,6,4,0,5] ya que es mayor que 7 (su predecesor) y que 6 (su sucesor).

Los extremos locales están formados por los mínimos y máximos locales. Por ejemplo, los extremos locales de [8,2,1,3,7,6,4,0,5] son el 1, el 7 y el 0.

Definir la función

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

tal que (extremos xs) es la lista de los extremos locales de la lista xs. Por ejemplo,

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

Leer más…

Subexpresiones aritméticas

Misceláneas

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

data Expr = N Int | S Expr Expr | P Expr Expr
  deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

P (N 2) (S (N 3) (N 7))

Definir la función

subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

λ> subexpresiones (S (N 2) (N 3))
fromList [N 2,N 3,S (N 2) (N 3)]
λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Leer más…

Representaciones de grafos

Misceláneas

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo

1 ----- 2
| \     |
|  3    |
| /     |
4 ----- 5

se puede representar por la matriz de adyacencia

|0 1 1 1 0|
|1 0 0 0 1|
|1 0 0 1 0|
|1 0 1 0 1|
|0 1 0 1 0|

donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia

[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.

Definir las funciones

matrizAlista :: Matrix Int -> [(Int,[Int])]
listaAmatriz :: [(Int,[Int])] -> Matrix Int

tales que

  • (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por
ejMatriz :: Matrix Int
ejMatriz = fromLists [[0,1,1,1,0],
[1,0,0,0,1],
[1,0,0,1,0],
[1,0,1,0,1],
[0,1,0,1,0]]

se tiene que

λ> matrizAlista ejMatriz
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
  • (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,
λ> listaAmatriz [(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]
( 0 1 1 1 0 )
( 1 0 0 0 1 )
( 1 0 0 1 0 )
( 1 0 1 0 1 )
( 0 1 0 1 0 )
λ> matrizAlista it
[(1,[2,3,4]),(2,[1,5]),(3,[1,4]),(4,[1,3,5]),(5,[2,4])]

Leer más…

Polinomios de Fibonacci

Misceláneas

La sucesión de polinomios de Fibonacci se define por

p(0) = 0
p(1) = 1
p(n) = x*p(n-1) + p(n-2)

Los primeros términos de la sucesión son

p(2) = x
p(3) = x^2 + 1
p(4) = x^3 + 2*x
p(5) = x^4 + 3*x^2 + 1

Definir la lista

sucPolFib :: [Polinomio Integer]

tal que sus elementos son los polinomios de Fibonacci. Por ejemplo,

λ> take 7 sucPolFib
[0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]
λ> sum (map grado (take 3000 sucPolFib2))
4495501

Comprobar con QuickCheck que el valor del n-ésimo término de sucPolFib para x=1 es el n-ésimo término de la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, ...

Nota. Limitar la búsqueda a ejemplos pequeños usando

quickCheckWith (stdArgs {maxSize=5}) prop_polFib

Leer más…

El pasatiempo de Ulises

Misceláneas

Ulises, en sus ratos libres, juega a un pasatiempo que consiste en, dada una serie de números naturales positivos en una cola, sacar un elemento y, si es distinto de 1, volver a meter el mayor de sus divisores propios. Si el número que saca es el 1, entonces lo deja fuera y no mete ningún otro. El pasatiempo continúa hasta que la cola queda vacía.

Por ejemplo, a partir de una cola con los números 10, 20 y 30, el pasatiempo se desarrollaría como sigue:

C [30,20,10]
C [20,10,15]
C [10,15,10]
C [15,10,5]
C [10,5,5]
C [5,5,5]
C [5,5,1]
C [5,1,1]
C [1,1,1]
C [1,1]
C [1]
C []

Definir la función

numeroPasos :: Cola Int -> Int

tal que (numeroPasos c) es el número de veces que Ulises saca algún número de la cola c al utilizarla en su pasatiempo. Por ejemplo,

numeroPasos (foldr inserta vacia [30])        ==  4
numeroPasos (foldr inserta vacia [20])        ==  4
numeroPasos (foldr inserta vacia [10])        ==  3
numeroPasos (foldr inserta vacia [10,20,30])  ==  11

Leer más…

Caminos reducidos

Misceláneas

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

data Direccion = N | S | E | O deriving (Show, Eq)
type Camino = [Direccion]

Definir la función

reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

reducido []                              ==  []
reducido [N]                             ==  [N]
reducido [N,O]                           ==  [N,O]
reducido [N,O,E]                         ==  [N]
reducido [N,O,E,S]                       ==  []
reducido [N,O,S,E]                       ==  [N,O,S,E]
reducido [S,S,S,N,N,N]                   ==  []
reducido [N,S,S,E,O,N]                   ==  []
reducido [N,S,S,E,O,N,O]                 ==  [O]
reducido (take (10^7) (cycle [N,E,O,S])) ==  []

Nótese que en el penúltimo ejemplo las reducciones son

    [N,S,S,E,O,N,O]
--> [S,E,O,N,O]
--> [S,N,O]
--> [O]

Leer más…

Descomposiciones de N como sumas de 1, 3 ó 4.

Misceláneas

El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:

5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 3
5 = 1 + 3 + 1
5 = 3 + 1 + 1
5 = 1 + 4
5 = 4 + 1

Definir las funciones

descomposiciones  :: Integer -> [[Integer]]
nDescomposiciones :: Integer -> Integer

tales que

  • (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
λ> descomposiciones1 4
[[4],[3,1],[1,3],[1,1,1,1]]
λ> descomposiciones1 5
[[4,1],[1,4],[3,1,1],[1,3,1],[1,1,3],[1,1,1,1,1]]
λ> descomposiciones1 6
[[3,3],[4,1,1],[1,4,1],[1,1,4],[3,1,1,1],[1,3,1,1],[1,1,3,1],
[1,1,1,3],[1,1,1,1,1,1]]
  • (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
nDescomposiciones 5                       ==  6
nDescomposiciones 10                      ==  64
nDescomposiciones 20                      ==  7921
nDescomposiciones 30                      ==  974169
length (show (nDescomposiciones (10^5)))  ==  20899

Nota: Se puede usar programación dinámica.

Leer más…

Caminos en un grafo

Misceláneas

Definir las funciones

grafo   :: [(Int,Int)] -> Grafo Int Int
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

  • (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,
λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])
  • (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo).

Leer más…

Problema del dominó

Misceláneas

Las fichas del dominó se pueden representar por pares de números enteros. El problema del dominó consiste en colocar todas las fichas de una lista dada de forma que el segundo número de cada ficha coincida con el primero de la siguiente.

Definir la función

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

tal que (domino fs) es la lista de las soluciones del problema del dominó correspondiente a las fichas fs. Por ejemplo,

λ> domino [(1,2),(2,3),(1,4)]
[[(4,1),(1,2),(2,3)],[(3,2),(2,1),(1,4)]]
λ> domino [(1,2),(1,1),(1,4)]
[[(4,1),(1,1),(1,2)],[(2,1),(1,1),(1,4)]]
λ> domino [(1,2),(3,4),(2,3)]
[[(1,2),(2,3),(3,4)]]
λ> domino [(1,2),(2,3),(5,4)]
[]
λ> domino [(x,y) | x <- [1..2], y <- [x..2]]
[[(2,2),(2,1),(1,1)],[(1,1),(1,2),(2,2)]]
λ> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
λ> mapM_ print (domino [(x,y) | x <- [1..3], y <- [x..3]])
[(1,3),(3,3),(3,2),(2,2),(2,1),(1,1)]
[(1,2),(2,2),(2,3),(3,3),(3,1),(1,1)]
[(2,2),(2,3),(3,3),(3,1),(1,1),(1,2)]
[(3,3),(3,2),(2,2),(2,1),(1,1),(1,3)]
[(2,3),(3,3),(3,1),(1,1),(1,2),(2,2)]
[(2,1),(1,1),(1,3),(3,3),(3,2),(2,2)]
[(3,3),(3,1),(1,1),(1,2),(2,2),(2,3)]
[(3,2),(2,2),(2,1),(1,1),(1,3),(3,3)]
[(3,1),(1,1),(1,2),(2,2),(2,3),(3,3)]
λ> length (domino [(x,y) | x <- [1..3], y <- [x..3]])
9
λ> length (domino [(x,y) | x <- [1..4], y <- [x..4]])
0
λ> length (domino [(x,y) | x <- [1..5], y <- [x..5]])
84480

Leer más…

El algoritmo de Damm

Misceláneas

El algoritmo de Damm se usa en la detección de errores en códigos numéricos. Es un procedimiento para obtener un dígito de control, usando la siguiente matriz, como describimos en los ejemplos

  |  0   1   2   3   4   5   6   7   8   9
--+---------------------------------------
0 |  0   3   1   7   5   9   8   6   4   2
1 |  7   0   9   2   1   5   4   8   6   3
2 |  4   2   0   6   8   7   1   3   5   9
3 |  1   7   5   0   9   8   3   4   2   6
4 |  6   1   2   3   0   4   5   9   7   8
5 |  3   6   7   4   2   0   9   5   8   1
6 |  5   8   6   9   7   2   0   1   3   4
7 |  8   9   4   5   3   6   2   0   1   7
8 |  9   4   3   8   6   1   7   2   0   5
9 |  2   5   8   1   4   3   6   7   9   0

Ejemplo 1: cálculo del dígito de control de 572

  • se comienza con la fila 0 y columna 5 de la matriz -> 9
  • a continuación, la fila 9 y columna 7 de la matriz -> 7
  • a continuación, la fila 7 y columna 2 de la matriz -> 4

con lo que se llega al final del proceso. Entonces, el dígito de control de 572 es 4.

Ejemplo 2: cálculo del dígito de control de 57260

  • se comienza con la fila 0 y columna 5 de la matriz -> 9
  • a continuación, la fila 9 y columna 7 de la matriz -> 7
  • a continuación, la fila 9 y columna 2 de la matriz -> 4
  • a continuación, la fila 6 y columna 4 de la matriz -> 5
  • a continuación, la fila 5 y columna 0 de la matriz -> 3

con lo que se llega al final del proceso. Entonces, el dígito de control de 57260 es 3.

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

type Matriz a = Array (Int,Int) a

Definimos la matriz:

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

Definir la función

digitoControl :: Int -> Int

tal que (digitoControl n) es el dígito de control de n. Por ejemplo:

digitoControl 572          == 4
digitoControl 57260        == 3
digitoControl 12345689012  == 6
digitoControl 5724         == 0
digitoControl 572603       == 0
digitoControl 123456890126 == 0

Comprobar con QuickCheck que si añadimos al final de un número n su dígito de control, el dígito de control del número que resulta siempre es 0.

Leer más…

El problema de la bicicleta de Turing

Misceláneas

Cuentan que Alan Turing tenía una bicicleta vieja, que tenía una cadena con un eslabón débil y además uno de los radios de la rueda estaba doblado. Cuando el radio doblado coincidía con el eslabón débil, entonces la cadena se rompía.

La bicicleta se identifica por los parámetros (i,d,n) donde

  • i es el número del eslabón que coincide con el radio doblado al empezar a andar,
  • d es el número de eslabones que se desplaza la cadena en cada vuelta de la rueda y
  • n es el número de eslabones de la cadena (el número n es el débil).

Si i = 2, d = 7 y n = 25, entonces la lista con el número de eslabón que toca el radio doblado en cada vuelta es

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

Con lo que la cadena se rompe en la vuelta número 14.

Definir las funciones

eslabones :: Int -> Int -> Int -> [Int]
numeroVueltas :: Int -> Int -> Int -> Int

tales que

  • (eslabones i d n) es la lista con los números de eslabones que tocan el radio doblado en cada vuelta en una bicicleta de tipo (i,d,n). Por ejemplo,
take 10 (eslabones 2 7 25)  ==  [2,9,16,23,5,12,19,1,8,15]
  • (numeroVueltas i d n) es el número de vueltas que pasarán hasta que la cadena se rompa en una bicicleta de tipo (i,d,n). Por ejemplo,
numeroVueltas 2 7 25  ==  14

Leer más…

Grafo de divisibilidad

Misceláneas

El grafo de divisibilidad de orden n es el grafo cuyos nodos son los números naturales entre 1 y n, cuyas aristas son los pares (x,y) tales que x divide a y o y divide a x y el coste de cada arista es el cociente entre su mayos y menor elemento.

Definir las siguientes funciones:

grafoDivisibilidad :: Int -> Grafo Int Int
coste :: Int -> Int

tales que

  • (grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,
λ> grafoDivisibilidad 12
G ND (array (1,12)
            [(1,[(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),
                 (8,8),(9,9),(10,10),(11,11),(12,12)]),
             (2,[(1,2),(4,2),(6,3),(8,4),(10,5),(12,6)]),
             (3,[(1,3),(6,2),(9,3),(12,4)]),
             (4,[(1,4),(2,2),(8,2),(12,3)]),
             (5,[(1,5),(10,2)]),
             (6,[(1,6),(2,3),(3,2),(12,2)]),
             (7,[(1,7)]),
             (8,[(1,8),(2,4),(4,2)]),
             (9,[(1,9),(3,3)]),
             (10,[(1,10),(2,5),(5,2)]),
             (11,[(1,11)]),
             (12,[(1,12),(2,6),(3,4),(4,3),(6,2)])])
  • (coste n) es el coste del árbol de expansión mínimo del grafo de divisibilidad de orden n. Por ejemplo,
coste 12    ==  41
coste 3000  ==  605305

Leer más…

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…