Extremos locales

José A. Alonso

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]

Subexpresiones aritméticas

José A. Alonso

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

Representaciones de grafos

José A. Alonso

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

Polinomios de Fibonacci

José A. Alonso

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

El pasatiempo de Ulises

José A. Alonso

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

Caminos reducidos

José A. Alonso

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]

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

José A. Alonso

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.

Caminos en un grafo

José A. Alonso

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).

Problema del dominó

José A. Alonso

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

El algoritmo de Damm

José A. Alonso

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.

El problema de la bicicleta de Turing

José A. Alonso

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

Grafo de divisibilidad

José A. Alonso

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

Grafo complemenario

José A. Alonso

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.

El problema de las celebridades

José A. Alonso

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

Pares a distancia dada

José A. Alonso

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

Problema de las 3 jarras

José A. Alonso

Misceláneas

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

Definir las funciones

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

tales que

(solucionesTresJarras p) es la lista de soluciones del problema de las tres jarras p. Por ejemplo,

λ> mapM_ print (solucionesTresJarras (4,2,1))
[(4,0,0),(2,2,0)]
[(4,0,0),(3,0,1),(1,2,1),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(2,2,0)]
[(4,0,0),(3,0,1),(3,1,0),(2,1,1),(1,2,1),(2,2,0)]
λ> mapM_ print (solucionesTresJarras (8,6,2))
[(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(6,0,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(2,6,0),(2,4,2),(4,4,0)]
[(8,0,0),(2,6,0),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(2,6,0),(2,4,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(2,6,0),(2,4,2),(0,6,2),(6,0,2),(6,2,0),(4,2,2),(4,4,0)]
[(8,0,0),(6,0,2),(6,2,0),(4,2,2),(0,6,2),(2,6,0),(2,4,2),(4,4,0)]
λ> length (solucionesTresJarras (8,5,3))
16
λ> head (solucionesTresJarras (8,5,3))
[(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
λ> length (solucionesTresJarras (8,6,5))
0

(tresJarras p) es una solución del problema de las tres jarras p con el mínimo mínimo número de trasvase, si p tiene solución y Nothing, en caso contrario. Por ejemplo,

λ> tresJarras (4,2,1)
Just [(4,0,0),(2,2,0)]
λ> tresJarras (8,6,2)
Just [(8,0,0),(2,6,0),(2,4,2),(4,4,0)]
λ> tresJarras (8,5,3)
Just [(8,0,0),(3,5,0),(3,2,3),(6,2,0),(6,0,2),(1,5,2),(1,4,3),(4,4,0)]
λ> tresJarras (8,6,5)
Nothing

Suma de árboles por niveles

José A. Alonso

Misceláneas

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

data Arbol = H
           | N a Arbol Arbol

Por ejemplo, los árboles

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

se representan por

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

Definir la función

suma :: Arbol -> Int

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

suma ej1  ==  6
suma ej2  ==  4

ya que

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

Normalización de expresiones aritméticas

José A. Alonso

Misceláneas

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

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

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

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

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

Definir la función

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

tales que

(esTermino a) se verifica si a es un término. Por ejemplo,

esTermino (V "x")                         == True
esTermino (P (V "x") (P (V "y") (V "z"))) == True
esTermino (P (V "x") (S (V "y") (V "z"))) == False
esTermino (S (V "x") (P (V "y") (V "z"))) == False

(esNormal a) se verifica si a está en forma normal. Por ejemplo,

esNormal (V "x")                                     == True
esNormal (P (V "x") (P (V "y") (V "z")))             == True
esNormal (S (V "x") (P (V "y") (V "z")))             == True
esNormal (P (V "x") (S (V "y") (V "z")))             == False
esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False
esNormal (S (P (V "x") (V "y")) (S (V "z") (V "x"))) == True

(normal e) es la forma normal de la expresión e obtenida aplicando, mientras que sea posible, las propiedades distributivas:

(a+b)*c = a*c+b*c
c*(a+b) = c*a+c*b

Por ejemplo,

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

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

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

import Test.QuickCheck
import Control.Monad

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

Recorrido en ZigZag

José A. Alonso

Misceláneas

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

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

Definir la función

recorridoZigZag :: Matrix a -> [a]

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

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

Sucesión de Recamán

José A. Alonso

Misceláneas

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

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

Definir las funciones

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

tales que

sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,

λ> take 25 sucRecaman3
[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]
λ> sucRecaman !! 1000
3686
λ> sucRecaman !! 1000001
1057163

(invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,

invRecaman 10       ==  12
invRecaman 3686     ==  1000
invRecaman 1057163  ==  1000001

(graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja

Sucesión de Recamán

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

Sucesión de Recamán

y (graficaInvRecaman 100) dibuja

Sucesión de Recamán

Operaciones con series de potencias

José A. Alonso

Misceláneas

Una serie de potencias es una serie de la forma

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

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

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

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

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

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

type Serie a = [a]

Definir las siguientes funciones

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

tales que

(opuesta xs) es la opuesta de la serie xs. Por ejemplo,

λ> take 7 (opuesta [-6,-4..])
[6,4,2,0,-2,-4,-6]

(suma xs ys) es la suma de las series xs e ys. Por ejemplo,

λ> take 7 (suma [1,3..] [2,4..])
[3,7,11,15,19,23,27]

(resta xs ys) es la resta de las series xs es ys. Por ejemplo,

λ> take 7 (resta [3,5..] [2,4..])
[1,1,1,1,1,1,1]
λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..])
[2,4,6,8,10,12,14]

(producto xs ys) es el producto de las series xs e ys. Por ejemplo,

λ> take 7 (producto [3,5..] [2,4..])
[6,22,52,100,170,266,392]

(cociente xs ys) es el cociente de las series xs e ys. Por ejemplo,

λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..])
[2.0,4.0,6.0,8.0,10.0,12.0,14.0]

(derivada xs) es la derivada de la serie xs. Por ejemplo,

λ> take 7 (derivada [2,4..])
[4,12,24,40,60,84,112]

(integral xs) es la integral de la serie xs. Por ejemplo,

λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0))
[0.0,4.0,6.0,8.0,10.0,12.0,14.0]

expx es la serie de la función exponencial. Por ejemplo,

λ> take 8 expx
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (derivada expx)
[1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
λ> take 8 (integral expx)
[0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]

Operaciones con polinomios como diccionarios

José A. Alonso

Misceláneas

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

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

type Polinomio a = M.Map Int a

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

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

se definen por

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

Definir las funciones

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

tales que

(sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,

λ> sumaPol ejPol1 ejPol2
fromList [(0,7),(1,7),(5,1)]
λ> sumaPol ejPol1 ejPol1
fromList [(0,6),(1,14),(3,-10)]

(multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo,

λ> multPorTerm (2,3) (M.fromList [(0,4),(2,1)])
fromList [(2,12),(4,3)]

(multPol p q) es el producto de los polinomios p y q. Por ejemplo,

λ> multPol ejPol1 ejPol2
fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
λ> multPol ejPol1 ejPol1
fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
λ> multPol ejPol2 ejPol2
fromList [(0,16),(3,40),(5,8),(6,25),(8,10),(10,1)]

Números como sumas de primos consecutivos.

José A. Alonso

Misceláneas

El número 311 se puede escribir de 5 formas distintas como suma de 1 o más primos consecutivos

311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
311 =  53 +  59 +  61 + 67 + 71
311 = 101 + 103 + 107
311 = 311

el número 41 se puede escribir de 4 formas

41 =  2 +  3 +  5 + 7 + 11 + 13
41 = 11 + 13 + 17
41 = 41

y el número 14 no se puede escribir como suma de primos consecutivos.

Definir la función

sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de uno o más números primos consecutivos. Por ejemplo,

λ> sumas 311
[[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],
[53,59,61,67,71],[101,103,107],[311]]
λ> sumas 41
[[2,3,5,7,11,13],[11,13,17],[41]]
λ> sumas 14
[]
λ> [length (sumas n) | n <- [0..20]]
[0,0,1,1,0,2,0,1,1,0,1,1,1,1,0,1,0,2,1,1,0]
λ> maximum [length (sumas n) | n <- [1..600]]
5

Subnúmeros pares

José A. Alonso

Misceláneas

Los subnúmeros de un número x son los números que se pueden formar con dígitos de x en posiciones consecutivas. Por ejemplo, el número 254 tiene 6 subnúmeros: 2, 5, 4, 25, 54 y 254.

Definir las funciones

subnumeros       :: Integer -> [Integer]
nSubnumerosPares :: Integer -> Integer

tales que

(subnumerosPares x) es la lista de los subnúmeros pares de x. Por ejemplo,

subnumerosPares 254   ==  [2,254,54,4]
subnumerosPares 154   ==  [154,54,4]
subnumerosPares 15    ==  []

(nSubnumerosPares x) es la cantidad de subnúmeros pares de x. Por ejemplo,

nSubnumerosPares 254   ==  4
nSubnumerosPares2 (4^(10^6))  ==  90625258498

Soluciones

import Data.List ( genericLength
                 , inits
                 , tails
                 )

subnumerosPares :: Integer -> [Integer]
subnumerosPares n =
  filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,
--    subnumeros 254  ==  [2,25,5,254,54,4]
subnumeros :: Integer -> [Integer]
subnumeros n =
  [read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo,
--    sublistas "abc"  ==  ["a","ab","b","abc","bc","c"]
sublistas :: [a] -> [[a]]
sublistas xs =
  concat [init (tails ys) | ys <- tail (inits xs)]

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

nSubnumerosPares :: Integer -> Integer
nSubnumerosPares =
  genericLength . subnumerosPares

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

nSubnumerosPares2 :: Integer -> Integer
nSubnumerosPares2 =
  sum . posicionesDigitosPares

-- (posicionesDigitosPares x) es la lista de las posiciones de los
-- dígitos pares de x. Por ejemplo,
--    posicionesDigitosPares 254  ==  [1,3]
posicionesDigitosPares :: Integer -> [Integer]
posicionesDigitosPares x =
  [n | (n,y) <- zip [1..] (show x)
     , y `elem` "02468"]

-- Comparación de eficiencia
--    λ> nSubnumerosPares (2^(10^3))
--    22934
--    (2.83 secs, 3,413,414,872 bytes)
--    λ> nSubnumerosPares2 (2^(10^3))
--    22934
--    (0.01 secs, 0 bytes)

Elementos con su doble en el conjunto.

José A. Alonso

Misceláneas

Definir la función

conDoble :: [Int] -> [Int]

tal que (conDoble xs) es la lista de los elementos del conjunto xs (representado como una lista sin elementos repetidos) cuyo doble pertenece a xs. Por ejemplo,

conDoble [1, 4, 3, 2, 9, 7, 18, 22]  ==  [1,2,9]
conDoble [2, 4, 8, 10]               ==  [2,4]
conDoble [7, 5, 11, 13, 1, 3]        ==  []
length (conDoble4 [1..10^6])         ==  500000

Referencia: Basado en el problema Doubles de POJ (Peking University Online Judge System).

Buscaminas

José A. Alonso

Misceláneas

El buscaminas es un juego cuyo objetivo es despejar un campo de minas sin detonar ninguna.

El campo de minas se representa mediante un cuadrado con NxN casillas. Algunas casillas tienen un número, este número indica las minas que hay en todas las casillas vecinas. Cada casilla tiene como máximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda contiene dos minas, cada una representada por el número 9, y a la derecha se muestra el campo obtenido anotando las minas vecinas de cada casilla

9 0 0 0       9 1 0 0
0 0 0 0       2 2 1 0
0 9 0 0       1 9 1 0
0 0 0 0       1 1 1 0

de la misma forma, la anotación del siguiente a la izquierda es el de la derecha

9 9 0 0 0     9 9 1 0 0
0 0 0 0 0     3 3 2 0 0
0 9 0 0 0     1 9 1 0 0

En el ejercicio se usará la librería Data.Matrix, cuyo manual se encuentra en aquí.

Los campos de minas se representan mediante matrices:

type Campo = Matrix Int

Por ejemplo, los anteriores campos de la izquierda se definen por

ejCampo1, ejCampo2 :: Campo
ejCampo1 = fromLists [[9,0,0,0],
                      [0,0,0,0],
                      [0,9,0,0],
                      [0,0,0,0]]
ejCampo2 = fromLists [[9,9,0,0,0],
                      [0,0,0,0,0],
                      [0,9,0,0,0]]

Definir la función

buscaminas :: Campo -> Campo

tal que (buscaminas c) es el campo obtenido anotando las minas vecinas de cada casilla. Por ejemplo,

λ> buscaminas ejCampo1
( 9 1 0 0 )
( 2 2 1 0 )
( 1 9 1 0 )
( 1 1 1 0 )

λ> buscaminas ejCampo2
( 9 9 1 0 0 )
( 3 3 2 0 0 )
( 1 9 1 0 0 )

Clases de equivalencia

José A. Alonso

Misceláneas

Definir la función

clasesEquivalencia :: Ord a =>
                      Set a -> (a -> a -> Bool) -> Set (Set a)

tal que (clasesEquivalencia xs r) es el conjunto de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

λ> let c = fromList [-3..3]
λ> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)
fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]
λ> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)
fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

Ampliación de una matriz

José A. Alonso

Misceláneas

Definir, usando Data.Matrix, la función

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

tal que (ampliaMatriz p f c) es la matriz obtenida a partir de p repitiendo cada fila f veces y cada columna c veces. Por ejemplo, si ej1 es la matriz definida por

ej1 :: Matrix Char
ej1 = fromLists [" x ",
                 "x x",
                 " x "]

entonces

λ> ampliaMatriz ej1 1 2
( ' ' ' ' 'x' 'x' ' ' ' ' )
( 'x' 'x' ' ' ' ' 'x' 'x' )
( ' ' ' ' 'x' 'x' ' ' ' ' )

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)
  xx
xx  xx
  xx
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)
 x
 x
x x
x x
 x
 x
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)
  xx
  xx
xx  xx
xx  xx
  xx
  xx
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)
   xxx
   xxx
xxx   xxx
xxx   xxx
   xxx
   xxx

Nota: Este ejercicio está basado en el problema Skener de Kattis.

Problema de las jarras

José A. Alonso

Misceláneas

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en alguna de las dos jarras.

Definir la función

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

tal (jarras (a,b,c)) es una solución del problema de las jarras (a,b,c) con el mínimo número de movimientos, si el problema tiene solución y Nothing, en caso contrario. Por ejemplo,

λ> jarras (5,3,4)
Just [(0,0),(5,0),(2,3),(2,0),(0,2),(5,2),(4,3)]

La interpretación de la solución anterior es

(0,0) se inicia con las dos jarras vacías,
(5,0) se llena la jarra de 5 con el grifo,
(2,3) se llena la de 3 con la de 5,
(2,0) se vacía la de 3,
(0,2) se pasa el contenido de la primera a la segunda,
(5,2) se llena la primera con el grifo,
(4,3) se llena la segunda con la primera.

Otros ejemplos:

λ> jarras (3,5,4)
Just [(0,0),(0,5),(3,2),(0,2),(2,0),(2,5),(3,4)]
λ> jarras (15,10,5)
Just [(0,0),(15,0),(5,10)]
λ> jarras (15,10,4)
Nothing
λ> length <$> jarras (181,179,100)
Just 199

El problema de las N torres

José A. Alonso

Misceláneas

El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.

Cada solución del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,

( 0 1 0 )
( 1 0 0 )
( 0 0 1 )

representa una solución del problema de las 3 torres.

Definir las funciones

torres  :: Int -> [Matrix Int]
nTorres :: Int -> Integer

tales que + (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

λ> torres 3
[( 1 0 0 )
 ( 0 1 0 )
 ( 0 0 1 )
,( 1 0 0 )
 ( 0 0 1 )
 ( 0 1 0 )
,( 0 1 0 )
 ( 1 0 0 )
 ( 0 0 1 )
,( 0 1 0 )
 ( 0 0 1 )
 ( 1 0 0 )
,( 0 0 1 )
 ( 1 0 0 )
 ( 0 1 0 )
,( 0 0 1 )
 ( 0 1 0 )
 ( 1 0 0 )
]

(nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,

λ> nTorres 3
6
λ> length (show (nTorres (10^4)))
35660

Densidades de números abundantes, perfectos y deficientes

José A. Alonso

Misceláneas

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

Definir las funciones

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

tales que

(densidades n) es la terna formada por la n-ésima densidad de los números abundantes (es decir, para los que la suma de sus divisores propios es mayor que el número), de los números perfectos (es decir, para los que la suma de sus divisores propios es mayor que el número) y de los números deficientes (es decir, para los que la suma de sus divisores propios es menor que el número). Por ejemplo,

densidades 100     ==  (0.22,    2.0e-2, 0.76)
densidades 1000    ==  (0.246,   3.0e-3, 0.751)
densidades 10000   ==  (0.2488,  4.0e-4, 0.7508)
densidades 100000  ==  (0.24795, 4.0e-5, 0.75201)

(graficas n) dibuja las gráficas de las k-ésimas densidades (para k entre 1 y n) de los números abundantes, de los números perfectos y de los números deficientes. Por ejemplo, (graficas 100) dibuja

Densidades de números abundantes, perfectos y deficientes

y (graficas 400) dibuja

Densidades de números abundantes, perfectos y deficientes

Enumeración de árboles binarios

José A. Alonso

Misceláneas

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

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

Por ejemplo, el árbol

      "B"
      / \
     /   \
    /     \
  "B"     "A"
  / \     / \
"A" "B" "C" "C"

se puede definir por

ej1 :: Arbol String
ej1 = N "B" (N "B" (H "A") (H "B")) (N "A" (H "C") (H "C"))

Definir la función

enumeraArbol :: Arbol t -> Arbol Int

tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,

λ> enumeraArbol ej1
N 6 (N 2 (H 0) (H 1)) (N 5 (H 3) (H 4))

Gráficamente,

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

Agrupamiento según valores

José A. Alonso

Misceláneas

Definir la función

agrupa :: Ord c => (a -> c) -> [a] -> Map c [a]

tal que (agrupa f xs) es el diccionario obtenido agrupando los elementos de xs según sus valores mediante la función f. Por ejemplo,

λ> agrupa length ["hoy", "ayer", "ana", "cosa"]
fromList [(3,["hoy","ana"]),(4,["ayer","cosa"])]
λ> agrupa head ["claro", "ayer", "ana", "cosa"]
fromList [('a',["ayer","ana"]),('c',["claro","cosa"])]

Distancias entre primos consecutivos

José A. Alonso

Misceláneas

Los 15 primeros números primos son

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Las distancias entre los elementos consecutivos son

1, 2, 2, 4, 2,  4,  2,  4,  6,  2,  6,  4,  2,  4

La distribución de las distancias es

(1,1), (2,6), (4,5), (6,2)

(es decir, el 1 aparece una vez, el 2 aparece 6 veces, etc.) La frecuencia de las distancias es

(1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

(es decir, el 1 aparece el 7.142857%, el 2 el 42.857143% etc.)

Definir las funciones

cuentaDistancias        :: Int -> [(Int,Int)]
frecuenciasDistancias   :: Int -> [(Int,Float)]
graficas                :: [Int] -> IO ()
distanciasMasFrecuentes :: Int -> [Int]

tales que

(cuentaDistancias n) es la distribución de distancias entre los n primeros primos consecutivos. Por ejemplo,

λ> cuentaDistancias 15
[(1,1),(2,6),(4,5),(6,2)]
λ> cuentaDistancias 100
[(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

(frecuenciasDistancias n) es la frecuencia de distancias entre los n primeros primos consecutivos. Por ejemplo,

λ> frecuenciasDistancias 15
[(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]
λ> frecuenciasDistancias 30
[(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

(graficas ns) dibuja las gráficas de (frecuenciasDistancias k) para k en ns. Por ejemplo, (graficas [10,20,30]) dibuja

Distancias entre primos consecutivos

(graficas [x*10^3 | x <- [1,2,3]]) dibuja

Distancias entre primos consecutivos

y (graficas [x*10^5 | x <- [1,2,3]]) dibuja

Distancias entre primos consecutivos

(distanciasMasFrecuentes n) es la lista de las distancias más frecuentes entre los elementos consecutivos de la lista de los n primeros primos. Por ejemplo,

distanciasMasFrecuentes 15   ==  [2]
distanciasMasFrecuentes 26   ==  [2,4]
distanciasMasFrecuentes 32   ==  [4]
distanciasMasFrecuentes 41   ==  [2,4,6]
distanciasMasFrecuentes 77   ==  [6]
distanciasMasFrecuentes 160  ==  [4,6]

Comprobar con QuickCheck si para todo n > 160 se verifica que (distanciasMasFrecuentes n) es [6].

Rotaciones divisibles por 4

José A. Alonso

Misceláneas

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816. De las cuales, las divisibles por 4 son 928160, 816092, 160928 y 92816.

Definir la función

nRotacionesDivisibles :: Integer -> Int

tal que (nRotacionesDivisibles n) es el número de rotaciones del número n divisibles por 4. Por ejemplo,

nRotacionesDivisibles 928160          ==  4
nRotacionesDivisibles 44              ==  2
nRotacionesDivisibles (1234^50000)    ==  38684
nRotacionesDivisibles (1234^300000)   ==  231853

Potencias perfectas

José A. Alonso

Misceláneas

Un número natural n es una potencia perfecta si existen dos números naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son

4 = 2², 8 = 2³, 9 = 3², 16 = 2⁴, 25 = 5², 27 = 3³, 32 = 2⁵,
36 = 6², 49 = 7², 64 = 2⁶, ...

Definir la sucesión

potenciasPerfectas :: [Integer]

cuyos términos son las potencias perfectas. Por ejemplo,

take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]
potenciasPerfectas !! 100   ==  6724

Definir el procedimiento

grafica :: Int -> IO ()

tal que (grafica n) es la representación gráfica de las n primeras potencias perfectas. Por ejemplo, para (grafica 30) dibuja

!Potencias perfectas](/images/Potencias_perfectas.png)

Sumas con sumandos distintos o con sumandos impares

José A. Alonso

Misceláneas

El número 6 se puede descomponer de 4 formas distintas como suma con sumandos distintos:

6 = 1 + 2 + 3
6 = 1 + 5
6 = 2 + 4
6 = 6

y también se puede descomponer de 4 formas distintas como suma con sumandos impares:

6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 3
6 = 1 + 5
6 = 3 + 3

Definir las siguientes funciones

sumasSumandosDistintos  :: Integer -> [[Integer]]
nSumasSumandosDistintos :: Integer -> Int
sumasSumandosImpares    :: Integer -> [[Integer]]
nSumasSumandosImpares   :: Integer -> Int
igualdadDeSumas         :: Integer -> Bool

tales que

(sumasSumandosDistintos n) es la lista de las descomposiciones de n como sumas con sumandos distintos. Por ejemplo,

sumasSumandosDistintos 5  ==  [[1,4],[2,3],[5]]
sumasSumandosDistintos 6  ==  [[1,2,3],[1,5],[2,4],[6]]

(nSumasSumandosDistintos n) es el número de descomposiciones de n como sumas con sumandos distintos. Por ejemplo,

nSumasSumandosDistintos 6  ==  4
nSumasSumandosDistintos 7  ==  5

(sumasSumandosImpares n) es la lista de las descomposiones de n como sumas con sumandos impares. Por ejemplo,

sumasSumandosImpares 5  ==  [[1,1,1,1,1],[1,1,3],[5]]
sumasSumandosImpares 6  ==  [[1,1,1,1,1,1],[1,1,1,3],[1,5],[3,3]]

(nSumasSumandosImpares n) es el número de descomposiciones de n como sumas con sumandos impares. Por ejemplo,

nSumasSumandosImpares 6  ==  4
nSumasSumandosImpares 7  ==  5

(igualdadDeSumas n) se verifica si, para todo k entre 1 y n, las funciones nSumasSumandosDistintos y nSumasSumandosImpares son iguales. Por ejemplo,

igualdadDeSumas 40  ==  True

Término ausente en una progresión aritmética.

José A. Alonso

Misceláneas

Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.

Definir la función

ausente :: Integral a => [a] -> a

tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,

ausente [3,7,9,11]                ==  5
ausente [3,5,9,11]                ==  7
ausente [3,5,7,11]                ==  9
ausente ([1..9]++[11..])          ==  10
ausente2 ([1..10^6] ++ [2+10^6])  ==  1000001

Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay exactamente un término de la progresión aritmética que no está en la lista.

El problema del reciclado

José A. Alonso

Misceláneas

El problema del reciclado del reciclado N P consiste en lo siguiente: un grupo de personas disponen de N botellas de refresco vacía y las llevan a reciclar obteniendo una botella llena por cada P vacías; se beben inmediatamente el contenido de las botellas obtenidas y sus botellas vacías, junto con las no recicladas anteriormente, las canjean por botellas llenas. El proceso continúa hasta que no tienen suficientes botellas para canjear. El objetivo del problema es calcular el número de botellas que se han bebido.

Por ejemplo, si disponen de 10 botellas y por cada 2 obtienen 1, se producen cuatro canjeos:

en el primer canjeo entregan las 10 y obtienen 5;
en el segundo, entregan 4, le quedan 1 y obtienen 2;
en el tercero, entregan 2, le queda 1 y obtienen 1;
en el cuarto, entregan 2 y obtienen 1.

Por tanto, se han bebido 9 y le quedan 1 que no pueden canjear.

Definir la función

reciclado :: Int -> Int -> Int

tal que (reciclado n p) es el número de botellas que se beben en el reciclado comenzado con n botellas y canjeando p botellas vacías por una llena. Por ejemplo,

reciclado  9 3  ==  4
reciclado 10 2  ==  9

Orden simétrico

José A. Alonso

Misceláneas

Dada una lista de cadenas ordenadas por longitud, se puede ordenar de manera simétrica colocando la primera cadena en primer lugar, la segunda en el último, la tercera en el segundo, la cuarta en el penúltimo y así sucesivamente.

Por ejemplo, dada la lista

Pi
Eva
Luis
Paula
Alberto
Francisco

su ordenación simétrica es

Pi
Luis
Alberto
Francisco
Paula
Eva

Definir la función

simetrica :: [String] -> [String]

tal que (simetrica xs) es la ordenación simétrica de la lista de cadenas (ordenada por longitud) xs. Por ejemplo,

λ> simetrica ["Pi","Eva","Luis","Paula","Alberto","Francisco"]
["Pi","Luis","Alberto","Francisco","Paula","Eva"]
λ> minimum $ simetrica2 [replicate k 'a' | k <- [1..2*10^6]]
"a"

Nota: Este ejercicio está basado en el problema Symmetric order de Kattis.

Puntos alcanzables en un mapa

José A. Alonso

Misceláneas

Un mapa con dos tipos de regiones (por ejemplo, tierra y mar) se puede representar mediante una matriz de ceros y unos.

Para los ejemplos usaremos los mapas definidos por

type Punto = (Int,Int)
type Mapa  = Array Punto Int

mapa1, mapa2 :: Mapa
mapa1 = listArray ((1,1),(3,4))
                  [1,1,0,0,
                   0,1,0,0,
                   1,0,0,0]
mapa2 = listArray ((1,1),(10,20))
                  [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,
                   1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,
                   0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

Definir las funciones

alcanzables :: Mapa -> Punto -> [Punto]
esAlcanzable :: Mapa -> Punto -> Punto -> Bool

tales que

(alcanzables p) es la lista de los puntos de mapa m que se pueden alcanzar a partir del punto p moviéndose en la misma región que p (es decir, a través de ceros si el elemento de m en p es un cero o a través de unos, en caso contrario) y los movimientos permitidos son ir hacia el norte, sur este u oeste (pero no en diagonal). Por ejemplo,

alcanzables mapa1 (1,1)  ==  [(2,2),(1,2),(1,1)]
alcanzables mapa1 (1,2)  ==  [(2,2),(1,1),(1,2)]
alcanzables mapa1 (1,3)  ==  [(3,2),(3,4),(3,3),(2,3),(2,4),(1,4),(1,3)]
alcanzables mapa1 (3,1)  ==  [(3,1)]

(esAlcanzable m p1 p2) se verifica si el punto p1 es alcanzable desde el p1 en el mapa m. Por ejemplo,

esAlcanzable mapa1 (1,4) (3,2)    ==  True
esAlcanzable mapa1 (1,4) (3,1)    ==  False
esAlcanzable mapa2 (2,3) (8,16)   ==  True
esAlcanzable mapa2 (8,1) (7,3)    ==  True
esAlcanzable mapa2 (1,1) (10,20)  ==  False

Nota: Este ejercicio está basado en el problema 10 kinds of people de Kattis.

Número de dígitos del factorial

José A. Alonso

Misceláneas

Definir las funciones

nDigitosFact :: Integer -> Integer
graficas     :: [Integer] -> IO ()

tales que

(nDigitosFact n) es el número de dígitos de n!. Por ejemplo,

nDigitosFact 0        ==  1
nDigitosFact 4        ==  2
nDigitosFact 5        ==  3
nDigitosFact 10       ==  7
nDigitosFact 100      ==  158
nDigitosFact 1000     ==  2568
nDigitosFact 10000    ==  35660
nDigitosFact 100000   ==  456574
nDigitosFact 1000000  ==  5565709

(graficas xs) dibuja las gráficas de los números de dígitos del factorial de k (para k en xs) y de la recta y = 5.5 x. Por ejemplo, (graficas [0,500..10^6]) dibuja

Número de dígitos del factorial

Nota: Este ejercicio está basado en el problema How many digits? de Kattis en donde se impone la restricción de calcular, en menos de 1 segundo, el número de dígitos de los factoriales de 10.000 números del rango [0,1.000.000].

Se puede simular como sigue

λ> import System.Random
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> maximum (map nDigitosFact4 xs)
5561492
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> maximum (map nDigitosFact4 xs)
5563303

Representación de conjuntos mediante intervalos

José A. Alonso

Misceláneas

Un conjunto de números enteros se pueden representar mediante una lista ordenada de intervalos tales que la diferencia entre el menor elemento de un intervalo y el mayor elemento de su intervalo anterior es mayor que uno.

Por ejemplo, el conjunto {2, 7, 4, 3, 9, 6} se puede representar mediante la lista de intervalos [(2,4),(6,7),(9,9)] de forma que en el primer intervalo se agrupan los números 2, 3 y 4; en el segundo, los números 6 y 7 y el tercero, el número 9.

Definir la función

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

tal que (intervalos xs) es lista ordenada de intervalos que representa al conjunto xs. Por ejemplo,

intervalos [2,7,4,3,9,6]  ==  [(2,4),(6,7),(9,9)]

Nota: Este ejercicio está basado en el problema Bus numbers de Kattis

Codificación matricial

José A. Alonso

Misceláneas

El procedimiento de codificación matricial se puede entender siguiendo la codificación del mensaje "todoparanada" como se muestra a continuación:

Se calcula la longitud L del mensaje. En el ejemplo es L es 12.
Se calcula el menor entero positivo N cuyo cuadrado es mayor o igual que L. En el ejemplo N es 4.
Se extiende el mensaje con N²-L puntos. En el ejemplo, el mensaje extendido es "todoparanada····"
Con el mensaje extendido se forma una matriz cuadrada NxN. En el ejemplo la matriz es

| t o d o |
| p a r a |
| n a d a |
| · · · · |

Se rota 90º la matriz del mensaje extendido. En el ejemplo, la matriz rotada es

| · n p t |
| · a a o |
| · d r d |
| · a a o |

Se calculan los elementos de la matriz rotada. En el ejemplo, los elementos son "·npt·aap·drd·aao"
El mensaje codificado se obtiene eliminando los puntos de los elementos de la matriz rotada. En el ejemplo, "nptaapdrdaao".

Definir la función

codificado :: String -> String

tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,

codificado "todoparanada"    ==  "nptaaodrdaao"
codificado "nptaaodrdaao"    ==  "danaopadtora"
codificado "danaopadtora"    ==  "todoparanada"
codificado "entodolamedida"  ==  "dmdeaeondltiao"

Nota: Este ejercicio está basado en el problema Secret Message de Kattis.

Reducción de repeticiones consecutivas

José A. Alonso

Misceláneas

Definir la función

reducida :: Eq a => [a] -> [a]

tal que (reducida xs) es la lista obtenida a partir de xs de forma que si hay dos o más elementos idénticos consecutivos, borra las repeticiones y deja sólo el primer elemento. Por ejemplo,

λ> reducida "eesssooo essss   toodddooo"
"eso es todo"

Nota: Basado en el ejercicio Apaxiaaaaaaaaaaaans! de Kattis.

Suma de subconjuntos

José A. Alonso

Misceláneas

Los subconjuntos de [1, 4, 2] son

[], [1], [4], [1, 4], [2], [1, 2], [4, 2], [1, 4, 2]

Las sumas de sus elementos son

0, 1, 4, 5, 2, 3, 6, 7

Y la suma de las sumas es 28.

Definir la función

sumaSubconjuntos :: [Integer] -> Integer

tal que (sumaSubconjuntos xs) es la suma de las sumas de los subconjuntos de xs. Por ejemplo,

sumaSubconjuntos [1,2]                     == 6
sumaSubconjuntos [1,4,2]                   == 28
length (show (sumaSubconjuntos [1..10^6])) == 301042

Por 3 o más 5

José A. Alonso

Misceláneas

El enunciado del problema Por 3 o más 5 de ¡Acepta el reto! es el siguiente

Cuenta la leyenda que un famoso matemático, tras aprender a sumar y multiplicar a la tierna edad de 3 años en apenas 5 días, se dio cuenta de que, empezando por 1, podía generar un montón de números sin más que multiplicar por 3 o sumar 5 a alguno de los que ya hubiera generado antes.

Por ejemplo, el 23 (edad a la que se casaría) lo obtuvo así: ((1 + 5) × 3) + 5 Por su parte el 77 (edad a la que tendría su primer bisnieto) lo consiguió: (((1 × 3 + 5) × 3) × 3) + 5

Por mucho que lo intentó, algunos números, sin embargo, resultaron ser imposibles de obtener, como por ejemplo el 5, el 7 o el 15.

Se dice que un número es generable si se puede escribir como una sucesión (quizá vacía) de multiplicaciones por 3 y sumas de 5 al número 1.

Definir las siguientes funciones

generables     :: [Integer]
generable      :: Integer -> Bool
arbolGenerable :: Integer -> Tree Integer

tales que

generables es la sucesión de los números generables. Por ejemplo,

λ> take 20 generables
[1,3,6,8,9,11,13,14,16,18,19,21,23,24,26,27,28,29,31,32]
λ> generables !! (10^6)
1250008

(generable x) se verifica si x es generable. Por ejemplo,

generable 23       ==  True
generable 77       ==  True
generable 15       ==  False
generable 1250008  ==  True
generable 1250010  ==  False

(arbolGenerable x) es el árbol de los números generables menores o iguales a x. Por ejemplo,

λ> putStrLn (drawTree (fmap show (arbolGenerable 11)))
1
|
+- 3
|  |
|  +- 9
|  |
|  `- 8
|
`- 6
   |
   `- 11

Números cubifinitos

José A. Alonso

Misceláneas

El enunciado del problema Números cubifinitos de ¡Acepta el reto! es el siguiente

Se dice que un número es cubifinito cuando al elevar todos sus dígitos al cubo y sumarlos el resultado o bien es 1 o bien es un número cubifinito.

Por ejemplo, el número 1243 es cubifinito, pues al elevar todos sus dígitos al cubo obtenemos 100 que es cubifinito.

Por su parte, el 513 no es cubifinito, pues al elevar al cubo sus dígitos conseguimos el 153 que nunca podrá ser cubifinito, pues la suma de los cubos de sus dígitos vuelve a dar 153.

Definir las funciones

esCubifinito :: Int -> Bool
grafica :: Int -> IO ()

tales que

(esCubifinito n) se verifica si n es un número cubifinito. Por ejemplo,

esCubifinito 1      ==  True
esCubifinito 10     ==  True
esCubifinito 1243   ==  True
esCubifinito 87418  ==  True
esCubifinito 513    ==  False

(grafica n) dibuja la gráfica de la sucesión de los primeros n números cubifinitos. Por ejemplo, al evaluar (grafica 50) se dibuja

Números cubifinitos

Distribución de diferencias de dígitos consecutivos de pi

José A. Alonso

Misceláneas

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

Las diferencias de sus elementos consecutivos es

2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

y la distribución de sus frecuencias en el intervalo [-9,9] es

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

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

distribucionDDCpi :: Int -> [Int]
graficas :: [Int] -> FilePath -> IO ()

tales que

(distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,

λ> distribucionDDCpi 18
[0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]
λ> distribucionDDCpi 100
[1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]
λ> distribucionDDCpi 200
[3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]
λ> distribucionDDCpi 1000
[16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]
λ> distribucionDDCpi 5000
[67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

(graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] "distribucionDDCpi.png" se escribe en el fichero "distribucionDDCpi.png" la siguiente gráfica

Distribución de diferencias de dígitos consecutivos de pi

Nota: Se puede usar la librería Data.Number.CReal.

Números de Catalan

José A. Alonso

Misceláneas

Los números de Catalan forman la sucesión cuyo término general es

Números de Catalan

Los primeros números de Catalan son

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786

Los números de Catalan satisfacen la siguiente relación de recurrencia:

Números de Catalan

Asintóticamente, los números de Catalan crecen como:

Números de Catalan

considerando que el cociente entre el n-ésimo número de Catalan y la expresión de la derecha tiende hacia 1 cuando n tiende a infinito.

Definir las funciones

catalan :: [Integer]
grafica :: Int -> Int -> IO ()

tales que

catalan es la lista de términos de la sucesión de Catalan. Por ejemplo,

λ> take 12 catalan
[1,1,2,5,14,42,132,429,1430,4862,16796,58786]
λ> length (show (catalan !! 50000))
30096

(grafica a b) dibuja los n-ésimos términos de la sucesión de Catalan, para n entre a y b, junto con los de la expresión de la derecha de

Números de Catalan

Por ejemplo, (grafica 5 10) dibuja

Números de Catalan

y (grafica 55 60) dibuja

Números de Catalan

Caminos minimales en un arbol numérico

José A. Alonso

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

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

Generadores de números de Gibonacci

José A. Alonso

Misceláneas

Los números de Gabonacci generados por (a,b) son los elementos de la sucesión de Gabonacci definida por

G(0) = a
G(1) = b
G(n) = G(n-2) + G(n-1), si n > 1

Por ejemplo, la sucesión de Gabonacci generada por (2,5) es 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, ...

Un número pertenece a distintas sucesiones de Gabonacci. Por ejemplo, el 9 pertenece a las sucesiones de Gabonacci generados por (3,3), (1,4) y (4,5).

El menor generador de Gabonacci de un número x es el par (a,b), con 1 ≤ a ≤ b, tal que (a,b) es un generador de Gabonacci de x y no existe ningún generador de Gabonacci de x (a',b') tal que b' < b ó b' = b y a' < a. Por ejemplo, el menor generador de Gabonacci de 9 es (3,3).

Definir la función

menorGenerador :: Integer -> (Integer,Integer)

tal que (menorGenerador x) es el menor generador de Gabonacci de x. Por ejemplo,

menorGenerador 9          ==  (3,3)
menorGenerador 7          ==  (1,3)
menorGenerador 5          ==  (1,1)
menorGenerador 27         ==  (3,7)
menorGenerador 57         ==  (4,9)
menorGenerador 218        ==  (10,21)
menorGenerador 1121       ==  (20,41)
menorGenerador 89         ==  (1,1)
menorGenerador 123        ==  (1,3)
menorGenerador 1000       ==  (2,10)
menorGenerador 842831057  ==  (2,7)
menorGenerador 1573655    ==  (985,1971)

Número de islas rectangulares de una matrizexer

José A. Alonso

Misceláneas

En este problema se consideran matrices cuyos elementos son 0 y 1. Los valores 1 aparecen en forma de islas rectangulares separadas por 0 de forma que como máximo las islas son diagonalmente adyacentes. Por ejemplo,

ej1, ej2 :: Array (Int,Int) Int
ej1 = listArray ((1,1),(6,3))
                [0,0,0,
                 1,1,0,
                 1,1,0,
                 0,0,1,
                 0,0,1,
                 1,1,0]
ej2 = listArray ((1,1),(6,6))
                [1,0,0,0,0,0,
                 1,0,1,1,1,1,
                 0,0,0,0,0,0,
                 1,1,1,0,1,1,
                 1,1,1,0,1,1,
                 0,0,0,0,1,1]

Definir la función

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

tal que (numeroDeIslas p) es el número de islas de la matriz p. Por ejemplo,

numeroDeIslas ej1  ==  3
numeroDeIslas ej2  ==  4

La codificación de Luka

José A. Alonso

Misceláneas

En el problema Kemija se utiliza la codificación de Luka consistente en añadir detrás de cada vocal la letra 'p' seguida de la vocal. Por ejemplo, la palabra "elena" se codifica como "epelepenapa" y "luisa" por "lupuipisapa".

Definir las funciones

codifica   :: String -> String
decodifica :: String -> String

tales que + (codifica cs) es la codificación de Luka de la cadena cs. Por ejemplo,

λ> codifica "elena admira a luisa"
"epelepenapa apadmipirapa apa lupuipisapa"
λ> codifica "todo para nada"
"topodopo paparapa napadapa"

(decodifica cs) es la decodificación de Luka de la cadena cs. Por ejemplo,

λ> decodifica "epelepenapa apadmipirapa apa lupuipisapa"
"elena admira a luisa"
λ> decodifica "topodopo paparapa napadapa"
"todo para nada"

Números binarios invertidos

José A. Alonso

Misceláneas

La representación binaria de 13 es 1101, que al invertirlo da 1011 cuya representación decimal es el número 11.

Definir la función

transformado :: Integer -> Integer

tal que (transformado x) es la representación decimal del número obtenido invirtiendo la representación binaria de x. Por ejemplo,

transformado 13  ==  11
transformado 47  ==  61

Nota: El ejercicio está basado en el problema Reversed Binary Numbers de Kattis.

Números construibles como sumas de dos dados

José A. Alonso

Misceláneas

Un número x es construible a partir de a y b si se puede escribir como una suma cuyos sumandos son a o b (donde se supone que a y be son números enteros mayores que 0). Por ejemplo, 7 y 9 son construibles a partir de 2 y 3 ya que 7 = 2+2+3 y 9 = 3+3+3.

Definir las funciones

construibles  :: Integer -> Integer -> [Integer]
esConstruible :: Integer -> Integer -> Integer -> Bool

tales que

(construibles a b) es la lista de los números construibles a partir de a y b. Por ejemplo,

take 5 (construibles 2 9)  ==  [2,4,6,8,9]
take 5 (construibles 6 4)  ==  [4,6,8,10,12]
take 5 (construibles 9 7)  ==  [7,9,14,16,18]

(esConstruible a b x) se verifica si x es construible a partir de a y b. Por ejemplo,

esConstruible 2 3 7   ==  True
esConstruible 9 7 15  ==  False

Contando en la arena

José A. Alonso

Misceláneas

El problema de ayer de ¡Acepta el reto! fue Contando en la arena cuyo enunciado reproduzco a continuación:

Es ampliamente conocido que escribimos los números utilizando base 10, en la que expresamos las cantidades utilizando 10 dígitos distintos (0…9). El valor de cada uno de ellos depende de la posición que ocupe dentro del número, pues cada dígito se multiplica por una potencia de 10 distinta según cuál sea esa posición. La descomposición, por ejemplo, del número 1.234 es: 1.234 = 1×10^3 + 2×10^2 + 3×10^1 + 4×10^0 Otra base muy conocida es la base 2 al ser la utilizada por los dispositivos electrónicos. En ella sólo hay dos dígitos distintos (0 y 1), que se ven multiplicados por potencias de 2. Mucho antes de que llegaran la base 2, la base 10 e incluso los números romanos, los primeros seres humanos contaban haciendo surcos en la arena, muescas en un trozo de madera o colocando palos en línea. Estaban, sin saberlo, usando base 1. En ella sólo hay un símbolo y cada dígito es multiplicado por una potencia de 1. Dado que 1^n = 1 el resultado es que todos los dígitos tienen el mismo peso.

Definir la función

transformaAbase1 :: FilePath -> FilePath -> IO ()

tal que al evaluar (transformaAbase1 f1 f2) lee el contenido del fichero f1 (que estará compuesto por distintos números mayores que 0, cada uno en una línea) y escribe en el fichero f2 una línea con la representación en base 1 de cada uno de los números de f1 excepto el 0 final. Por ejemplo, si el contenido de "Entrada.txt" es

al evaluar (transformaAbase1 "Entrada.txt" "Salida.txt") el contenido de "Salida.txt" debe de ser

1
1111
111111

Cálculo de pi mediante la serie de Nilakantha

José A. Alonso

Misceláneas

Una serie infinita para el cálculo de pi, publicada por Nilakantha en el siglo XV, es \[\pi = 3 + \frac{4}{2 \cdot 3 \cdot 4} - \frac{4}{4 \cdot 5 \cdot 6} + \frac{4}{6 \cdot 7 \cdot 8} - \frac{4}{8 \cdot 9 \cdot 10} + \cdots\]

Definir las funciones

aproximacionPi :: Int -> Double
tabla          :: FilePath -> [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi obtenido sumando los n primeros términos de la serie de Nilakantha. Por ejemplo,

aproximacionPi 0        ==  3.0
aproximacionPi 1        ==  3.1666666666666665
aproximacionPi 2        ==  3.1333333333333333
aproximacionPi 3        ==  3.145238095238095
aproximacionPi 4        ==  3.1396825396825396
aproximacionPi 5        ==  3.1427128427128426
aproximacionPi 10       ==  3.1414067184965018
aproximacionPi 100      ==  3.1415924109719824
aproximacionPi 1000     ==  3.141592653340544
aproximacionPi 10000    ==  3.141592653589538
aproximacionPi 100000   ==  3.1415926535897865
aproximacionPi 1000000  ==  3.141592653589787
pi                      ==  3.141592653589793

(tabla f ns) escribe en el fichero f las n-ésimas aproximaciones de pi, donde n toma los valores de la lista ns, junto con sus errores. Por ejemplo, al evaluar la expresión

tabla "AproximacionesPi.txt" [0,10..100]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|   10 | 3.141406718497 | 0.000185935093 |
|   20 | 3.141565734659 | 0.000026918931 |
|   30 | 3.141584272675 | 0.000008380915 |
|   40 | 3.141589028941 | 0.000003624649 |
|   50 | 3.141590769850 | 0.000001883740 |
|   60 | 3.141591552546 | 0.000001101044 |
|   70 | 3.141591955265 | 0.000000698325 |
|   80 | 3.141592183260 | 0.000000470330 |
|   90 | 3.141592321886 | 0.000000331704 |
|  100 | 3.141592410972 | 0.000000242618 |
+------+----------------+----------------+

al evaluar la expresión

tabla "AproximacionesPi.txt" [0,500..5000]

hace que el contenido del fichero "AproximacionesPi.txt" sea

+------+----------------+----------------+
| n    | Aproximación   | Error          |
+------+----------------+----------------+
|    0 | 3.000000000000 | 0.141592653590 |
|  500 | 3.141592651602 | 0.000000001988 |
| 1000 | 3.141592653341 | 0.000000000249 |
| 1500 | 3.141592653516 | 0.000000000074 |
| 2000 | 3.141592653559 | 0.000000000031 |
| 2500 | 3.141592653574 | 0.000000000016 |
| 3000 | 3.141592653581 | 0.000000000009 |
| 3500 | 3.141592653584 | 0.000000000006 |
| 4000 | 3.141592653586 | 0.000000000004 |
| 4500 | 3.141592653587 | 0.000000000003 |
| 5000 | 3.141592653588 | 0.000000000002 |
+------+----------------+----------------+

Sucesiones alícuotas

José A. Alonso

Misceláneas

La sucesión alícuota de un número x es la sucesión cuyo primer término es x y cada otro término es la suma de los divisores propios del término anterior. Por ejemplo, la sucesión alícuota de 10 es [10,8,7,1,0,0,0] ya que

la suma de los divisores propios de 10 es 5 + 2 + 1 = 8
la suma de los divisores propios de  8 es 4 + 2 + 1 = 7
la suma de los divisores propios de  7 es 1
la suma de los divisores propios de  1 es 0

Definir la función

sucAlicuota :: Integer -> [Integer]

tal que (sucAlicuota x) es la sucesión alícuota de x. Por ejemplo,

take 6 (sucAlicuota 10)       ==  [10,8,7,1,0,0]
take 6 (sucAlicuota 95)       ==  [95,25,6,6,6,6]
take 6 (sucAlicuota 220)      ==  [220,284,220,284,220,284]
sucAlicuota 1184 !! (1+10^7)  ==  1210
sucAlicuota 276 !! 200        ==  2790456740340877466506

Precisión de aproximaciones de pi

José A. Alonso

Misceláneas

La precisión de una aproximación x de pi es el número de dígitos comunes entre el inicio de x y de pi. Por ejemplo, puesto que 355/113 es 3.1415929203539825 y pi es 3.141592653589793, la precisión de 355/113 es 7.

Definir las siguientes funciones

mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]
precisionPi       :: Double -> Int
precisionPiCR     :: CReal -> Int

tales que

(mayorPrefijoComun xs ys) es el mayor prefijo común de xs e ys. Por ejemplo,

mayorPrefijoComun []      [2,3,4,5]  ==  []
mayorPrefijoComun [2,3,5] []         ==  []
mayorPrefijoComun [2,3,5] [2,3,4,5]  ==  [2,3]
mayorPrefijoComun [2,3,5] [2,5,3,4]  ==  [2]
mayorPrefijoComun [2,3,5] [5,2,3,4]  ==  []

(precisionPi x) es la precisión de la aproximación de pi x. Por ejemplo,

precisionPi (25/8)              ==  2
precisionPi (22/7)              ==  3
precisionPi (sqrt 2 + sqrt 3)   ==  3
precisionPi (377/120)           ==  4
precisionPi (31**(1/3))         ==  4
precisionPi (7^7/4^9)           ==  5
precisionPi (355/113)           ==  7
precisionPi ((2143/22)**(1/4))  ==  9

(precisionPiCR x) es la precisión de la aproximación de pi x, como números reales. Por ejemplo,

precisionPiCR (log (640320^3+744)/(sqrt 163))                        == 31
precisionPiCR (log (5280^3*(236674+30303*sqrt 61)^3+744)/(sqrt 427)) == 53

Nota: Para la definición precisionPiCR se usa la librería Data.Number.CReal que se instala con

cabal install numbers

Cálculo de pi mediante el método de Newton

José A. Alonso

Misceláneas

El método de Newton para el cálculo de pi se basa en la relación

Cálculo de pi mediante el método de Newton

y en el desarrollo del arco seno

Cálculo de pi mediante el método de Newton

de donde se obtiene la fórmula

Cálculo de pi mediante el método de Newton

La primeras aproximaciones son

a(0) = 6*(1/2)                               = 3.0
a(1) = 6*(1/2+1/(2*3*2^3))                   = 3.125
a(2) = 6*(1/2+1/(2*3*2^3)+(1*3)/(2*4*5*2^5)) = 3.1390625

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Newton. Por ejemplo,

aproximacionPi 0   ==  3.0
aproximacionPi 1   ==  3.125
aproximacionPi 2   ==  3.1390625
aproximacionPi 10  ==  3.1415926468755613
aproximacionPi 21  ==  3.141592653589793
pi                 ==  3.141592653589793

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..30]) dibuja

Cálculo de pi mediante el método de Newton

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

José A. Alonso

Misceláneas

La fórmula de Gregory-Leibniz para calcular pi es

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

y la de Beeler es

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

Definir las funciones

aproximaPiGL     :: Int -> Double
aproximaPiBeeler :: Int -> Double
graficas         :: [Int] -> IO ()

tales que

(aproximaPiGL n) es la aproximación de pi con los primeros n términos de la fórmula de Gregory-Leibniz. Por ejemplo,

aproximaPiGL 1       ==  4.0
aproximaPiGL 2       ==  2.666666666666667
aproximaPiGL 3       ==  3.466666666666667
aproximaPiGL 10      ==  3.0418396189294032
aproximaPiGL 100     ==  3.1315929035585537
aproximaPiGL 1000    ==  3.140592653839794
aproximaPiGL 10000   ==  3.1414926535900345
aproximaPiGL 100000  ==  3.1415826535897198

(aproximaPiBeeler n) es la aproximación de pi con los primeros n términos de la fórmula de Beeler. Por ejemplo,

aproximaPiBeeler 1   ==  2.0
aproximaPiBeeler 2   ==  2.6666666666666665
aproximaPiBeeler 3   ==  2.933333333333333
aproximaPiBeeler 10  ==  3.140578169680337
aproximaPiBeeler 60  ==  3.141592653589793
pi                   ==  3.141592653589793

(graficas xs) dibuja la gráfica de las k-ésimas aproximaciones de pi, donde k toma los valores de la lista xs, con las fórmulas de Gregory-Leibniz y de Beeler. Por ejemplo, (graficas [1..50]) dibuja

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

donde la línea morada corresponde a la aproximación de Gregory-Leibniz y la verde a la de Beeler.

Cálculo de pi mediante la fracción continua de Lange

José A. Alonso

Misceláneas

En 1999, L.J. Lange publicó el artículo An elegant new continued fraction for π.

En el primer teorema del artículo se demuestra la siguiente expresión de π mediante una fracción continua $Cálculo de pi mediante la fracción continua de Lange$

La primeras aproximaciones son

a(1) = 3+1                = 4.0
a(2) = 3+(1/(6+9))        = 3.066666666666667
a(3) = 3+(1/(6+9/(6+25))) = 3.158974358974359

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fracción continua de Lange. Por ejemplo,

aproximacionPi 1     ==  4.0
aproximacionPi 2     ==  3.066666666666667
aproximacionPi 3     ==  3.158974358974359
aproximacionPi 10    ==  3.141287132741557
aproximacionPi 100   ==  3.141592398533554
aproximacionPi 1000  ==  3.1415926533392926

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..10]) dibuja

$Cálculo de pi mediante la fracción continua de Lange$

(grafica [10..100]) dibuja

$Cálculo de pi mediante la fracción continua de Lange$

y (grafica [100..200]) dibuja

$Cálculo de pi mediante la fracción continua de Lange$

Cálculo de pi mediante la variante de Euler de la serie armónica

José A. Alonso

Misceláneas

En el artículo El desarrollo más bello de Pi como suma infinita, Miguel Ángel Morales comenta el desarrollo de pi publicado por Leonhard Euler en su libro "Introductio in Analysis Infinitorum" (1748).

El desarrollo es el siguiente

Cálculo de pi mediante la variante de Euler de la serie armónica

y se obtiene a partir de la serie armónica

Cálculo de pi mediante la variante de Euler de la serie armónica

modificando sólo el signo de algunos términos según el siguiente criterio:

Dejamos un + cuando el denominador de la fracción sea un 2 o un primo de la forma 4m-1.
Cambiamos a - si el denominador de la fracción es un primo de la forma 4m+1.
Si el número es compuesto ponemos el signo que quede al multiplicar los signos correspondientes a cada factor.

Por ejemplo,

la de denominador 3 = 4x1-1 lleva un +,
la de denominador 5 = 4x1+1 lleva un -,
la de denominador 13 = 4x3+1 lleva un -,
la de denominador 6 = 2x3 lleva un + (porque los dos llevan un +),
la de denominador 10 = 2x5 lleva un - (porque el 2 lleva un + y el 5 lleva un -) y
la de denominador 50 = 5x5x2 lleva un + (un - por el primer 5, otro - por el segundo 5 y un + por el 2).

Definir las funciones

aproximacionPi :: Int -> Double
grafica        :: Int -> IO ()

tales que

(aproximacionPi n) es la aproximación de pi obtenida sumando los n primeros términos de la serie de Euler. Por ejemplo.

aproximacionPi 1        ==  1.0
aproximacionPi 10       ==  2.3289682539682537
aproximacionPi 100      ==  2.934318000847734
aproximacionPi 1000     ==  3.0603246224585128
aproximacionPi 10000    ==  3.1105295744825403
aproximacionPi 100000   ==  3.134308801935256
aproximacionPi 1000000  ==  3.1395057903490806

(grafica n) dibuja la gráfica de las aproximaciones de pi usando k sumando donde k toma los valores de la lista [100,110..n]. Por ejemplo, al evaluar (grafica 4000) se obtiene

Cálculo de pi mediante la variante de Euler de la serie armónica

Regresión lineal

José A. Alonso

Misceláneas

Dadas dos listas de valores

xs = [x(1), x(2), ..., x(n)]
ys = [y(1), y(2), ..., y(n)]

la ecuación de la recta de regresión de ys sobre xs es y = a+bx, donde \[b = \frac{n \sum x_i y_i - \sum x_i \sum y_i}{n \sum x_i^2 - \left(\sum x_i\right)^2}\] \[a = \frac{\sum y_i - b \sum x_i}{n}\]

Definir la función

regresionLineal :: [Double] -> [Double] -> (Double,Double)

tal que (regresionLineal xs ys) es el par (a,b) de los coeficientes de la recta de regresión de ys sobre xs. Por ejemplo, para los valores

ejX, ejY :: [Double]
ejX = [5,  7, 10, 12, 16, 20, 23, 27, 19, 14]
ejY = [9, 11, 15, 16, 20, 24, 27, 29, 22, 20]

se tiene

λ> regresionLineal ejX ejY
(5.195045748716805,0.9218924347243919)

Para comprobar la definición se define el procedimiento

grafica :: [Double] -> [Double] -> IO ()
grafica xs ys =
    plotPathsStyle
      [YRange (0,10+mY)]
      [(defaultStyle {plotType = Points,
                      lineSpec = CustomStyle [LineTitle "Datos",
                                              PointType 2,
                                              PointSize 2.5]},
                     zip xs ys),
       (defaultStyle {plotType = Lines,
                      lineSpec = CustomStyle [LineTitle "Ajuste",
                                              LineWidth 2]},
                     [(x,a+b*x) | x <- [0..mX]])]
    where (a,b) = regresionLineal xs ys
          mX    = maximum xs
          mY    = maximum ys

tal que (grafica xs ys) pintea los puntos correspondientes a las listas de valores xs e ys y su recta de regresión. Por ejemplo, con (grafica ejX ejY) se obtiene el siguiente dibujo

Regresión lineal

Sucesión de trazas de dígitos de pi

José A. Alonso

Misceláneas

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Las matrices de orden 1x1, 2x2, ..., 5x5 formadas por los primeros dígitos de pi son

( 3 )  ( 3 1 )  ( 3 1 4 )  ( 3 1 4 1 )  ( 3 1 4 1 5 )
       ( 4 1 )  ( 1 5 9 )  ( 5 9 2 6 )  ( 9 2 6 5 3 )
                ( 2 6 5 )  ( 5 3 5 8 )  ( 5 8 9 7 9 )
                           ( 9 7 9 3 )  ( 3 2 3 8 4 )
                                        ( 6 2 6 4 3 )

y sus trazas (es decir, sumas de los elementos de la diagonal principal) son 3, 4, 13, 20 y 25, respectivamente.

Definir la función

trazas :: Int -> IO [Int]

tal que (trazas n) es la lista de las trazas de las matrices de orden 1x1, 2x2, 3x3, ..., nxn formadas por los primeros dígitos de pi. Por ejemplo,

λ> trazas 20
[3,4,13,20,25,30,19,32,41,59,62,64,58,75,62,60,80,99,78,108]
λ> ts <- trazas 1000
λ> maximum ts
4644
λ> maximum <$> trazas 1000
4644

Distribución de dígitos de pi

José A. Alonso

Misceláneas

Se pueden generar los dígitos de Pi, como se explica en el artículo Unbounded spigot algorithms for the digits of pi, con la función digitosPi definida por

digitosPi :: [Integer]
digitosPi = g(1,0,1,1,3,3) where
  g (q,r,t,k,n,l) =
    if 4*q+r-t < n*t
    then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)
    else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

Por ejemplo,

λ> take 25 digitosPi
[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3]

La distribución de los primeros 25 dígitos de pi es [0,2,3,5,3,3,3,1,2,3] ya que el 0 no aparece, el 1 ocurre 2 veces, el 3 ocurre 3 veces, el 4 ocurre 5 veces, ...

Usando digitosPi, definir las siguientes funciones

distribucionDigitosPi :: Int -> [Int]
frecuenciaDigitosPi   :: Int -> [Double]

tales que

(distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,

λ> distribucionDigitosPi 10
[0,2,1,2,1,2,1,0,0,1]
λ> distribucionDigitosPi 100
[8,8,12,12,10,8,9,8,12,13]
λ> distribucionDigitosPi 1000
[93,116,103,103,93,97,94,95,101,105]
λ> distribucionDigitosPi 5000
[466,531,496,460,508,525,513,488,492,521]

(frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,

λ> frecuenciaDigitosPi 10
[0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]
λ> frecuenciaDigitosPi 100
[8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]
λ> frecuenciaDigitosPi 1000
[9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]
λ> frecuenciaDigitosPi 5000
[9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

Búsqueda en los dígitos de pi

José A. Alonso

Misceláneas

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir la función

posicion :: String -> IO (Maybe Int)

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

λ> posicion "15"
Just 3
λ> posicion "2017"
Just 8897
λ> posicion "022017"
Just 382052
λ> posicion "14022017"
Nothing
λ> posicion "999999"
Just 762
λ> posicion "458151"
Just 999995

Cálculo de pi usando la fórmula de Vieta

José A. Alonso

Misceláneas

La fórmula de Vieta para el cálculo de pi es la siguiente \[ \pi = 2 \times \frac{2}{\sqrt{2}} \times \frac{2}{\sqrt{2 + \sqrt{2}}} \times \frac{2}{\sqrt{2 + \sqrt{2 + \sqrt{2}}}} \times \frac{2}{\sqrt{2 + \sqrt{2 + \sqrt{2 + \sqrt{2}}}}} \times \cdots \]

Definir las funciones

aproximacionPi :: Int -> Double
errorPi :: Double -> Int

tales que

(aproximacionPi n) es la aproximación de pi usando n factores de la fórmula de Vieta. Por ejemplo,

aproximacionPi  5  ==  3.140331156954753
aproximacionPi 10  ==  3.1415914215112
aproximacionPi 15  ==  3.141592652386592
aproximacionPi 20  ==  3.1415926535886207
aproximacionPi 25  ==  3.141592653589795

(errorPi x) es el menor número de factores de la fórmula de Vieta necesarios para obtener pi con un error menor que x. Por ejemplo,

errorPi 0.1        ==  2
errorPi 0.01       ==  4
errorPi 0.001      ==  6
errorPi 0.0001     ==  7
errorPi 1e-4       ==  7
errorPi 1e-14      ==  24
pi                 ==  3.141592653589793
aproximacionPi 24  ==  3.1415926535897913

Cálculo de pi usando el producto de Wallis

José A. Alonso

Misceláneas

El producto de Wallis es una expresión, descubierta por John Wallis en 1655, para representar el valor de π y que establece que: \[ \frac{\pi}{2} = \frac{2}{1} \cdot \frac{2}{3} \cdot \frac{4}{3} \cdot \frac{4}{5} \cdot \frac{6}{5} \cdot \frac{6}{7} \cdot \frac{8}{7} \cdot \frac{8}{9} \cdots \]

Definir las funciones

factoresWallis  :: [Rational]
productosWallis :: [Rational]
aproximacionPi  :: Int -> Double
errorPi         :: Double -> Int

tales que + factoresWallis es la sucesión de los factores del productos de Wallis. Por ejemplo,

λ> take 10 factoresWallis
[2 % 1,2 % 3,4 % 3,4 % 5,6 % 5,6 % 7,8 % 7,8 % 9,10 % 9,10 % 11]

productosWallis es la sucesión de los productos de los primeros factores de Wallis. Por ejemplo,

λ> take 7 productosWallis
[2 % 1,4 % 3,16 % 9,64 % 45,128 % 75,256 % 175,2048 % 1225]

(aproximacionPi n) es la aproximación de pi obtenida multiplicando los n primeros factores de Wallis. Por ejemplo,

aproximacionPi 20     ==  3.2137849402931895
aproximacionPi 200    ==  3.1493784731686008
aproximacionPi 2000   ==  3.142377365093878
aproximacionPi 20000  ==  3.141671186534396

(errorPi x) es el menor número de factores de Wallis necesarios para obtener pi con un error menor que x. Por ejemplo,

errorPi 0.1     ==  14
errorPi 0.01    ==  155
errorPi 0.001   ==  1569
errorPi 0.0001  ==  15707

Caminos en un árbol binario con suma dada

José A. Alonso

Misceláneas

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

data Arbol = H
           | N Int Arbol Arbol
  deriving Show

Por ejemplo, los árboles

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

se representan por

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

Definir las funciones

caminos     :: Arbol -> [[Int]]
caminosSuma :: Arbol -> Int -> [[Int]]

tales que

(caminos a) es la lista de los caminos entre dos nodos cualesquiera del árbol a. Por ejemplo,

λ> caminos ej1
[[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5],
 [2],[2,1],[2,7],[1],[7],[4],[4,5],[5]]
λ> caminos ej2
[[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9],
 [5],[5,6],[6],[8],[8,4],[8,9],[4],[9]]
λ> length (caminos ej3)
33

(caminosSuma a k) es la lista de los caminos entre dos nodos cualesquiera del árbol a cuya suma es k. Por ejemplo,

λ> caminosSuma ej1 3
[[3],[2,1]]
λ> caminosSuma ej3 3
[[3],[-1,4]]
λ> caminosSuma ej3 4
[[1,3],[1,-1,4],[3,1],[-1,4,1],[-1,5],[4]]
λ> caminosSuma ej3 5
[[1,3,1],[1,-1,4,1],[1,-1,5],[3,2],[3,1,1],[-1,4,2],[4,1],[5]]
λ> caminosSuma ej3 6
[[1,3,2],[1,3,1,1],[1,-1,4,2],[4,2],[6]]
λ> caminosSuma ej3 7
[]

Máximo común divisor de x e y veces n

José A. Alonso

Misceláneas

Definir las funciones

repite :: Int -> Integer -> Integer
mcdR   :: Integer -> Int -> Int -> Integer

tales que

(repite x n) es el número obtenido repitiendo x veces el número n. Por ejemplo.

repite 3 123  ==  123123123

(mcdR n x y) es el máximo común divisor de los números obtenidos repitiendo x veces e y veces el número n. Por ejemplo.

mcdR 123 2 3                     ==  123
mcdR 4 4 6                       ==  44
mcdR 2017 (10^1000) (2+10^1000)  ==  20172017

Caminos desde la raíz en un árbol binario

José A. Alonso

Misceláneas

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

data Arbol = H
           | N Int Arbol Arbol
  deriving Show

Por ejemplo, los árboles

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

se representan por

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

Definir la función

caminosDesdeRaiz :: Arbol -> [[Int]]

tal que (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la raíz de a hasta cualquiera de sus nodos. Por ejemplo.

λ> caminosDesdeRaiz ej1
[[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]]
λ> caminosDesdeRaiz ej2
[[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]]

Prefijo con suma acotada

José A. Alonso

Misceláneas

Definir la función

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

tal que (prefijoAcotado x ys) es el mayor prefijo de ys cuya suma es menor que x. Por ejemplo,

prefijoAcotado 10 [3,2,5,7]  ==  [3,2]
prefijoAcotado 10 [1..]      ==  [1,2,3]

Aplicaciones de operaciones

José A. Alonso

Misceláneas

Definir la función

aplicaciones :: [a -> b -> c] -> [a] -> [b] -> [c]

tal que (aplicaciones os xs ys) es la lista obtenida aplicando las operaciones de os a los elementos de xs es ys. Por ejemplo,

λ> aplicaciones [(+),(*)] [1,2] [5,8]
[6,9,7,10,5,8,10,16]
λ> aplicaciones [(+),(*)] [1,2] [5]
[6,7,5,10]
λ> aplicaciones [(<),(>)] ["ab","c"] ["def","c"]
[True,True,True,False,False,False,False,False]
λ> import Data.List
λ> aplicaciones [(++),intersect] ["ab","c"] ["bd","cf"]
["abbd","abcf","cbd","ccf","b","","","c"]

Sucesión de Cantor de números innombrables

José A. Alonso

Misceláneas

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior como se indica a continuación:

1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
(2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
(25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
(30) 99 100

Definir la sucesión

sucCantor :: [Integer]

cuyos elementos son los términos de la sucesión de Cantor. Por ejemplo,

λ> take 100 sucCantor
[1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,
 22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,
 40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,
 13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,
 20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,
 6, 92,93,94,95,96, 29, 30 ,99,100]

λ> sucCantor2 !! (5+10^6)
544480

λ> sucCantor2 !! (6+10^6)
266086

Particiones de una lista

José A. Alonso

Misceláneas

Definir la función

particiones :: [a] -> [[[a]]]

tal que (particiones xs) es la lista de las particiones de xs en segmentos de elementos consecutivos. Por ejemplo,

λ> particiones [1..3]
[[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,2,3]]]
λ> mapM_ print (particiones "abcd")
["a","b","c","d"]
["a","b","cd"]
["a","bc","d"]
["a","bcd"]
["ab","c","d"]
["ab","cd"]
["abc","d"]
["abcd"]
λ> length (particiones [1..22])
2097152

Comprobar con QuickCheck que la concatenación de cada uno de los elementos de (particiones xs) es igual a xs.

Nota: En la comprobación usar ejemplos pequeños como se indica a continuación

quickCheckWith (stdArgs {maxSize=10}) prop_particiones

Subrayado de un carácter

José A. Alonso

Misceláneas

Definir el procedimiento

subraya :: String -> Char -> IO ()

tal que (subraya cs c) escribe la cadena cs y debajo otra subrayando las ocurrencias de c. Por ejemplo,

λ> subraya "Salamanca es castellana" 'a'
Salamanca es castellana
 ^ ^ ^  ^     ^     ^ ^
λ> subraya "Salamanca es castellana" 'n'
Salamanca es castellana
      ^              ^
λ> subraya "Salamanca es castellana" ' '
Salamanca es castellana
         ^  ^

Eliminación de triplicados

José A. Alonso

Misceláneas

Definir la función

sinTriplicados :: Eq a => [a] -> [a]

tal que (sinTriplicados xs) es la lista obtenida dejando en xs sólo las dos primeras ocurrencias de cada uno de sus elementos. Por ejemplo,

sinTriplicados "aaabcbccdbabdcd"  ==  "aabcbcdd"
sinTriplicados "xxxxx"            ==  "xx"
sinTriplicados "abcabc"           ==  "abcabc"
sinTriplicados "abcdabcaba"       ==  "abcdabc"
sinTriplicados "abacbadcba"       ==  "abacbdc"
sinTriplicados "aaabcbccdbabdcd"  ==  "aabcbcdd"
sinTriplicados (show (5^4^3))     ==  "54210108624757363989"
sinTriplicados (show (8^8^8))     ==  "60145207536139279488"

Máximo producto de pares en la lista.

José A. Alonso

Misceláneas

Definir la función

maximoProducto :: [Int] -> Maybe Int

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir como producto de dos elementos distintos de xs o Nothing, en el caso de que ningún elemento de xs se pueda escribir como producto de dos elementos distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

maximoProducto [10, 3, 5, 30, 35]       ==  Just 30
maximoProducto [10, 2, 2, 4, 30, 35]    ==  Just 4
maximoProducto [17, 2, 1, 35, 30]       ==  Just 35
maximoProducto [2,4]                    ==  Nothing
maximoProducto [2, 5, 7, 8]             ==  Nothing
maximoProducto [10, 2, 4, 30, 35]       ==  Nothing
maximoProducto [1+2^n | n <- [1..10^6]] ==  Just 4611686018427387905

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Suma minimal de productos de pares de elementos consecutivos

José A. Alonso

Misceláneas

Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos:

10, por ejemplo con [1,4,2,3] ya que 1x4+2x3 = 10
11, por ejemplo con [1,3,2,4] ya que 1x3+2x4 = 11
14, por ejemplo con [1,2,3,4] ya que 1x2+3x4 = 14

Por tanto, la mínima suma de los productos de elementos consecutivos en las permutaciones de [1,2,3,4] es 10 y una permutación con dicha suma es [1,4,2,3].

Definir las funciones

minimaSumaProductos  :: (Num a, Ord a) => [a] -> a
permutacionMinimal   :: (Num a, Ord a) => [a] -> [a]

tales que

(minimaSumaProductos xs) es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,

minimaSumaProductos [1..4]             ==  10
minimaSumaProductos [3,2,5,7,1,6]      ==  34
minimaSumaProductos [9,2,8,4,5,7,6,0]  ==  74
minimaSumaProductos [1,2,1,4,0,5,6,0]  ==  6

(permutacionMinimal xs) es una permutación de xs cuya suma de productos de elementos consecutivos de xs es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,

permutacionMinimal [1..4]             ==  [1,4,3,2]
permutacionMinimal [3,2,5,7,1,6]      ==  [1,7,2,6,3,5]
permutacionMinimal [9,2,8,4,5,7,6,0]  ==  [0,9,2,8,4,7,5,6]
permutacionMinimal [1,2,1,4,0,5,6,0]  ==  [0,6,0,5,1,4,1,2]

Máxima potencia que divide al factorial

José A. Alonso

Misceláneas

La máxima potencia de 2 que divide al factorial de 5 es 3, ya que 5! = 120, 120 es divisible por 2^3 y no lo es por 2^4.

Definir la función

maxPotDivFact :: Integer -> Integer -> Integer

tal que (maxPotDivFact p n), para cada primo p, es el mayor k tal que p^k divide al factorial de n. Por ejemplo,

maxPotDivFact 2 5       ==  3
maxPotDivFact 3 6       ==  2
maxPotDivFact 2 10      ==  8
maxPotDivFact 3 10      ==  4
maxPotDivFact 2 (10^2)  ==  97
maxPotDivFact 2 (10^3)  ==  994
maxPotDivFact 2 (10^4)  ==  9995
maxPotDivFact 2 (10^5)  ==  99994
maxPotDivFact 2 (10^6)  ==  999993
maxPotDivFact 3 (10^5)  ==  49995
maxPotDivFact 3 (10^6)  ==  499993
maxPotDivFact 7 (10^5)  ==  16662
maxPotDivFact 7 (10^6)  ==  166664
length (show (maxPotDivFact 2 (10^20000)))  ==  20000

Árboles continuos

José A. Alonso

Misceláneas

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

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

Por ejemplo, los árboles

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

se representan por

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

Un árbol binario es continuo si el valor absoluto de la diferencia de los elementos adyacentes es 1. Por ejemplo, el árbol ej1 es continuo ya que el valor absoluto de sus pares de elementos adyacentes son

|3-2| = |2-1| = |2-3| = |3-4| = |4-5| = 1

En cambio, el ej2 no lo es ya que |8-10| ≠ 1.

Definir la función

esContinuo :: (Num a, Eq a) => Arbol a -> Bool

tal que (esContinuo x) se verifica si el árbol x es continuo. Por ejemplo,

esContinuo ej1  ==  True
esContinuo ej2  ==  False

La sucesión "Mira y di"

José A. Alonso

Misceláneas

La sucesión "Mira y di" (en inglés, Look-and-Say) es una sucesión de números naturales en donde cada término se obtiene agrupando las cifras iguales del anterior y recitándolas. Por ejemplo, si x(0) = 1 se lee como "un uno" y por tanto x(1) = 11. Análogamente,

x(1) = 11     (dos unos                          --> 21)
x(2) = 21     (un dos un uno                     --> 1211)
x(3) = 1211   (un uno un dos dos unos            --> 111221)
x(4) = 111221 (tres unos dos doses un uno        --> 312211)
x(5) = 312211 (un tres un uno dos doses dos unos --> 13112221)

Definir la función

sucMiraYDi :: Integer -> [Integer]

tal que (sucMiraYDi n) es la sucesión "Mira y di" cuyo primer término es n. Por ejemplo,

λ> take 9 (sucMiraYdi 1)
[1,11,21,1211,111221,312211,13112221,1113213211,31131211131221]
λ> take 5 (sucMiraYdi 2017)
[2017,12101117,111211103117,31123110132117,1321121321101113122117]
λ> take 7 (sucMiraYDi 22)
[22,22,22,22,22,22,22]
λ> (sucMiraYDi 1) !! 11
3113112221232112111312211312113211
λ> (sucMiraYDi 1) !! 12
1321132132111213122112311311222113111221131221

Independientemente del término inicial x(0) elegido (con la única salvedad del 22), la sucesión diverge y la razón entre el número de cifras de x(n) y el de x(n-1) tiende a un valor fijo que es la constante de Conway λ ≈ 1.303577269. Por ejemplo, para x(0) = 1, las razones son

2, 1, 2, 1.5, 1, 1.3333333333333333, 1.25, 1.4, 1.4285714285714286, 1.3

Definir la función

aproximacionConway :: Integer -> Double -> Int

tal que (aproximacionConway n e) es el menor k tal que la diferencia entre la constante de Conway y la razón entre el número de cifras de x(k) x(k-1) es, en valor absoluto, menor que e. Por ejemplo,

aproximacionConway 1 0.3     ==  3
aproximacionConway 1 0.1     ==  5
aproximacionConway 1 0.01    ==  9
aproximacionConway 1 0.001   ==  24
aproximacionConway 1 0.0001  ==  43
aproximacionConway 2 0.0001  ==  47

Cadena de primos

José A. Alonso

Misceláneas

La lista de los primeros números primos es

[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

Los primeros elementos de la cadena obtenida concatenado los números primos es

"23571113171923293137414347535961677173798389971011"

Definir la función

primoEnPosicion :: Int -> Integer

tal que (primoEnPosicion n) es el número primo que tiene algún dígito en la posición n de la cadena obtenida concatenado los números primos. Por ejemplo,

primoEnPosicion 0       ==  2
primoEnPosicion 1       ==  3
primoEnPosicion 4       ==  11
primoEnPosicion 5       ==  11
primoEnPosicion 6       ==  13
primoEnPosicion 1022    ==  2011
primoEnPosicion 1023    ==  2017
primoEnPosicion 1026    ==  2017
primoEnPosicion 1027    ==  2027
primoEnPosicion (10^7)  ==  21242357

Notación polaca inversa

José A. Alonso

Misceláneas

La notación polaca inversa (en inglés, Reverse Polish Notation, o RPN), es una forma alternativa de escribir expresiones matemáticas. Por ejemplo, la expresión "20 - (4 + 3) * 2" en RPN es "20 4 3 + 2 * -".

Para evaluar una expresión en RPN, usamos una lista auxiliar (inicialmente vacía) y recorremos la expresión de izquierda a derecha. Cada vez que encontramos un número, lo añadimos a la lista auxiliar. Cuando encontramos un operador, retiramos los dos números que hay al principio de la pila, utilizamos el operador con ellos y los quitamos de la lista y le añadimos el resultado. Cuando alcancemos el final de la expresión, debemos tener un solo número en la lista auxiliar si la expresión estaba bien formada, y éste representa el resultado de la expresión. Por ejemplo, la evaluación de RPN "20 4 3 + 2 * -" es la siguiente

""                 []
"20"               [20]
"20 4"             [4, 20]
"20 4 3"           [3, 4, 20]
"20 4 3 +"         [7, 20]
"20 4 3 + 2"       [2, 7, 20]
"20 4 3 + 2 *"     [14, 20]
"20 4 3 + 2 * -"   [6]

Definir la función

valor :: String -> Float

tal que (valor cs) es el valor de la expresión RPN cs. Por ejemplo,

valor "4"               ==  4.0
valor "4 3 +"           ==  7.0
valor "4 3 + 2 *"       ==  14.0
valor "20 4 3 + 2 * -"  ==  6.0
valor "3 7 + 2 /"       ==  5.0

La conjetura de Rodolfo

José A. Alonso

Misceláneas

El pasado 1 de enero, Claudio Meller publicó el artículo La conjetura de Rodolfo que afirma que

Todos los números naturales se pueden números pueden expresarse como la suma de un capicúa y un capicúa especial (siendo los capicúas especiales los números que al quitarles los ceros finales son capicúas; por ejemplo, 32300, 50500 y 78987).

Definir las funciones

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

tales que

(descomposiciones x) es la lista de las descomposiciones de x como la suma de un capicúa y un capicúa especial. Por ejemplo,

descomposiciones 1980  ==  [(99,1881),(979,1001)]
descomposiciones 2016  ==  [(575,1441),(606,1410)]
descomposiciones 1971  ==  [(161,1810),(1771,200),(1881,90)]

contraejemplosConjeturaRodolfo es la lista de contraejemplos de la conjetura de Rodolfo; es decir, de los números que no pueden expresarse com la suma de un capicúa y un capicúa especial. Por ejemplo,

λ> take 12 contraejemplosConjeturaRodolfo
[1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
[3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

Sustitución en una posición

José A. Alonso

Misceláneas

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

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

Por ejemplo, los árboles

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

se pueden representar por

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

Para indicar las posiciones del árbol se define el tipo

type Posicion = [Direccion]

donde

data Direccion = D | I
  deriving Eq

representa un movimiento hacia la derecha (D) o a la izquierda. Por ejemplo, las posiciones de los elementos del ej1 son

9 []
8 [I]
3 [I,I]
2 [I,D]
6 [D]
4 [D,I]
5 [D,D]

Definir la función

sustitucion :: Posicion -> a -> Arbol a -> Arbol a

tal que (sustitucion ds z x) es el árbol obtenido sustituyendo el elemento de x en la posición ds por z. Por ejemplo,

λ> sustitucion [I,D] 7 ej1
N 9 (N 8 (N 3 H H) (N 7 H H)) (N 6 (N 4 H H) (N 5 H H))
λ> sustitucion [D,D] 7 ej1
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 7 H H))
λ> sustitucion [I] 7 ej1
N 9 (N 7 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
λ> sustitucion [] 7 ej1
N 7 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Sumas de dos capicúas

José A. Alonso

Misceláneas

Definir las funciones

sumas2Capicuas  :: Integer -> [(Integer, Integer)]
noSuma2Capicuas :: [Integer]

tales que

(sumas2Capicuas x) es la lista de las descomposiciones de x como suma de dos capicúas (con el primer sumando menor o igual que el segundo). Por ejemplo,

sumas2Capicuas 17  == [(6,11),(8,9)]
sumas2Capicuas 187 == [(6,181),(66,121),(88,99)]
sumas2Capicuas 165 == [(4,161),(44,121),(66,99),(77,88)]
sumas2Capicuas 382 == [(9,373),(191,191)]
sumas2Capicuas 151 == [(0,151)]
sumas2Capicuas 201 == []

noSuma2Capicuas es la sucesión de los números que no se pueden escribir como suma de dos capicúas. Por ejemplo,

λ> take 15 noSuma2Capicuas
[21,32,43,54,65,76,87,98,201,1031,1041,1042,1051,1052,1053]
λ> noSuma2Capicuas !! 3000
19941

Inversa del factorial

José A. Alonso

Misceláneas

Definir la función

inversaFactorial :: Integer -> Maybe Integer

tal que (inversaFactorial x) es (Just n) si el factorial de n es x y es Nothing si no existe ningún número n tal que el factorial de n es x. Por ejemplo,

inversaFactorial 24  ==  Just 4
inversaFactorial 25  ==  Nothing

Suma ordenada de listas infinitas ordenadas

José A. Alonso

Misceláneas

Definir la función

sumaOrdenada :: [Integer] -> [Integer] -> [Integer]

tal que (sumaOrdenada xs ys) es la suma ordenada de las listas infinitas crecientes xs e ys. Por ejemplo,

λ> take 15 (sumaOrdenada [5,10..] [7,14..])
[12,17,19,22,24,26,27,29,31,32,33,34,36,37,38]
λ> take 15 (sumaOrdenada [2^n | n <- [0..]] [3^n | n <- [0..]])
[2,3,4,5,7,9,10,11,13,17,19,25,28,29,31]

Sumas de tres capicúas

José A. Alonso

Misceláneas

Definir la función

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

tales que (sumas3Capicuas x) es la lista de las descomposiciones de x como suma de tres capicúas (con los sumandos no decrecientes). Por ejemplo,

sumas3Capicuas 0  ==  [(0,0,0)]
sumas3Capicuas 1  ==  [(0,0,1)]
sumas3Capicuas 2  ==  [(0,0,2),(0,1,1)]
sumas3Capicuas 3  ==  [(0,0,3),(0,1,2),(1,1,1)]
sumas3Capicuas 4  ==  [(0,0,4),(0,1,3),(0,2,2),(1,1,2)]
length (sumas3Capicuas 17)      ==  17
length (sumas3Capicuas 2017)    ==  47
length (sumas3Capicuas 999999)  ==  15266

Comprobar con QuickCheck que todo número natural se puede escribir como suma de tres capicúas.

Sucesión de capicúas

José A. Alonso

Misceláneas

Definir las funciones

capicuas        :: [Integer]
posicionCapicua :: Integer -> Integer

tales que

capicuas es la sucesión de los números capicúas. Por ejemplo,

λ> take 45 capicuas
[0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
 303,313,323,333,343,353]
λ> capicuas !! (10^5)
900010009

(posicionCapicua x) es la posición del número capicúa x en la sucesión de los capicúas. Por ejemplo,

λ> posicionCapicua 353
44
λ> posicionCapicua 900010009
100000
λ> let xs = show (123^30)
λ> posicionCapicua (read (xs ++ reverse xs))
1497912859868342793044999075260564303046944727069807798026337448
λ> posicionCapicua (read (xs ++ "7" ++ reverse xs))
5979128598683427930449990752605643030469447270698077980263374496

Nodos con k sucesores

José A. Alonso

Misceláneas

Sumas y restas alternativas

José A. Alonso

Misceláneas

Definir la función

sumasYrestas :: Num a => [a] -> a

tal que (sumasYrestas xs) es el resultado de alternativamente los elementos de xs. Por ejemplo,

sumasYrestas [3,2,4,1,7] = 3 - 2 + 4 - 1 + 7
                         = 11

Otros ejemplos,

sumasYrestas [3,2,4]              ==  5
sumasYrestas [3,2,4,1]            ==  4
sumasYrestas [3,2,4,1,7]          ==  11
sumasYrestas (replicate (10^6) 1) ==  0

Números dorados

José A. Alonso

Misceláneas

Los dígitos del número 2375 se pueden separar en dos grupos de igual tamaño ([7,2] y [5,3]) tales que para los correspondientes números (72 y 53) se verifique que la diferencia de sus cuadrados sea el número original (es decir, 72^2 - 53^2 = 2375).

Un número x es dorado si sus dígitos se pueden separar en dos grupos de igual tamaño tales que para los correspondientes números (a y b) se verifique que la diferencia de sus cuadrados sea el número original (es decir, b^2 - a^2 = x).

Definir la función

esDorado :: Integer -> Bool

tales que (esDorado x) se verifica si x es un número dorado. Por ejemplo,

λ> esDorado 2375
True
λ> take 5 [x | x <- [1..], esDorado x]
[48,1023,1404,2325,2375]

Sucesión de cuadrados reducidos

José A. Alonso

Misceláneas

La sucesión de cuadrados de orden n definida a partir de un número x se forma iniciándola en x y, para cada término z el siguiente es el número formado por los n primeros dígitos del cuadrado de z. Por ejemplo, para n = 4 y x = 1111, el primer término de la sucesión es 1111, el segundo es 1234 (ya que 1111^2 = 1234321) y el tercero es 1522 (ya que 1234^2 = 1522756).

Definir la función

sucCuadrados :: Int -> Integer -> [Integer]

tal que (sucCuadrados n x) es la sucesión de cuadrados de orden n definida a partir de x. Por ejemplo,

λ> take 10 (sucCuadrados 4 1111)
[1111,1234,1522,2316,5363,2876,8271,6840,4678,2188]
λ> take 10 (sucCuadrados 3 457)
[457,208,432,186,345,119,141,198,392,153]
λ> take 20 (sucCuadrados 2 55)
[55,30,90,81,65,42,17,28,78,60,36,12,14,19,36,12,14,19,36,12]

Familias de números con algún dígito en común

José A. Alonso

Misceláneas

Una familia de números es una lista de números tal que todos tienen la misma cantidad de dígitos y, además, dichos números tienen al menos un dígito común.

Por ejemplo, los números 72, 32, 25 y 22 pertenecen a la misma familia ya que son números de dos dígitos y todos tienen el dígito 2, mientras que los números 123, 245 y 568 no pertenecen a la misma familia, ya que no hay un dígito que aparezca en los tres números.

Definir la función

esFamilia :: [Integer] -> Bool

tal que (esFamilia ns) se verifica si ns es una familia de números. Por ejemplo,

esFamilia [72, 32, 25, 22]  ==  True
esFamilia [123,245,568]     ==  False
esFamilia [72, 32, 25, 223] ==  False

Estratificación de un árbol

José A. Alonso

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         8   3
    |        /|\       /|\  |
    4       4 5 6     4 5 6 7

se representan por

ej1, ej2, ej3 :: Arbol Int
ej1 = N 1 [N 8 [],N 3 [N 4 []]]
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 []]]

Un estrato de un árbol es la lista de nodos que se encuentran al mismo nivel de profundidad. Por ejemplo, los estratos del árbol ej1 son [1], [8,3] y [4].

Definir la función

estratos :: Arbol a -> [[a]]

tal que (estratos x) es la lista de los estratos del árbol x. Por ejemplo,

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

Terminaciones de Fibonacci

José A. Alonso

Misceláneas

Definir la sucesión

sucFinalesFib :: [(Integer,Integer)]

cuyos elementos son los pares (n,x), donde x es el n-ésimo término de la sucesión de Fibonacci, tales que la terminación de x es n. Por ejemplo,

λ> take 6 sucFinalesFib
[(0,0),(1,1),(5,5),(25,75025),(29,514229),(41,165580141)]
λ> head [(n,x) | (n,x) <- sucFinalesFib, n > 200]
(245,712011255569818855923257924200496343807632829750245)
λ> head [n | (n,_) <- sucFinalesFib, n > 10^4]
10945