Ir al contenido principal

Árboles continuos

Misceláneas

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

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

Por ejemplo, los árboles

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

se representan por

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

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

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

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

Definir la función

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

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

esContinuo ej1  ==  True
esContinuo ej2  ==  False

Leer más…

La sucesión "Mira y di"

Misceláneas

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

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

Definir la función

sucMiraYDi :: Integer -> [Integer]

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

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

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

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

Definir la función

aproximacionConway :: Integer -> Double -> Int

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

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

Leer más…

Cadena de primos

Misceláneas

La lista de los primeros números primos es

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

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

"23571113171923293137414347535961677173798389971011"

Definir la función

primoEnPosicion :: Int -> Integer

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

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

Leer más…

Notación polaca inversa

Misceláneas

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

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

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

Definir la función

valor :: String -> Float

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

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

Leer más…

La conjetura de Rodolfo

Misceláneas

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

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

Definir las funciones

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

tales que

  • (descomposiciones x) es la lista de las descomposiciones de x como la suma de un capicúa y un capicúa especial. Por ejemplo,
descomposiciones 1980  ==  [(99,1881),(979,1001)]
descomposiciones 2016  ==  [(575,1441),(606,1410)]
descomposiciones 1971  ==  [(161,1810),(1771,200),(1881,90)]
  • contraejemplosConjeturaRodolfo es la lista de contraejemplos de la conjetura de Rodolfo; es decir, de los números que no pueden expresarse com la suma de un capicúa y un capicúa especial. Por ejemplo,
λ> take 12 contraejemplosConjeturaRodolfo
[1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
[3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

Leer más…

Sustitución en una posición

Misceláneas

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

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

Por ejemplo, los árboles

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

se pueden representar por

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

Para indicar las posiciones del árbol se define el tipo

type Posicion = [Direccion]

donde

data Direccion = D | I
  deriving Eq

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

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

Definir la función

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

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

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

Leer más…

Sumas de dos capicúas

Misceláneas

Definir las funciones

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

tales que

  • (sumas2Capicuas x) es la lista de las descomposiciones de x como suma de dos capicúas (con el primer sumando menor o igual que el segundo). Por ejemplo,
sumas2Capicuas 17  == [(6,11),(8,9)]
sumas2Capicuas 187 == [(6,181),(66,121),(88,99)]
sumas2Capicuas 165 == [(4,161),(44,121),(66,99),(77,88)]
sumas2Capicuas 382 == [(9,373),(191,191)]
sumas2Capicuas 151 == [(0,151)]
sumas2Capicuas 201 == []
  • noSuma2Capicuas es la sucesión de los números que no se pueden escribir como suma de dos capicúas. Por ejemplo,
λ> take 15 noSuma2Capicuas
[21,32,43,54,65,76,87,98,201,1031,1041,1042,1051,1052,1053]
λ> noSuma2Capicuas !! 3000
19941

Leer más…

Inversa del factorial

Misceláneas

Definir la función

inversaFactorial :: Integer -> Maybe Integer

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

inversaFactorial 24  ==  Just 4
inversaFactorial 25  ==  Nothing

Leer más…

Suma ordenada de listas infinitas ordenadas

Misceláneas

Definir la función

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

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

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

Leer más…

Sumas de tres capicúas

Misceláneas

Definir la función

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

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

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

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

Leer más…