Los triángulos binarios de Pascal se formas a partir de una lista de ceros y unos usando las reglas del triángulo de Pascal, donde cada uno de los números es suma módulo dos de los dos situados en diagonal por encima suyo. Por ejemplo, los triángulos binarios de Pascal correspondientes a [1,0,1,1,1] y [1,0,1,1,0] son

1 0 1 1 1   1 0 1 1 0
 1 1 0 0     1 1 0 1
  0 1 0       0 1 1
   1 1         1 0
    0           1

Sus finales, desde el extremo inferior al extremos superior derecho, son [0,1,0,0,1] y [1,0,1,1,0], respectivamente.

Una lista es Pascal capicúa si es igual a los finales de su triángulo binario de Pascal. Por ejemplo, [1,0,1,1,0] es Pascal capicúa.

Definir las funciones

trianguloPascalBinario :: [Int] -> [[Int]]
pascalCapicuas         :: Int -> [[Int]]
nPascalCapicuas        :: Int -> Integer

tales que

• (trianguloPascalBinario xs) es el triágulo binario de Pascal correspondiente a la lista xs. Por ejemplo,

λ> trianguloPascalBinario [1,0,1,1,1]
[[1,0,1,1,1],[1,1,0,0],[0,1,0],[1,1],[0]]
λ> trianguloPascalBinario [1,0,1,1,0]
[[1,0,1,1,0],[1,1,0,1],[0,1,1],[1,0],[1]]

• (pascalCapicuas n) es la lista de listas de Pascal capicúas de n elementos. Por ejemplo,

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

• (nPascalCapicuas n) es el número de listas de Pascal capicúas de n elementos. Por ejemplo,

λ> nPascalCapicuas 2
2
λ> nPascalCapicuas 3
4
λ> nPascalCapicuas 4
4
λ> nPascalCapicuas 400
1606938044258990275541962092341162602522202993782792835301376
λ> length (show (nPascalCapicuas (10^5)))
15052
λ> length (show (nPascalCapicuas (10^6)))
150515
λ> length (show (nPascalCapicuas (10^7)))
1505150

Leer más…

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.

Definir las funciones

imparesPascal          :: [[Integer]]
nImparesPascal         :: [Int]
grafica_nImparesPascal :: Int -> IO ()

tales que

• imparesPascal es la lista de los elementos impares en cada una de las filas del triángulo de Pascal. Por ejemplo,

λ> take 8 imparesPascal
[[1],[1,1],[1,1],[1,3,3,1],[1,1],[1,5,5,1],[1,15,15,1],[1,7,21,35,35,21,7,1]]

• nImparesPascal es la lista del número de elementos impares en cada una de las filas del triángulo de Pascal. Por ejemplo,

λ> take 32 nImparesPascal
[1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,8,16,16,32]
λ> maximum (take (10^6) nImparesPascal3)
524288

• (grafica_nImparesPascal n) dibuja la gráfica de los n primeros términos de nImparesPascal. Por ejemplo, (grafica_nImparesPascal 50) dibuja

y (grafica_nImparesPascal 100) dibuja

Comprobar con QuickCheck que todos los elementos de nImparesPascal son potencias de dos.

Leer más…

Los árboles binarios se pueden representar con

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

Definir las funciones

arboles  :: Integer -> a -> [Arbol a]
nArboles :: [Integer]

tales que

• (arboles n x) es la lista de todos los árboles binarios con n elementos iguales a x. Por ejemplo,

λ> arboles 0 7
[]
λ> arboles 1 7
[H 7]
λ> arboles 2 7
[]
λ> arboles 3 7
[N 7 (H 7) (H 7)]
λ> arboles 4 7
[]
λ> arboles 5 7
[N 7 (H 7) (N 7 (H 7) (H 7)),N 7 (N 7 (H 7) (H 7)) (H 7)]
λ> arboles 6 7
[]
λ> arboles 7 7
[N 7 (H 7) (N 7 (H 7) (N 7 (H 7) (H 7))),
 N 7 (H 7) (N 7 (N 7 (H 7) (H 7)) (H 7)),
 N 7 (N 7 (H 7) (H 7)) (N 7 (H 7) (H 7)),
 N 7 (N 7 (H 7) (N 7 (H 7) (H 7))) (H 7),
 N 7 (N 7 (N 7 (H 7) (H 7)) (H 7)) (H 7)]

• nArboles es la sucesión de los números de árboles con k elementos iguales a 7, con k ∈ {1,3,5,...}. Por ejemplo,

λ> take 14 nArboles
[1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900]
λ> nArboles !! 100
896519947090131496687170070074100632420837521538745909320
λ> length (show (nArboles !! 1000))
598

Leer más…

Definir las funciones

numerosCon1y2               :: Int -> [Int]
restosNumerosCon1y2         :: Int -> [Int]
grafica_restosNumerosCon1y2 :: Int -> IO ()

tales que

• (numerosCon1y2 n) es la lista ordenada de números de n dígitos que se pueden formar con los dígitos 1 y 2. Por ejemplo,

numerosCon1y2 2  ==  [11,12,21,22]
numerosCon1y2 3  ==  [111,112,121,122,211,212,221,222]

• (restosNumerosCon1y2 n) es la lista de los restos de dividir los elementos de (restosNumerosCon1y2 n) entre 2^n. Por ejemplo,

restosNumerosCon1y2 2 == [3,0,1,2]
restosNumerosCon1y2 3 == [7,0,1,2,3,4,5,6]
restosNumerosCon1y2 4 == [7,8,1,2,11,12,5,6,15,0,9,10,3,4,13,14]

• (graficaRestosNumerosCon1y2 n) dibuja la gráfica de los restos de dividir los elementos de (restosNumerosCon1y2 n) entre 2^n. Por ejemplo, (graficaRestosNumerosCon1y2 3) dibuja

(graficaRestosNumerosCon1y2 4) dibuja

y (graficaRestosNumerosCon1y2 5) dibuja

Nota: En la definición usar la función plotListStyle y como segundo argumento usar

(defaultStyle {plotType = LinesPoints,
               lineSpec = CustomStyle [PointType 7]})

Comprobar con QuickCheck que todos los elementos de (restosNumerosCon1y2 n) son distintos.

Leer más…

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

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

Por ejemplo, los árboles

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

se representan por

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

Definir la función

espiral :: Arbol a -> [a]

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

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

Leer más…

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

3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir las funciones

nOcurrenciasPrimosEnPi :: Int -> Int -> IO [Int]
graficaPrimosEnPi      :: Int -> Int -> IO ()

tales que

• (nOcurrenciasPrimosEnPi n k) es la lista de longitud n cuyo i-ésimo elemento es el número de ocurrencias del i-ésimo número primo en los k primeros decimales del número pi. Por ejemplo,

nOcurrenciasPrimosEnPi 4 20 == [2,3,3,1]

ya que los 20 primeros decimales de pi son 14159265358979323846 y en ellos ocurre el 2 dos veces, el 3 ocurre 3 veces, el 5 ocurre 3 veces y el 7 ocurre 1 vez. Otros ejemplos son

λ> nOcurrenciasPrimosEnPi 10 100
[12,11,8,8,1,0,1,1,2,0]
λ> nOcurrenciasPrimosEnPi 10 (10^4)
[1021,974,1046,970,99,102,90,113,99,95]
λ> nOcurrenciasPrimosEnPi 10 (10^6)
[100026,100229,100359,99800,10064,10012,9944,10148,9951,9912]

• (graficaPrimosEnPi n k) dibuja la gráfica del número de ocurrencias de los n primeros números primos en los k primeros dígitos de pi. Por ejemplo, (graficaPrimosEnPi 10 (10^4)) dibuja

(graficaPrimosEnPi 10 (10^6)) dibuja

y (graficaPrimosEnPi 50 (10^5)) dibuja

Leer más…

La sucesión triangular es la obtenida concatenando las listas [1], [1,2], [1,2,3], [1,2,3,4], .... Sus primeros términos son 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, ...

Definir las funciones

sucTriangular        :: [Integer]
terminoSucTriangular :: Int -> Integer
graficaSucTriangular :: Int -> IO ()

tales que

• sucTriangular es la lista de los términos de la sucesión triangular. Por ejemplo,

λ> take 30 sucTriangular
[1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,2,3,4,5,6,1,2,3,4,5,6,7,1,2]

• (terminoSucTriangular n) es el término n-ésimo de la sucesión triangular. Por ejemplo,

terminoSucTriangular 5       ==  3
terminoSucTriangular 10      ==  1
terminoSucTriangular 20      ==  6
terminoSucTriangular 100     ==  10
terminoSucTriangular 1001    ==  12
terminoSucTriangular (10^5)  ==  320

• (graficaSucTriangular n) dibuja la gráfica de los n primeros términos de la sucesión triangular. Por ejemplo, (graficaSucTriangular 300) dibuja

"

Leer más…

Definir la función

soluciones :: [(Integer,Integer,Integer)]

tal que sus elementos son las ternas (x,y,k) de soluciones del sistema \[x² = y³ = k\] Por ejemplo,

λ> take 6 soluciones
[(0,0,0),(-1,1,1),(1,1,1),(-8,4,64),(8,4,64),(-27,9,729)]
λ> soluciones !! (6*10^5+6)
(27000810008100027,90001800009,729043741093514580109350437400729)

Leer más…

Definir la función

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

tal que (interseccion xss) es la intersección de la lista no vacía de listas infinitas crecientes xss; es decir, la lista de los elementos que pertenecen a todas las listas de xss. Por ejemplo,

λ> take 10 (interseccion [[2,4..],[3,6..],[5,10..]])
[30,60,90,120,150,180,210,240,270,300]
λ> take 10 (interseccion [[2,5..],[3,5..],[5,7..]])
[5,11,17,23,29,35,41,47,53,59]

Leer más…

Se considera el siguiente par de operaciones sobre los números:

• multiplicar por dos
• restar uno.

Dados dos números x e y se desea calcular el menor número de operaciones para transformar x en y. Por ejemplo, el menor número de operaciones para transformar el 4 en 7 es 2:

4 ------> 8 ------> 7
   (*2)      (-1)

y el menor número de operaciones para transformar 2 en 5 es 4

2 ------> 4 ------> 3 ------> 6 ------> 5
   (*2)      (-1)      (*2)      (-1)

Definir las siguientes funciones

arbolOp :: Int -> Int -> Arbol
minNOp  :: Int -> Int -> Int

tales que

• (arbolOp x n) es el árbol de profundidad n obtenido aplicándole a x las dos operaciones. Por ejemplo,

λ> arbolOp 4 1
N 4 (H 8) (H 3)
λ> arbolOp 4 2
N 4 (N 8 (H 16) (H 7))
    (N 3 (H 6) (H 2))
λ> arbolOp 2 3
N 2 (N 4
       (N 8 (H 16) (H 7))
       (N 3 (H 6) (H 2)))
    (N 1
       (N 2 (H 4) (H 1))
       (H 0))
λ> arbolOp 2 4
N 2 (N 4 (N 8
            (N 16 (H 32) (H 15))
            (N 7 (H 14) (H 6)))
         (N 3
            (N 6 (H 12) (H 5))
            (N 2 (H 4) (H 1))))
    (N 1 (N 2
            (N 4 (H 8) (H 3))
            (N 1 (H 2) (H 0)))
         (H 0))

• (minNOp x y) es el menor número de operaciones necesarias para transformar x en y. Por ejemplo,

minNOp 4 7  ==  2
minNOp 2 5  ==  4

Leer más…