Número medio

José A. Alonso

Misceláneas

Un número medio es número natural que es igual a la media aritmética de las permutaciones de sus dígitos. Por ejemplo, 370 es un número medio ya que las permutaciones de sus dígitos es 073, 037, 307, 370, 703 y 730 cuya media es 2220/6 que es igual a 370.

Definir las siguientes funciones

numeroMedio                :: Integer -> Bool
densidadesNumeroMedio      :: [Double]
graficaDensidadNumeroMedio :: Int -> IO ()

tales que

(numeroMedio n) se verifica si n es un número medio. Por ejemplo,

λ> numeroMedio 370
True
λ> numeroMedio 371
False
λ> numeroMedio 485596707818930041152263374
True
λ> filter numeroMedio [100..600]
[111,222,333,370,407,444,481,518,555,592]
λ> filter numeroMedio [3*10^5..6*10^5]
[333333,370370,407407,444444,481481,518518,555555,592592]

densidades es la lista cuyo elemento n-ésimo (empezando a contar en 1) es la densidad de números medios en el intervalo [1,n]; es decir, la cantidad de números medios menores o iguales que n dividida por n. Por ejemplo,

λ> mapM_ print (take 30 densidades)
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0.9
0.9090909090909091
0.8333333333333334
0.7692307692307693
0.7142857142857143
0.6666666666666666
0.625
0.5882352941176471
0.5555555555555556
0.5263157894736842
0.5
0.47619047619047616
0.5
0.4782608695652174
0.4583333333333333
0.44
0.4230769230769231
0.4074074074074074
0.39285714285714285
0.3793103448275862
0.36666666666666664

(graficaDensidadNumeroMedio n) dibuja la gráfica de las densidades de los intervalos [1,k] para k desde 1 hasta n. Por ejemplo, (graficaDensidadNumeroMedio 100) dibuja

Número medio

y (graficaDensidadNumeroMedio 1000) dibuja

Número medio

Tren de potencias

José A. Alonso

Misceláneas

Si n es el número natural cuya expansión decimal es abc... , el tren de potencias de n es a^bc^d... donde el último exponente es 1, si n tiene un número impar de dígitos. Por ejemplo

trenDePotencias 2453  = 2^4*5^3     = 2000
trenDePotencias 24536 = 2^4*5^3*6^1 = 12000

Definir las funciones

trenDePotencias            :: Integer -> Integer
esPuntoFijoTrenDePotencias :: Integer -> Bool
puntosFijosTrenDePotencias :: [Integer]
tablaTrenDePotencias       :: Integer -> Integer -> IO ()

tales que

(trenDePotencias n) es el tren de potencia de n. Por ejemplo.

trenDePotencias 20   ==  1
trenDePotencias 21   ==  2
trenDePotencias 24   ==  16
trenDePotencias 39   ==  19683
trenDePotencias 623  ==  108

(esPuntoFijoTrenDePotencias n) se verifica si n es un punto fijo de trenDePotencias; es decir, (trenDePotencias n) es igual a n. Por ejemplo,

esPuntoFijoTrenDePotencias 2592                        ==  True
esPuntoFijoTrenDePotencias 24547284284866560000000000  ==  True

puntosFijosTrenDePotencias es la lista de los puntso fijos de trenDePotencias. Por ejemplo,

take 10 puntosFijosTrenDePotencias  ==  [1,2,3,4,5,6,7,8,9,2592]

(tablaTrenDePotencias a b) es la tabla de los trenes de potencias de los números entre a y b. Por ejemplo,

λ> tablaTrenDePotencias 20 39
| 20 |     1 |
| 21 |     2 |
| 22 |     4 |
| 23 |     8 |
| 24 |    16 |
| 25 |    32 |
| 26 |    64 |
| 27 |   128 |
| 28 |   256 |
| 29 |   512 |
| 30 |     1 |
| 31 |     3 |
| 32 |     9 |
| 33 |    27 |
| 34 |    81 |
| 35 |   243 |
| 36 |   729 |
| 37 |  2187 |
| 38 |  6561 |
| 39 | 19683 |
λ> tablaTrenDePotencias 2340 2359
| 2340 |        8 |
| 2341 |       32 |
| 2342 |      128 |
| 2343 |      512 |
| 2344 |     2048 |
| 2345 |     8192 |
| 2346 |    32768 |
| 2347 |   131072 |
| 2348 |   524288 |
| 2349 |  2097152 |
| 2350 |        8 |
| 2351 |       40 |
| 2352 |      200 |
| 2353 |     1000 |
| 2354 |     5000 |
| 2355 |    25000 |
| 2356 |   125000 |
| 2357 |   625000 |
| 2358 |  3125000 |
| 2359 | 15625000 |

Comprobar con QuickCheck que entre 2593 y 24547284284866559999999999 la función trenDePotencias no tiene puntos fijos.

Sucesión fractal

José A. Alonso

Misceláneas

La sucesión del reloj astronómico de Praga

José A. Alonso

Misceláneas

La cadena infinita "1234321234321234321...", formada por la repetición de los dígitos 123432, tiene una propiedad (en la que se basa el funcionamiento del reloj astronómico de Praga: la cadena se puede partir en una sucesión de números, de forma que la suma de los dígitos de dichos números es la serie de los números naturales, como se observa a continuación:

1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, ...
1, 2, 3, 4,  5,   6,  7,    8,   9,   10,    11, ...

Definir la lista

reloj :: [Integer]

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

λ> take 11 reloj
[1,2,3,4,32,123,43,2123,432,1234,32123]

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.

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"

Sin ceros consecutivos

José A. Alonso

Misceláneas

Definir la función

sinDobleCero :: Int -> [[Int]]

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

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

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

Valores de polinomios y de expresiones

José A. Alonso

Misceláneas

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

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

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

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

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

Definir las funciones

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

tales que

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

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

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

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

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

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

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

valorP p n == valorE (expresion p) n

Ancestro común más bajo

José A. Alonso

Misceláneas

El tipo de los árboles binarios se define por

data Arbol = H Int
           | N Int Arbol Arbol

Por ejemplo, el árbol

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

se define por

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

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

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

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

Definir la función

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

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

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

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

La regla de los signos de Descartes

José A. Alonso

Misceláneas

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

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

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

Definir las funciones

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

tales que

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

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

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

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

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

Números taxicab

José A. Alonso

Misceláneas

Los números taxicab, taxi-cab o números de Hardy-Ramanujan son aquellos números naturales que pueden expresarse como suma de dos cubos de más de una forma.

Alternativamente, se define al n-ésimo número taxicab como el menor número que es suma de dos cubos de n formas.

Definir las siguientes sucesiones

taxicab  :: [Integer]
taxicab2 :: [Integer]

tales que taxicab es la sucesión de estos números según la primera definición y taxicab2 según la segunda. Por ejemplo,

take 5 taxicab   ==  [1729,4104,13832,20683,32832]
take 2 taxicab2  ==  [2,1729]

Nota 1. La sucesiones taxicab y taxicab2 se corresponden con las sucesiones A001235 y A011541 de la OEIS.

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

Números de Church

José A. Alonso

Misceláneas

Los números naturales pueden definirse de forma alternativa empleando los números de Church. Podemos representar un número natural n como una función que toma una función f como parámetro y devuelve n veces f.

Definimos por tanto los números naturales como

Type Nat = forall a. (a -> a) -> a -> a

De esta forma, para representar el número uno, repetir una vez una función es lo mismo que solamente aplicarla.

uno :: Nat
uno f x = f x

De manera similar, dos debe aplicar f dos veces a su argumento.

dos :: Nat
dos f x = f (f x)

Definir cero equivale por tanto a devolver el argumento sin modificar.

cero :: Nat
cero f x = x

Definir las funciones

cero    :: Nat
uno     :: Nat
dos     :: Nat
tres    :: Nat
nat2Int :: Nat -> Int
succ    :: Nat -> Nat
suma    :: Nat -> Nat -> Nat
mult    :: Nat -> Nat -> Nat
exp     :: Nat -> Nat -> Nat

tales que

cero, uno y dos son definiciones alternativas a las ya dadas y tres es el número natural 3 con esta representación.
(nat2Int n) es el número entero correspondiente al número natuaral n. Por ejemplo,

nat2Int cero == 0
nat2Int uno  == 1
nat2Int dos  == 2
nat2Int tres == 3

(succ n) es el sucesor del número n. Por ejemplo,

nat2Int (succ dos)   ==  3
nat2Int (succ tres)  ==  4

(suma n m) es la suma de n y m. Por ejemplo,

nat2Int (suma dos tres)         ==  5
nat2Int (suma dos (succ tres))  ==  6

(mult n m) es el producto de n y m. Por ejemplo,

nat2Int (mult dos tres)         ==  6
nat2Int (mult dos (succ tres))  ==  8

(exp n m) es la potencia m-ésima de n. Por ejemplo,

nat2Int (exp dos tres)   ==  8
nat2Int (exp tres dos)   ==  9
nat2Int (exp tres cero)  ==  1
nat2Int (exp cero tres)  ==  0

Comprobar con QuickCheck las siguientes propiedades. Para ello importar la librería Test.QuickCheck.Function y seguir el siguiente ejemplo:

prop_Succ1 :: Fun Int Int -> Int -> Bool
prop_Succ1 (Fun _ f) x = succ cero f x == uno f x

succ uno                   = dos
succ dos                   = tres
suma cero uno              = uno
suma dos tres              = suma tres dos
suma (suma dos dos) tres   = suma uno (suma tres tres)
mult uno uno               = uno
mult cero (suma tres tres) = cero
mult dos tres              = suma tres tres
exp dos dos                = suma dos dos
exp tres dos               = suma (mult dos (mult dos dos)) uno
exp tres cero              = uno

Nota 1: Añadir al inicio del archivo del ejercicio los pragmas

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TemplateHaskell #-}

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

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.

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

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

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

Sustitución de pares de elementos consecutivos iguales

José A. Alonso

Misceláneas

Dada una lista xs se reemplaza el primer par de elementos consecutivos iguales x por x+1 y se repite el proceso con las listas obtenidas hasta que no haya ningún par de elementos consecutivos iguales. Por ejemplo, para [5,2,1,1,2,2] se tiene el siguiente proceso

    [5,2,1,1,2,2]
==> [5,2,2,  2,2]
==> [5,3,    2,2]
==> [5,3,    3]
==> [5,4]

Definir la función

sustitucion :: [Int] -> [Int]

tal que (sustitucion xs) es la lista obtenida aplicándole a xs el proceso anterior. Por ejemplo,

sustitucion [5,2,1,1,2,2]         ==  [5,4]
sustitucion [4,2,1,1,2,2]         ==  [5]
sustitucion [4,5,11,2,5,7,2]      ==  [4,5,11,2,5,7,2]
sustitucion (1:[1..2*10^6])       ==  [2000001]
length (sustitucion [1..2*10^6])  ==  2000000

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 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, la reunión 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

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. El coste de cada arista es el cociente entre su mayor 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
coste (2*10^5)  ==  1711798835

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

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

Mayor número de atracciones

José A. Alonso

Misceláneas

En el siguiente gráfico se representa en una cuadrícula el plano de Manhattan. Cada línea es una opción a seguir; el número representa las atracciones que se pueden visitar si se elige esa opción.

     3         2         4         0
* ------- * ------- * ------- * ------- *
|         |         |         |         |
|1        |0        |2        |4        |3
|    3    |    2    |    4    |    2    |
* ------- * ------- * ------- * ------- *
|         |         |         |         |
|4        |6        |5        |2        |1
|    0    |    7    |    3    |    4    |
* ------- * ------- * ------- * ------- *
|         |         |         |         |
|4        |4        |5        |2        |1
|    3    |    3    |    0    |    2    |
* ------- * ------- * ------- * ------- *
|         |         |         |         |
|5        |6        |8        |5        |3
|    1    |    3    |    2    |    2    |
* ------- * ------- * ------- * ------- *

El turista entra por el extremo superior izquierda y sale por el extremo inferior derecha. Sólo puede moverse en las direcciones Sur y Este (es decir, hacia abajo o hacia la derecha).

Representamos el mapa mediante una matriz p tal que p(i,j) = (a,b), donde a = nº de atracciones si se va hacia el sur y b = nº de atracciones si se va al este. Además, ponemos un 0 en el valor del número de atracciones por un camino que no se puede elegir. De esta forma, el mapa anterior se representa por la matriz siguiente:

( (1,3)   (0,2)   (2,4)   (4,0)  (3,0) )
( (4,3)   (6,2)   (5,4)   (2,2)  (1,0) )
( (4,0)   (4,7)   (5,3)   (2,4)  (1,0) )
( (5,3)   (6,3)   (8,0)   (5,2)  (3,0) )
( (0,1)   (0,3)   (0,2)   (0,2)  (0,0) )

En este caso, si se hace el recorrido

[S, E, S, E, S, S, E, E],

el número de atracciones es

1  3  6  7  5  8  2  2

cuya suma es 34.

Definir la función

mayorNumeroV:: M.Matrix (Int,Int) -> Int

tal que (mayorNumeroV p) es el máximo número de atracciones que se pueden visitar en el plano representado por la matriz p. Por ejemplo, si se define la matriz anterior por

ejMapa :: M.Matrix (Int,Int)
ejMapa = M.fromLists [[(1,3),(0,2),(2,4),(4,0),(3,0)],
                      [(4,3),(6,2),(5,4),(2,2),(1,0)],
                      [(4,0),(4,7),(5,3),(2,4),(1,0)],
                      [(5,3),(6,3),(8,0),(5,2),(3,0)],
                      [(0,1),(0,3),(0,2),(0,2),(0,0)]]

entonces

mayorNumeroV ejMapa                                     ==  34
mayorNumeroV (fromLists [[(1,3),(0,0)],[(0,3),(0,0)]])  ==  4
mayorNumeroV (fromLists [[(1,3),(6,0)],[(0,3),(0,0)]])  ==  9

Para los siguientes ejemplos se define un generador de mapas

genMapa :: Int -> Matrix (Int,Int)
genMapa n =
extendTo (0,0) n n (fromList (n-1) (n-1) [(k,k+1) | k <- [1..]])

Entonces,

mayorNumeroV (genMapa 10)  ==  962
mayorNumeroV (genMapa 500)  ==  185880992

Números construidos con los dígitos de un conjunto dado

José A. Alonso

Misceláneas

Definir las siguientes funciones

numerosCon      :: [Integer] -> [Integer]
numeroDeDigitos :: [Integer] -> Int -> Int

tales que

(numerosCon ds) es la lista de los números que se pueden construir con los dígitos de ds (cuyos elementos son distintos elementos del 1 al 9) . Por ejemplo,

λ> take 22 (numerosCon [1,4,6,9])
[1,4,6,9,11,14,16,19,41,44,46,49,61,64,66,69,91,94,96,99,111,114]
λ> take 15 (numerosCon [4,6,9])
[4,6,9,44,46,49,64,66,69,94,96,99,444,446,449]
λ> take 15 (numerosCon [6,9])
[6,9,66,69,96,99,666,669,696,699,966,969,996,999,6666]

(numeroDeDigitos ds k) es el número de dígitos que tiene el k-ésimo elemento (empezando a contar en 0) de la sucesión (numerosCon ds). Por ejemplo,

numeroDeDigitos [1,4,6,9]   3  ==  1
numeroDeDigitos [1,4,6,9]   6  ==  2
numeroDeDigitos [1,4,6,9]  22  ==  3
numeroDeDigitos [4,6,9]    15  ==  3
numeroDeDigitos [6,9]      15  ==  4
numeroDeDigitos [1,4,6,9] (10^(10^5))  ==  166097
numeroDeDigitos   [4,6,9] (10^(10^5))  ==  209590
numeroDeDigitos     [6,9] (10^(10^5))  ==  332192

Número de triangulaciones de un polígono

José A. Alonso

Misceláneas

Una triangulación de un polígono es una división del área en un conjunto de triángulos, de forma que la unión de todos ellos es igual al polígono original, y cualquier par de triángulos es disjunto o comparte únicamente un vértice o un lado. En el caso de polígonos convexos, la cantidad de triangulaciones posibles depende únicamente del número de vértices del polígono.

Si llamamos T(n) al número de triangulaciones de un polígono de n vértices, se verifica la siguiente relación de recurrencia:

T(2) = 1
T(n) = T(2)*T(n-1) + T(3)*T(n-2) + ... + T(n-1)*T(2)

Definir la función

numeroTriangulaciones :: Integer -> Integer

tal que (numeroTriangulaciones n) es el número de triangulaciones de un polígono convexo de n vértices. Por ejemplo,

numeroTriangulaciones 3  == 1
numeroTriangulaciones 5  == 5
numeroTriangulaciones 6  == 14
numeroTriangulaciones 7  == 42
numeroTriangulaciones 50 == 131327898242169365477991900
length (show (numeroTriangulaciones   800)) ==  476
length (show (numeroTriangulaciones  1000)) ==  597
length (show (numeroTriangulaciones 10000)) == 6014

Sucesiones suaves

José A. Alonso

Misceláneas

Una sucesión es suave si valor absoluto de la diferencia de sus términos consecutivos es 1.

Definir la función

suaves :: Int -> [[Int]]

tal que (suaves n) es la lista de las sucesiones suaves de longitud n cuyo último término es 0. Por ejemplo,

suaves 2  ==  [[1,0],[-1,0]]
suaves 3  ==  [[2,1,0],[0,1,0],[0,-1,0],[-2,-1,0]]

Máximos de expresiones aritméticas

José A. Alonso

Misceláneas

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

data Expr = N Int
          | X
          | S Expr Expr
          | R Expr Expr
          | P Expr Expr
          | E Expr Int
          deriving (Eq, Show)

Por ejemplo, la expresión

3*x - (x+2)^7

se puede definir por

R (P (N 3) X) (E (S X (N 2)) 7)

Definir la función

maximo :: Expr -> [Int] -> (Int,[Int])

tal que (maximo e xs) es el par formado por el máximo valor de la expresión e para los puntos de xs y en qué puntos alcanza el máximo. Por ejemplo,

λ> maximo (E (S (N 10) (P (R (N 1) X) X)) 2) [-3..3]
(100,[0,1])

Clausura respecto de una operación binaria

José A. Alonso

Misceláneas

Se dice que una operador @ es interno en un conjunto A si al @ sobre elementos de A se obtiene como resultado otro elemento de A. Por ejemplo, la suma es un operador interno en el conjunto de los números naturales pares.

La clausura de un conjunto A con respecto a un operador @ es el menor conjunto B tal que A está contenido en B y el operador @ es interno en el conjunto B. Por ejemplo, la clausura del conjunto {2} con respecto a la suma es el conjunto de los números pares positivos:

{2, 4, 6, 8, ...} = {2*k | k <- [1..]}

Definir la función

clausuraOperador :: (Int -> Int -> Int) -> Set Int -> Set Int

tal que (clausuraOperador op xs) es la clausura del conjunto xs con respecto a la operación op. Por ejemplo,

clausuraOperador gcd (fromList [6,9,10])     ==
   fromList [1,2,3,6,9,10]
clausuraOperador gcd (fromList [42,70,105])  ==
   fromList [7,14,21,35,42,70,105]
clausuraOperador lcm (fromList [6,9,10])     ==
   fromList [6,9,10,18,30,90]
clausuraOperador lcm (fromList [2,3,5,7])    ==
   fromList [2,3,5,6,7,10,14,15,21,30,35,42,70,105,210]

Polinomio digital

José A. Alonso

Misceláneas

Definir la función

polinomioDigital :: Int -> Polinomio Int

tal que (polinomioDigital n) es el polinomio cuyos coeficientes son los dígitos de n. Por ejemplo,

λ> polinomioDigital 5703
5*x^3 + 7*x^2 + 3

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería [[https://hackage.haskell.org/package/I1M-0.2.2/docs/I1M-Pol.html][I1M.Pol]].

Las sucesiones de Loomis

José A. Alonso

Misceláneas

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

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

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

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

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

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

Definir las siguientes funciones

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

tales que

(sucLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

λ> take 15 (sucLoomis 1)
[1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 2)
[2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 3)
[3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
λ> take 15 (sucLoomis 4)
[4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
λ> take 15 (sucLoomis 5)
[5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
λ> take 15 (sucLoomis 20)
[20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
λ> take 15 (sucLoomis 100)
[100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
λ> sucLoomis 1 !! (2*10^5)
235180736652

(convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

convergencia  2      ==  2
convergencia  3      ==  26
convergencia  4      ==  4
convergencia 17      ==  38
convergencia 19      ==  102
convergencia 43      ==  162
convergencia 27      ==  202
convergencia 58      ==  474
convergencia 63      ==  150056
convergencia 81      ==  150056
convergencia 89      ==  150056
convergencia (10^12) ==  1000101125092

(graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja

Las sucesiones de Loomis

y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja

Las sucesiones de Loomis

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]

Diccionario inverso

José A. Alonso

Misceláneas

El inverso de un diccionario d es el diccionario que a cada valor x le asigna la lista de claves cuyo valor en d es x. Por ejemplo, el inverso de

[("a",3),("b",2),("c",3),("d",2),("e",1)])

es

[(1,["e"]),(2,["d","b"]),(3,["c","a"])]

Definir la función

inverso :: (Ord k, Ord v) => Map k v -> Map v [k]

tal que (inverso d) es el inverso del diccionario d. Por ejemplo,

λ> inverso (fromList [("a",3),("b",2),("c",3),("d",2),("e",1)])
fromList [(1,["e"]),(2,["d","b"]),(3,["c","a"])]
λ> inverso (fromList [(x,x^2) | x <- [-3,-2..3]])
fromList [(0,[0]),(1,[1,-1]),(4,[2,-2]),(9,[3,-3])]

Subconjuntos con suma dada

José A. Alonso

Misceláneas

Sea S un conjunto finito de números enteros positivos y n un número natural. El problema consiste en calcular los subconjuntos de S cuya suma es n.

Definir la función

subconjuntosSuma:: [Int] -> Int -> [[Int]] tal que

tal que (subconjuntosSuma xs n) es la lista de los subconjuntos de xs cuya suma es n. Por ejemplo,

λ> subconjuntosSuma [3,34,4,12,5,2] 9
[[4,5],[3,4,2]]
λ> subconjuntosSuma [3,34,4,12,5,2] 13
[]
λ> length (subconjuntosSuma [1..100] (sum [1..100]))
1

Sumas de subconjuntos

José A. Alonso

Misceláneas

Definir la función

sumasSubconjuntos :: Set Int -> Set Int

tal que (sumasSubconjuntos xs) es el conjunto de las sumas de cada uno de los subconjuntos de xs. Por ejemplo,

λ> sumasSubconjuntos (fromList [3,2,5])
fromList [0,2,3,5,7,8,10]
λ> length (sumasSubconjuntos (fromList [-40,-39..40]))
1641

Subsucesiones crecientes de elementos consecutivos

José A. Alonso

Misceláneas

Definir la función

subsucesiones :: [Integer] -> [[Integer]]

tal que (subsucesiones xs) es la lista de las subsucesiones crecientes de elementos consecutivos de xs. Por ejemplo,

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

Números compuestos por un conjunto de primos

José A. Alonso

Misceláneas

Los números compuestos por un conjunto de primos son los números cuyos factores primos pertenecen al conjunto. Por ejemplo, los primeros números compuestos por [2,5,7] son

1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,...

El 28 es compuesto ya que sus divisores primos son 2 y 7 que están en [2,5,7].

Definir la función

compuestos :: [Integer] -> [Integer]

tal que (compuesto ps) es la lista de los números compuestos por el conjunto de primos ps. Por ejemplo,

λ> take 20 (compuestos [2,5,7])
[1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70]
λ> take 20 (compuestos [2,5])
[1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250]
λ> take 20 (compuestos [2,3,5])
[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
λ> take 20 (compuestos [3,5,7,11,13])
[1,3,5,7,9,11,13,15,21,25,27,33,35,39,45,49,55,63,65,75]
λ> take 15 (compuestos [2])
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
λ> compuestos [2,7] !! (10^4)
57399514149595471961908157955229677377312712667508119466382354072731648
λ> compuestos [2,3,5] !! (10^5)
290237644800000000000000000000000000000

Notas de evaluación acumulada

José A. Alonso

Misceláneas

La evaluación acumulada, las notas se calculan recursivamente con la siguiente función

N(1) = E(1)
N(k) = máximo(E(k), 0.4*N(k-1)+0.6*E(k))

donde E(k) es la nota del examen k. Por ejemplo, si las notas de los exámenes son [3,7,6,3] entonces las acumuladas son [3.0,7.0,6.4,4.4]

Las notas e los exámenes se encuentran en ficheros CSV con los valores separados por comas. Cada línea representa la nota de un alumno, el primer valor es el identificador del alumno y los restantes son sus notas. Por ejemplo, el contenido de examenes.csv es

juaruigar,3,7,9,3
evadialop,3,6,7,4
carrodmes,0,9,8,7

Definir las funciones

acumuladas      :: [Double] -> [Double]
notasAcumuladas :: FilePath -> FilePath -> IO ()

tales que

(acumuladas xs) es la lista de las notas acumuladas (redondeadas con un decimal) de los notas de los exámenes xs. Por ejemplo,

acumuladas [2,5]      ==  [2.0,5.0]
acumuladas [5,2]      ==  [5.0,3.2]
acumuladas [3,7,6,3]  ==  [3.0,7.0,6.4,4.4]
acumuladas [3,6,7,3]  ==  [3.0,6.0,7.0,4.6]

(notasAcumuladas f1 f2) que escriba en el fichero f2 las notas acumuladas correspondientes a las notas de los exámenes del fichero f1. Por ejemplo, al evaluar

notasAcumuladas "examenes.csv" "acumuladas.csv"

escribe en el fichero acumuladas.csv

juaruigar,3.0,7.0,9.0,5.4
evadialop,3.0,6.0,7.0,5.2
carrodmes,0.0,9.0,8.4,7.6

Reducción de opuestos

José A. Alonso

Misceláneas

Se considera el siguiente procedimiento de reducción de listas: busca un par de elementos consecutivos iguales pero con signos opuestos, se eliminan dichos elementos y se continúa el proceso hasta que no se encuentren pares de elementos consecutivos iguales pero con signos opuestos. Por ejemplo, la reducción de [-2,1,-1,2,3,4,-3] es

[-2,1,-1,2,3,4,-3]    (se elimina el par (1,-1))
-> [-2,2,3,4,-3]      (se elimina el par (-2,2))
-> [3,4,-3]           (el par (3,-3) no son consecutivos)

Definir la función

reducida :: [Int] -> [Int]

tal que (reducida xs) es la lista obtenida aplicando a xs el de eliminación de pares de elementos consecutivos opuestos. Por ejemplo,

reducida [-2,1,-1,2,3,4,-3]           == [3,4,-3]
reducida [-2,1,-1,2,3,-4,4,-3]        == []
reducida [-2,1,-1,2,5,3,-4,4,-3]      == [5]
reducida [-2,1,-1,2,5,3,-4,4,-3,-5]   == []

Matrices de Hadamard

José A. Alonso

Misceláneas

Las matrices de Hadamard se definen recursivamente como sigue

λ> hadamard 0
( 1 )

λ> hadamard 1
(  1  1 )
(  1 -1 )

λ> hadamard 2
(  1  1  1  1 )
(  1 -1  1 -1 )
(  1  1 -1 -1 )
(  1 -1 -1  1 )

λ> hadamard 3
(  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 -1  1 -1  1 )
(  1  1 -1 -1 -1 -1  1  1 )
(  1 -1 -1  1 -1  1  1 -1 )

En general, la n-ésima matriz de Hadamard, H(n), es

( H(n-1)  H(n-1) )
( H(n-1) -H(n-1) )

Definir la función

hadamard :: Int -> Matrix Int

tal que (hadamard n) es la n-ésima matriz de Hadamard.

Comprobar con QuickCheck que para todo número natural n, el producto de la n-ésima matriz de Hadamard y su traspuesta es igual al producto de 2^n por la matriz identidad de orden 2^n.

Decidir si existe un subconjunto con suma dada

José A. Alonso

Misceláneas

Sea S un conjunto finito de números naturales y m un número natural. El problema consiste en determinar si existe un subconjunto de S cuya suma es m. Por ejemplo, si S = [3,34,4,12,5,2] y m = 9, existe un subconjunto de S, [4,5], cuya suma es 9. En cambio, no hay ningún subconjunto de S que sume 13.

Definir la función

existeSubSuma :: [Int] -> Int -> Bool

tal que (existeSubSuma xs m) se verifica si existe algún subconjunto de xs que sume m. Por ejemplo,

existeSubSuma [3,34,4,12,5,2] 9                == True
existeSubSuma [3,34,4,12,5,2] 13               == False
existeSubSuma ([3,34,4,12,5,2]++[20..400]) 13  == False
existeSubSuma ([3,34,4,12,5,2]++[20..400]) 654 == True
existeSubSuma [1..200] (sum [1..200])          == True

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

Nota. Se puede comprobar la función mediante The pi-search page o Pi search engine.

Números superpares

José A. Alonso

Misceláneas

Definir la función

superpar :: Int -> Bool

tal que (superpar n) se verifica si n es un número par tal que todos sus dígitos son pares. Por ejemplo,

superpar 426  ==  True
superpar 456  ==  False

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

Alturas primas

José A. Alonso

Misceláneas

Se considera una enumeración de los números primos:

p(1)=2,  p(2)=3, p(3)=5, p(4)=7, p(5)=11, p(6)=13, p(7)=17,...

Dado un entero x > 1, su altura prima es el mayor i tal que el primo p(i) aparece en la factorización de x en números primos. Por ejemplo, la altura prima de 3500 tiene longitud 4, pues 3500=2^2x5^3x7^1 y la de 34 tiene es 7, pues 34 = 2x17. Además, se define la altura prima de 1 como 0.

Definir las funciones

alturaPrima        :: Integer -> Integer
alturasPrimas      :: Integer -> [Integer]
graficaAlturaPrima :: Integer -> IO ()

tales que

(alturaPrima x) es la altura prima de x. Por ejemplo,

alturaPrima 3500  ==  4
alturaPrima 34    ==  7

(alturasPrimas n) es la lista de las altura prima de los primeros n números enteros positivos. Por ejemplo,

alturasPrimas 15  ==  [0,1,2,1,3,2,4,1,2,3,5,2,6,4,3]
maximum (alturasPrimas 10000)  ==  1229
maximum (alturasPrimas 20000)  ==  2262
maximum (alturasPrimas 30000)  ==  3245
maximum (alturasPrimas 40000)  ==  4203

(graficaAlturaPrima n) dibuja las alturas primas de los números entre 2 y n. Por ejemplo, (graficaAlturaPrima 500) dibuja

Alturas primas

Ampliación de árboles binarios

José A. Alonso

Misceláneas

Representamos los árboles binarios mediante el tipo de dato

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

Una forma de ampliar un árbol binario es añadiendo un nuevo nivel donde las nuevas hojas sean iguales a la suma de los valores de los nodos desde el padre hasta llegar a la raíz (inclusives). Por ejemplo:

  5               5       |         3                3
 / \             / \      |        / \             /   \
2   0    ==>    2   0     |       2   4    ==>    2     4
               / \ / \    |      / \             / \   / \
              7  7 5  5   |     0   1           0   1 7   7
                                               /\   /\
                                              5  5 6  6

Definir la función

ampliaArbol:: Num a => Arbol a -> Arbol a

tal que (ampliaArbol a) es el árbol a ampliado en un nivel. Por ejemplo,

λ> ampliaArbol (N 5 (H 2)(H 0))
N 5 (N 2 (H 7) (H 7)) (N 0 (H 5) (H 5))
λ> ampliaArbol (N 3 (N 2 (H 0) (H 1)) (H 4))
N 3 (N 2 (N 0 (H 5) (H 5)) (N 1 (H 6) (H 6))) (N 4 (H 7) (H 7))
λ> ampliaArbol (H 1)
N 1 (H 1) (H 1)
λ> ampliaArbol N 1 (H 1) (H 1)
N 1 (N 1 (H 2) (H 2)) (N 1 (H 2) (H 2))

Diccionario de frecuencias

José A. Alonso

Misceláneas

Definir la función

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

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

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

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

La carrera de Collatz

José A. Alonso

Misceláneas

Sea f la siguiente función, aplicable a cualquier número entero positivo:

Si el número es par, se divide entre 2.
Si el número es impar, se multiplica por 3 y se suma 1.

La carrera de Collatz consiste en, dada una lista de números ns, sustituir cada número n de ns por f(n) hasta que alguno sea igual a 1. Por ejemplo, la siguiente sucesión es una carrera de Collatz

[ 3, 6,20, 49, 73]
[10, 3,10,148,220]
[ 5,10, 5, 74,110]
[16, 5,16, 37, 55]
[ 8,16, 8,112,166]
[ 4, 8, 4, 56, 83]
[ 2, 4, 2, 28,250]
[ 1, 2, 1, 14,125]

En esta carrera, los ganadores son 3 y 20.

Definir la función

ganadores :: [Int] -> [Int]

tal que (ganadores ns) es la lista de los ganadores de la carrera de Collatz a partir de la lista inicial ns. Por ejmplo,

ganadores [3,6,20,49,73]  ==  [3,20]

Mayor número obtenido intercambiando dos dígitos

José A. Alonso

Misceláneas

Definir la función

maximoIntercambio :: Int -> Int

tal que (maximoIntercambio x) es el máximo número que se puede obtener intercambiando dos dígitos de x. Por ejemplo,

maximoIntercambio 983562  ==  986532
maximoIntercambio 31524   ==  51324
maximoIntercambio 897     ==  987

Sucesión de antecesores y sucesores

José A. Alonso

Misceláneas

Definir la lista

antecesoresYsucesores :: [[Integer]]

cuyos elementos son

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

donde cada una de las listas se obtiene de la anterior sustituyendo cada elemento por su antecesor y su sucesor; es decir, el 1 por el 0 y el 2, el 0 por el -1 y el 1, el 2 por el 1 y el 3, etc. Por ejemplo,

λ> take 4 antecesoresYsucesores
[[1],[0,2],[-1,1,1,3],[-2,0,0,2,0,2,2,4]]

Comprobar con Quickcheck que la suma de los elementos de la lista n-ésima de antecesoresYsucesores es 2^n.

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

quickCheckWith (stdArgs {maxSize=7}) prop_suma

Árbol de subconjuntos

José A. Alonso

Misceláneas

Definir las siguientes funciones

arbolSubconjuntos       :: [a] -> Tree [a]
nNodosArbolSubconjuntos :: Integer -> Integer
sumaNNodos              :: Integer -> Integer

tales que

(arbolSubconjuntos xs) es el árbol de los subconjuntos de xs. Por ejemplo.

λ> putStrLn (drawTree (arbolSubconjuntos "abc"))
abc
|
+- bc
|  |
|  +- c
|  |
|  `- b
|
+- ac
|  |
|  +- c
|  |
|  `- a
|
`- ab
   |
   +- b
   |
   `- a

(nNodosArbolSubconjuntos xs) es el número de nodos del árbol de xs. Por ejemplo

nNodosArbolSubconjuntos "abc"  ==  10
nNodosArbolSubconjuntos [1..4*10^4] `mod` (7+10^9) == 546503960

(sumaNNodos n) es la suma del número de nodos de los árboles de los subconjuntos de [1..k] para 1 <= k <= n. Por ejemplo,

λ> sumaNNodos 3  ==  14
sumaNNodos (4*10^4) `mod` (7+10^9)  ==  249479844

Sucesiones de números consecutivos con suma dada

José A. Alonso

Misceláneas

El número 15 se puede escribir de 5 formas como suma de números naturales consecutivos:

15 = 0+1+2+3+4+5 = 1+2+3+4+5 = 4+5+6 = 7+8 = 15.

Definir las funciones

sucesionesConSuma        :: Int -> [(Int,Int)]
graficaSucesionesConSuma :: Int -> IO ()

tales que

(sucesionesConSuma n) es la lista de los pares formados por el primero y por el último elemento de las sucesiones de números naturales consecutivos con suma n. Por ejemplo,

sucesionesConSuma 15             ==  [(0,5),(1,5),(4,6),(7,8),(15,15)]
length (sucesionesConSuma 3000)  ==  8

(graficaSucesionesConSuma n) dibuja la gráfica del número de formas de escribir los n primeros números como suma de números naturales consecutivos. Por ejemplo, (graficaSucesionesConSuma 100) dibuja

Sucesiones de números consecutivos con suma dada

Operaciones binarias con matrices

José A. Alonso

Misceláneas

Entre dos matrices de la misma dimensión se pueden aplicar distintas operaciones binarias entre los elementos en la misma posición. Por ejemplo, si a y b son las matrices

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

entonces a+b y a-b son, respectivamente

|4 8 8|     |2 0 4|
|7 7 9|     |3 5 5

Definir la función

opMatriz :: (Int -> Int -> Int) ->
Matriz Int -> Matriz Int -> Matriz Int

tal que (opMatriz f p q) es la matriz obtenida aplicando la operación f entre los elementos de p y q de la misma posición. Por ejemplo,

λ> a = listArray ((1,1),(2,3)) [3,4,6,5,6,7]
λ> b = listArray ((1,1),(2,3)) [1,4,2,2,1,2]
λ> elems (opMatriz (+) a b)
[4,8,8,7,7,9]
λ> elems (opMatriz max a b)
[3,4,6,5,6,7]
λ> c = listArray ((1,1),(2,2)) ["ab","c","d","ef"]
λ> d = listArray ((1,1),(2,2)) [3,1,0,5]
λ> elems (opMatriz menor c d)
[True,False,False,True]

Números tetranacci

José A. Alonso

Misceláneas

Los números tetranacci son una generalización de los números de Fibonacci definidos por

T(0) = 0,
T(1) = 1,
T(2) = 1,
T(3) = 2,
T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4), para n > 3.

Los primeros números tetranacci son

0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208

Definir las funciones

tetranacci        :: Int -> Integer
graficaTetranacci :: Int -> IO ()

tales que

(tetranacci n) es el n-ésimo número tetranacci. Por ejemplo,

λ> tetranacci 10
208
λ> map tetranacci [0..10]
[0,1,1,2,4,8,15,29,56,108,208]
λ> length (show (tetranacci5 (10^5)))
28501

(graficaTetranacci n) dibuja la gráfica de los cocientes de n primeros pares de número tetranacci. Por ejemplo, (graficaTetranacci 300) dibuja

Números tetranacci

Múltiplos repitunos

José A. Alonso

Misceláneas

El ejercicio 4 de la Olimpiada Matemáticas de 1993 es el siguiente:

Demostrar que para todo número primo p distinto de 2 y de 5, existen infinitos múltiplos de p de la forma 1111......1 (escrito sólo con unos).

Definir la función

multiplosRepitunos :: Integer -> Integer -> [Integer]

tal que (multiplosRepitunos p n) es la lista de los múltiplos repitunos de p (es decir, de la forma 1111...1 escrito sólo con unos), donde p es un número primo distinto de 2 y 5. Por ejemplo,

head (multiplosRepitunos  7 10)       == 111111
head (multiplosRepitunos  7 (10^10))  == 111111111111
head (multiplosRepitunos  7 (10^20))  == 111111111111111111111111
head (multiplosRepitunos 19 (10^10))  == 111111111111111111

Comprobar con QuickCheck que para todo primo p mayor que 5 y todo número entero positivo n, existe un mútiplo repituno de p mayor que n.

Máxima longitud de sublistas crecientes

José A. Alonso

Misceláneas

Definir la función

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

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

λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
3
λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
6
λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
6
λ> longitudMayorSublistaCreciente [1..2000]
2000
λ> longitudMayorSublistaCreciente [2000,1999..1]
1
λ> import System.Random
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> longitudMayorSublistaCreciente2 xs
61
λ> longitudMayorSublistaCreciente3 xs
61

Mayores sublistas crecientes

José A. Alonso

Misceláneas

Definir la función

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

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

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

Conjetura de Goldbach

José A. Alonso

Misceláneas

Una forma de la conjetura de Golbach afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres números primos.

Si se define el índice de Goldbach de n > 1 como la mínima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de Goldbach afirma que todos los índices de Goldbach de los enteros mayores que 1 son menores que 4.

Definir las siguientes funciones

indiceGoldbach  :: Int -> Int
graficaGoldbach :: Int -> IO ()

tales que

(indiceGoldbach n) es el índice de Goldbach de n. Por ejemplo,

indiceGoldbach 2                        ==  1
indiceGoldbach 4                        ==  2
indiceGoldbach 27                       ==  3
sum (map indiceGoldbach [2..5000])      ==  10619
maximum (map indiceGoldbach [2..5000])  ==  3

(graficaGoldbach n) dibuja la gráfica de los índices de Goldbach de los números entre 2 y n. Por ejemplo, (graficaGoldbach 150) dibuja

Conjetura de Goldbach

Comprobar con QuickCheck la conjetura de Goldbach anterior.

Particiones primas

José A. Alonso

Misceláneas

Una partición prima de un número natural n es un conjunto de primos cuya suma es n. Por ejemplo, el número 7 tiene 7 particiones primas ya que

7 = 7 = 5 + 2 = 3 + 2 + 2

Definir la función

particiones :: Int -> [[Int]]

tal que (particiones n) es el comjunto de las particiones primas de n. Por ejemplo,

particiones 7             ==  [[7],[5,2],[3,2,2]]
particiones 8             ==  [[5,3],[3,3,2],[2,2,2,2]]
particiones 9             ==  [[7,2],[5,2,2],[3,3,3],[3,2,2,2]]
length (particiones 100)  ==  40899

La sucesión de Sylvester

José A. Alonso

Misceláneas

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

sylvester        :: Integer -> Integer
graficaSylvester :: Integer -> Integer -> IO ()

tales que

(sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,

λ> [sylvester n | n <- [0..7]]
[2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
λ> length (show (sylvester 25))
6830085

(graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
(graficaSylvester 3 30) dibuja
(graficaSylvester 4 30) dibuja
(graficaSylvester 5 30) dibuj4

Camino de máxima suma en una matriz

José A. Alonso

Misceláneas

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

(  1  6 11  2 )
(  7 12  3  8 )
(  3  8  4  9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El camino de máxima suma es el segundo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

caminoMaxSuma :: Matrix Int -> [Int]

tal que (caminoMaxSuma m) es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[1,7,12,8,4,9]
λ> sum (caminoMaxSuma (fromList 500 500 [1..]))
187001249

Máximo de las sumas de los caminos en una matriz

José A. Alonso

Misceláneas

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

(  1  6 11  2 )
(  7 12  3  8 )
(  3  8  4  9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El máximo de las suma de los caminos es 41.

Definir la función

maximaSuma :: Matrix Int -> Int

tal que (maximaSuma m) es el máximo de las sumas de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
41
λ> maximaSuma (fromList 800 800 [1..])
766721999

Caminos en una matriz

José A. Alonso

Misceláneas

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

(  1  6 11  2 )
(  7 12  3  8 )
(  3  8  4  9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Definir la función

caminos :: Matrix Int -> [[Int]]

tal que (caminos m) es la lista de los caminos en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[[1,7, 3,8,4,9],
[1,7,12,8,4,9],
[1,7,12,3,4,9],
[1,7,12,3,8,9],
[1,6,12,8,4,9],
[1,6,12,3,4,9],
[1,6,12,3,8,9],
[1,6,11,3,4,9],
[1,6,11,3,8,9],
[1,6,11,2,8,9]]
λ> length (caminos (fromList 12 13 [1..]))
1352078

Suma de las alturas de los nodos de un árbol

José A. Alonso

Misceláneas

Las árboles binarios se pueden representar con el siguiente tipo

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

Por ejemplo, el árbol

se representa por

ej1 :: Arbol Int
ej1 = N 1 (N 2 (N 4 H H) (N 5 H H)) (N 3 H H)

La altura de cada elemento del árbol es la máxima distancia a las hojas en su rama. Por ejemplo, en el árbol anterior, la altura de 1 es 3, la de 2 es 2, la de 3 es 1, la de 4 es 1 y la de 5 es 1.

Definir la función

sumaAlturas :: Arbol t -> Int

tal que (sumaAlturas a) es la suma de las alturas de los elementos de a. Por ejemplo,

λ> sumaAlturas (N 1 (N 2 (N 4 H H) (N 5 H H)) (N 3 H H))
8
λ> sumaAlturas (N 1 (N 2 (N 4 H H) H) (N 3 H H))
7
λ> sumaAlturas (N 1 (N 2 (N 4 H H) H) (N 2 (N 4 H H) (N 5 H H)))
10

La conjetura de Levy

José A. Alonso

Misceláneas

Hyman Levy observó que

 7 = 3 + 2 x 2
 9 = 3 + 2 x 3 =  5 + 2 x 2
11 = 5 + 2 x 3 =  7 + 2 x 2
13 = 3 + 2 x 5 =  7 + 2 x 3
15 = 3 + 2 x 5 = 11 + 2 x 2
17 = 3 + 2 x 7 =  7 + 2 x 5 = 11 + 2 x 3 = 13 + 2 x 2
19 = 5 + 2 x 7 = 13 + 2 x 3

y conjeturó que todos los número impares mayores o iguales que 7 se pueden escribir como la suma de un primo y el doble de un primo. El objetivo de los siguientes ejercicios es comprobar la conjetura de Levy.

Definir las siguientes funciones

descomposicionesLevy :: Integer -> [(Integer,Integer)]
graficaLevy          :: Integer -> IO ()

tales que

(descomposicionesLevy x) es la lista de pares de primos (p,q) tales que x = p + 2q. Por ejemplo,

descomposicionesLevy  7  ==  [(3,2)]
descomposicionesLevy  9  ==  [(3,3),(5,2)]
descomposicionesLevy 17  ==  [(3,7),(7,5),(11,3),(13,2)]

(graficaLevy n) dibuja los puntos (x,y) tales que x pertenece a [7,9..7+2x(n-1)] e y es el número de descomposiciones de Levy de x. Por ejemplo, (graficaLevy 200) dibuja

La conjetura de Levy

Comprobar con QuickCheck la conjetura de Levy.

Matrices de Pascal

José A. Alonso

Misceláneas

El triángulo de Pascal es un triángulo de números

       1
      1 1
     1 2 1
   1  3 3  1
  1 4  6  4 1
 1 5 10 10 5 1
...............

construido de la siguiente forma

la primera fila está formada por el número 1;
las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

La matriz de Pascal es la matriz cuyas filas son los elementos de la correspondiente fila del triángulo de Pascal completadas con ceros. Por ejemplo, la matriz de Pascal de orden 6 es

|1 0  0  0 0 0|
|1 1  0  0 0 0|
|1 2  1  0 0 0|
|1 3  3  1 0 0|
|1 4  6  4 1 0|
|1 5 10 10 5 1|

Definir la función

matrizPascal :: Int -> Matrix Integer

tal que (matrizPascal n) es la matriz de Pascal de orden n. Por ejemplo,

λ> matrizPascal 6
(  1  0  0  0  0  0 )
(  1  1  0  0  0  0 )
(  1  2  1  0  0  0 )
(  1  3  3  1  0  0 )
(  1  4  6  4  1  0 )
(  1  5 10 10  5  1 )

La conjetura de Gilbreath

José A. Alonso

Misceláneas

Partiendo de los 5 primeros números primos y calculando el valor absoluto de la diferencia de cada dos números consecutivos hasta quedarse con un único número se obtiene la siguiente tabla:

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

Se observa que todas las filas, salvo la inicial, comienzan con el número 1.

Repitiendo el proceso pero empezando con los 8 primeros números primos se obtiene la siguiente tabla:

2, 3, 5, 7, 11, 13, 17, 19
1, 2, 2, 4,  2,  4,  2
1, 0, 2, 2,  2,  2
1, 2, 0, 0,  0
1, 2, 0, 0
1, 2, 0
1, 2
1

Se observa que, de nuevo, todas las filas, salvo la inicial, comienza con el número 1.

La conjetura de Gilbreath afirma que si escribimos la sucesión de números primos completa y después construimos las correspondientes sucesiones formadas por el valor absoluto de la resta de cada pareja de números consecutivos, entonces todas esas filas que obtenemos comienzan siempre por 1.

El objetivo de este ejercicio es comprobar experimentalmente dicha conjetura.

Para la representación, usaremos la simétrica de la que hemos comentado anteriormente; es decir,

 2
 3, 1
 5, 2, 1
 7, 2, 0, 1
11, 4, 2, 2, 1
13, 2, 2, 0, 2, 1
17, 4, 2, 0, 0, 2, 1
19, 2, 2, 0, 0, 0, 2, 1

en la que la primera columna son los números primos y el elemento de la fila i y columna j (con i, j > 1) es el valor absoluto de la diferencia de los elementos (i,j-1) e (i-1,j-1).

Definir las siguientes funciones

siguiente           :: Integer -> [Integer] -> [Integer]
triangulo           :: [[Integer]]
conjetura_Gilbreath :: Int -> Bool

tales que

(siguiente x ys) es la línea siguiente de la ys que empieza por x en la tabla de Gilbreath; es decir, si ys es [y1,y2,...,yn], entonces (siguiente x ys) es [x,|y1-x|,|y2-|y1-x||,...] Por ejemplo,

siguiente  7 [5,2,1]               ==  [7,2,0,1]
siguiente 29 [23,4,2,0,0,0,0,2,1]  ==  [29,6,2,0,0,0,0,0,2,1]

triangulo es el triángulo de Gilbreath. Por ejemplo,

λ> take 10 triangulo
[[ 2],
[ 3,1],
[ 5,2,1],
[ 7,2,0,1],
[11,4,2,2,1],
[13,2,2,0,2,1],
[17,4,2,0,0,2,1],
[19,2,2,0,0,0,2,1],
[23,4,2,0,0,0,0,2,1],
[29,6,2,0,0,0,0,0,2,1]]

(conjeturaGilbreath n) se verifica si se cumple la conjetura de Gilbreath para los n primeros números primos; es decir, en el triángulo de Gilbreath cuya primera columna son los n primeros números primos, todas las filas a partir de la segunda terminan en 1. Por ejemplo,

λ> conjeturaGilbreath 1000
True

Suma de las sumas de los cuadrados de los divisores

José A. Alonso

Misceláneas

La suma de las sumas de los cuadrados de los divisores de los 6 primeros números enteros positivos es

  1² + (1²+2²) + (1²+3²) + (1²+2²+4²) + (1²+5²) + (1²+2²+3²+6²)
= 1  + 5       + 10      + 21         + 26      + 50
= 113

Definir la función

sumaSumasCuadradosDivisores :: Integer -> Integer

tal que (sumaSumasCuadradosDivisores n) es la suma de las sumas de los cuadrados de los divisores de los n primeros números enteros positivos. Por ejemplo,

sumaSumasCuadradosDivisores 6       ==  113
sumaSumasCuadradosDivisores (10^6)  ==  400686363385965077

Suma de los dígitos de las repeticiones de un número

José A. Alonso

Misceláneas

Dados dos números naturales n y x, su suma reducida se obtiene a partir del número obtenido repitiendo n veces el x sumando sus dígitos hasta obtener un número con sólo un dígito. Por ejemplo, si n es 3 y x es 24 las transformaciones son

242424 ==> 18 ==> 9

Análogamente, si n es 4 y x es 7988 las transformaciones son

7988798879887988 ==> 128 ==> 11 ==> 2

Definir las funciones

sumaReducidaDigitosRepeticiones :: Integer -> Integer -> Integer
grafica                         :: Integer -> IO ()

tales que

(sumaReducidaDigitosRepeticiones n x) es la suma reducida de n repeticiones de x. Por ejemplo

sumaReducidaDigitosRepeticiones 3 24                    ==  9
sumaReducidaDigitosRepeticiones 4 7988                  == 2
sumaReducidaDigitosRepeticiones (12^(10^7)) (12^(10^7)) == 9

(grafica n) dibuja la gráfica de los n primeros elementos de la sucesión cuyo elementos k-ésimo es (sumaReducidaDigitosRepeticiones k k). Por ejemplo, (grafica 50) dibuja

Suma de los dígitos de las repeticiones de un número

Cruce de listas

José A. Alonso

Misceláneas

Definir la función

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

tal que (cruce xs ys) es la lista de las listas obtenidas uniendo las listas de xs sin un elemento con las de ys sin un elemento. Por ejemplo,

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

Comprobar con QuickCheck que el número de elementos de (cruce xs ys) es el producto de los números de elementos de xs y de ys.

Matrices centro simétricas

José A. Alonso

Misceláneas

Una matriz centro simétrica es una matriz cuadrada que es simétrica respecto de su centro. Por ejemplo, de las siguientes matrices, las dos primeras son simétricas y las otras no lo son

(1 2)   (1 2 3)   (1 2 3)   (1 2 3)
(2 1)   (4 5 4)   (4 5 4)   (4 5 4)
        (3 2 1)   (3 2 2)

Definir la función

esCentroSimetrica :: Eq t => Array (Int,Int) t -> Bool

tal que (esCentroSimetrica a) se verifica si la matriz a es centro simétrica. Por ejemplo,

λ> esCentroSimetrica (listArray ((1,1),(2,2)) [1,2, 2,1])
True
λ> esCentroSimetrica (listArray ((1,1),(3,3)) [1,2,3, 4,5,4, 3,2,1])
True
λ> esCentroSimetrica (listArray ((1,1),(3,3)) [1,2,3, 4,5,4, 3,2,2])
False
λ> esCentroSimetrica (listArray ((1,1),(2,3)) [1,2,3, 4,5,4])
False

Nodos con máxima suma de hijos

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

se representan por

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

Definir la función

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

tal que (nodosSumaMaxima a) es la lista de los nodos del árbol a cuyos hijos tienen máxima suma. Por ejemplo,

nodosSumaMaxima ej1  ==  [1]
nodosSumaMaxima ej2  ==  [7,3]

Números cuyos factoriales son divisibles por x pero no por y

José A. Alonso

Misceláneas

Hay 3 números (el 2, 3 y 4) cuyos factoriales son divisibles por 2 pero no por 5. Análogamente, hay números 5 (el 5, 6, 7, 8, 9) cuyos factoriales son divisibles por 15 pero no por 25.

Definir la función

nNumerosConFactorialesDivisibles :: Integer -> Integer -> Integer

tal que (nNumerosConFactorialesDivisibles x y) es la cantidad de números cuyo factorial es divisible por x pero no por y. Por ejemplo,

nNumerosConFactorialesDivisibles 2  5       ==  3
nNumerosConFactorialesDivisibles 15 25      ==  5
nNumerosConFactorialesDivisibles2 100 2000  ==  5

La función de Smarandache

José A. Alonso

Misceláneas

La función de Smarandache, también conocida como la función de Kempner, es la función que asigna a cada número entero positivo n el menor número cuyo factorial es divisible por n y se representa por S(n). Por ejemplo, el número 8 no divide a 1!, 2!, 3!, pero sí divide 4!; por tanto, S(8) = 4.

Definir las funciones

smarandache        :: Integer -> Integer
graficaSmarandache :: Integer -> IO ()

tales que

(smarandache n) es el menor número cuyo factorial es divisible por n. Por ejemplo,

smarandache 8   ==  4
smarandache 10  ==  5
smarandache 16  ==  6

(graficaSmarandache n) dibuja la gráfica de los n primeros términos de la sucesión de Smarandache. Por ejemplo, (graficaSmarandache 100) dibuja

La función de Smarandache

(graficaSmarandache 500) dibuja

La función de Smarandache

Generación de progresiones geométricas

José A. Alonso

Misceláneas

Definir la función

geometrica :: Int -> Int -> Int -> [Int]

tal que (geometrica a b c) es la lista de los términos de la progresión geométrica cuyo primer término es a, su segundo término es b (que se supone que es múltiplo de a) y los términos son menores o iguales que c. Por ejemplo,

geometrica 1 3  27   ==  [1,3,9,27]
geometrica 2 6  100  ==  [2,6,18,54]
geometrica 3 12 57   ==  [3,12,48]
geometrica 4 20 253  ==  [4,20,100]
geometrica 5 25 625  ==  [5,25,125,625]
geometrica 6 42 42   ==  [6,42]

Ceros con los n primeros números

José A. Alonso

Misceláneas

Los números del 1 al 3 se pueden escribir de dos formas, con el signo más o menos entre ellos, tales que su suma sea 0:

 1+2-3 = 0
-1-2+3 = 0

Definir la función

ceros :: Int -> [[Int]]

tal que (ceros n) son las posibles formas de obtener cero sumando los números del 1 al n, con el signo más o menos entre ellos. Por ejemplo,

ceros 3           ==  [[1,2,-3],[-1,-2,3]]
ceros 4           ==  [[1,-2,-3,4],[-1,2,3,-4]]
ceros 5           ==  []
length (ceros 7)  ==  8
take 3 (ceros 7)  ==  [[1,2,-3,4,-5,-6,7],[1,2,-3,-4,5,6,-7],[1,-2,3,4,-5,6,-7]]

Menor potencia de 2 que comienza por n

José A. Alonso

Misceláneas

Definir las funciones

menorPotencia            :: Integer -> (Integer,Integer)
graficaMenoresExponentes :: Integer -> IO ()

tales que

(menorPotencia n) es el par (k,m) donde m es la menor potencia de 2 que empieza por n y k es su exponentes (es decir, 2^k = m). Por ejemplo,

menorPotencia 3             ==  (5,32)
menorPotencia 7             ==  (46,70368744177664)
fst (menorPotencia 982)     ==  3973
fst (menorPotencia 32627)   ==  28557
fst (menorPotencia 158426)  ==  40000

(graficaMenoresExponentes n) dibuja la gráfica de los exponentes de 2 en las menores potencias de los n primeros números enteros positivos. Por ejemplo, (graficaMenoresExponentes 200) dibuja

Menor potencia de 2 que comienza por n

Representación ampliada de matrices dispersas

José A. Alonso

Misceláneas

En el ejercicio anterior se explicó una representación reducida de las matrices dispersas. A partir del número de columnas y la representación reducida se puede construir la matriz.

Definir la función

ampliada :: Num a => Int -> [[(Int,a)]] -> Matrix a

tal que (ampliada n xss) es la matriz con n columnas cuya representación reducida es xss. Por ejemplo,

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

λ> ampliada 3 [[],[]]
( 0 0 0 )
( 0 0 0 )

λ> ampliada 2 [[],[],[]]
( 0 0 )
( 0 0 )
( 0 0 )

Representación reducida de matrices dispersas

José A. Alonso

Misceláneas

Una representación reducida de una matriz dispersa es una lista de listas donde cada una de las listas representa una fila de la matriz mediante listas de pares correspondientes a las snúmeros de columnas con valores no nulos de la matriz. Por ejemplo, la representación reducida de la matriz

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

es [[(3,4)],[(2,5)],[]].

Definir la función

reducida :: (Num a, Eq a) => Matrix a -> [[(Int,a)]]

tal que (reducida p) es la representación reducida de la matriz p. Por ejemplo,

reducida (fromList 3 3 [0,0,4,0,5,0,0,0,0])  ==  [[(3,4)],[(2,5)],[]]
reducida (identity 3)  ==  [[(1,1)],[(2,1)],[(3,1)]]
reducida (zero 9 3)    ==  [[],[],[],[],[],[],[],[],[]]
reducida (zero 9 4)    ==  [[],[],[],[],[],[],[],[],[]]

Matrices dispersas

José A. Alonso

Misceláneas

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

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

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

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

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

Definir las siguientes funciones

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

tales que

(dispersion p) es la dispersión de la matriz p. Por ejemplo,

dispersion ej1              ==  0.7777777777777778
dispersion ej2              ==  0.3333333333333333
dispersion (fmap (+1) ej1)  ==  0.0
dispersion (identity 3)     ==  0.6666666666666666
dispersion (zero 9 9)       ==  1.0

(esDispersa p) se verifica si la matriz p es dispersa. Por ejemplo,

esDispersa ej1              ==  True
esDispersa ej2              ==  False
esDispersa (fmap (+1) ej1)  ==  False
esDispersa (identity 3)     ==  True
esDispersa (zero 9 9)       ==  True

Vértices de un cuadrado

José A. Alonso

Misceláneas

Definir la función

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

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

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

Números que no son cuadrados

José A. Alonso

Misceláneas

Definir las funciones

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

tales que

noCuadrados es la lista de los números naturales que no son cuadrados. Por ejemplo,

λ> take 25 noCuadrados
[2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27,28,29,30]

(graficaNoCuadrados n) dibuja las diferencias entre los n primeros elementos de noCuadrados y sus posiciones. Por ejemplo, (graficaNoCuadrados 300) dibuja

Números que no son cuadrados

(graficaNoCuadrados 3000) dibuja

Números que no son cuadrados

(graficaNoCuadrados 30000) dibuja

Números que no son cuadrados

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

Árboles binarios completos

José A. Alonso

Misceláneas

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

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

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

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

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

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

Definir la función

esBinarioCompleto :: Arbol t -> Bool

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

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

Menor número divisible por 10^n cuyos dígitos suman n

José A. Alonso

Misceláneas

Definir la función

menor :: Integer -> Integer

tal que (menor n) es el menor número divisible por 10^n cuyos dígitos suman n. Por ejemplo,

menor 5   ==  500000
menor 20  ==  29900000000000000000000

Números trimórficos

José A. Alonso

Misceláneas

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

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

Definir las funciones

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

tal que

trimorficos es la lista de los números trimórficos. Por ejemplo,

λ> take 20 trimorficos
[0,1,4,5,6,9,24,25,49,51,75,76,99,125,249,251,375,376,499,501]

(densidadTrimorficos n) es la densidad de trimórficos hasta n. Por ejemplo,

densidadTrimorficos 10      ==  0.6
densidadTrimorficos 100     ==  0.13
densidadTrimorficos 1000    ==  2.6e-2
densidadTrimorficos 10000   ==  3.7e-3
densidadTrimorficos 100000  ==  4.8e-4

Períodos de Fibonacci

José A. Alonso

Misceláneas

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

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

Al calcular sus restos módulo 3 se obtiene

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

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

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

Definir las funciones

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

tales que

(fibsMod n) es la lista de los términos de la sucesión de Fibonacci módulo n. Por ejemplo,

λ> take 24 (fibsMod 3)
[0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1, 0,1,1,2,0,2,2,1]
λ> take 24 (fibsMod 4)
[0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1, 0,1,1,2,3,1]

(periodoFibMod n) es la parte perioica de la sucesión de Fibonacci módulo n. Por ejemplo,

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

longPeriodosFibMod es la sucesión de las longitudes de los períodos de las sucesiones de Fibonacci módulo n, para n > 0. Por ejemplo,

λ> take 20 longPeriodosFibMod
[1,3,8,6,20,24,16,12,24,60,10,24,28,48,40,24,36,24,18,60]

(graficaLongPeriodosFibMod n) dibuja la gráfica de los n primeros términos de la sucesión longPeriodosFibMod. Por ejemplo, (graficaLongPeriodosFibMod n) dibuja

Períodos de Fibonacci

Recorrido de árboles en espiral

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

se representan por

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

Definir la función

espiral :: Arbol a -> [a]

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

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

Huecos binarios

José A. Alonso

Misceláneas

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

Definir las funciones

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

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

longMayorHuecoBinario 20    ==  2
longMayorHuecoBinario 529   ==  4
longMayorHuecoBinario 2018  ==  3

(graficaLongMayorHuecoBinario n) dibuja la gráfica de las longitudes de los mayores huecos binarios de los n primeros números naturales. Por ejemplo, (graficaLongMayorHuecoBinario 200) dibuja

Huecos binarios

División equitativa

José A. Alonso

Misceláneas

Definir la función

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

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

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

Celdas interiores de una retícula

José A. Alonso

Misceláneas

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

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

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

Definir la función

interiores :: Int -> [Int]

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

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

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

Dígitos iniciales

José A. Alonso

Misceláneas

Definir las funciones

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

tales que

digitosIniciales es la lista de los dígitos iniciales de los números naturales. Por ejemplo,

λ> take 100 digitosIniciales
[0,1,2,3,4,5,6,7,8,9,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,
 3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,
 6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,
 9,9,9,9,9,9,9,9,9,9]

(graficaDigitosIniciales n) dibuja la gráfica de los primeros n términos de la sucesión digitosIniciales. Por ejemplo, (graficaDigitosIniciales 100) dibuja

Dígitos iniciales

y (graficaDigitosIniciales 1000) dibuja

Dígitos iniciales

Exponentes de Hamming

José A. Alonso

Misceláneas

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

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

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

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

Definir la sucesión

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

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

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

Recorrido del robot

José A. Alonso

Misceláneas

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

type Punto = (Int,Int)

y los movimientos de un robot mediante el tipo

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

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

Definir la función

posicion :: [Movimiento] -> Punto

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

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

Relaciones arbóreas

José A. Alonso

Misceláneas

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

Una relación binaria es arbórea si

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

Definir la función

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

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

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

Máxima distancia en árbol

José A. Alonso

Misceláneas

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

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

Por ejemplo, el árbol

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

se puede representar por

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

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

Definir la función

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

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

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

Relación definida por un árbol

José A. Alonso

Misceláneas

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

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

Por ejemplo, el árbol

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

se pueden representar por

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

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

Definir la función

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

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

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