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…

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…

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…

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…

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…

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

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…

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…

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…

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

y (graficaComplementoPotencial 500) dibuja

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

Leer más…

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

Leer más…

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

Leer más…

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…

Escribir, usando CodeWorld, un programa para dibujar el fractal hexagonal que se muestra en la siguiente animación

Las 5 fases de la animación son

• Fase 0:
• Fase 1:
• Fase 2:
• Fase 3:
• Fase 4:

Leer más…

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…

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…

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…

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…

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…

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

y (grafica 30000) dibuja

Leer más…

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…

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

Leer más…

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 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…

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…

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…

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…

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…

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

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

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

Leer más…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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]]