Definir la función
particion :: [a] -> [Int] -> [[a]]
tal que (particion xs ns) es la partición de xs donde la longitud de cada parte está determinada por los elementos de ns. Por ejemplo,
particion [1..10] [2,5,0,3] == [[1,2],[3,4,5,6,7],[],[8,9,10]] particion [1..10] [1,4,2,3] == [[1],[2,3,4,5],[6,7],[8,9,10]]
Definir la función
maximos :: Ord a => [a] -> [a]
tal que (maximos xs) es la lista de los elementos de xs que son mayores que todos sus anteriores. Por ejemplo,
maximos [1,-3,5,2,3,4,7,6,7] == [1,5,7] maximos "bafcdegag" == "bfg" maximos (concat (replicate (10^6) "adxbcde")++"yz") == "adxyz" length (maximos [1..10^6]) == 1000000
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]
Nota: La relación entre la sucesión y el funcionamiento del reloj se puede ver en The Mathematics Behind Prague's Horloge Introduction.
Sea p(n) el n-ésimo primo y sea r el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2. Por ejemplo,
si n = 3, entonces p(3) = 5 y r = ( 4^3 + 6^3) mod (5^2) = 5 si n = 7, entonces p(7) = 17 y r = (16^7 + 18^7) mod (17^2) = 238
Definir la función
menorPR :: Integer -> Integer
tal que (menorPR x) es el menor n tal que el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2 es mayor que x. Por ejemplo,
menorPR 100 == 5 menorPR 345 == 9 menorPR 1000 == 13 menorPR (10^9) == 7037 menorPR (10^10) == 21035 menorPR (10^12) == 191041
El polinomio cromático de un grafo calcula el número de maneras en las cuales puede ser coloreado el grafo usando un número de colores dado, de forma que dos vértices adyacentes no tengan el mismo color.
En el caso del grafo completo de n vértices, su polinomio cromático es
P(n,x) = x(x-1)(x-2) ... (x-(n-1))
Por ejemplo,
P(3,x) = x(x-1)(x-2) = x^3 - 3·x^2 + 2·x P(4,x) = x(x-1)(x-2)(x-3) = x^4 - 6·x^3 + 11·x^2 - 6·x
Lo que significa que P(4)(x) es el número de formas de colorear el grafo completo de 4 vértices con x colores. Por tanto,
P(4,2) = 0 (no se puede colorear con 2 colores) P(4,4) = 24 (hay 24 formas de colorearlo con 4 colores)
Definir la función
polGC:: Int -> Polinomio Int
tal que (polGC n) es el polinomio cromático del grafo completo de n vértices. Por ejemplo,
polGC 4 == x^4 + -6*x^3 + 11*x^2 + -6*x polGC 5 == x^5 + -10*x^4 + 35*x^3 + -50*x^2 + 24*x
Comprobar con QuickCheck que si el número de colores (x) coincide con el número de vértices del grafo (n), el número de maneras de colorear el grafo es n!.
Nota 1. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación
λ> quickCheckWith (stdArgs {maxSize=7}) prop_polGC +++ OK, passed 100 tests.
Nota 2: Este ejercicio debe realizarse usando únicamente las funciones de la librería de polinomios (I1M.PolOperaciones) que aquí.
Definir la función
sumaPosteriores :: [Int] -> [Int]
tal que (sumaPosteriores xs) es la lista obtenida sustituyendo cada elemento de xs por la suma de los elementos posteriores. Por ejemplo,
sumaPosteriores [1..8] == [35,33,30,26,21,15,8,0] sumaPosteriores [1,-3,2,5,-8] == [-4,-1,-3,-8,0]
Comprobar con QuickCheck que el último elemento de la lista (sumaPosteriores xs) siempre es 0.
Un sistema de ecuaciones lineales Ax = b es triangular inferior si todos los elementos de la matriz A que están por encima de la diagonal principal son nulos; es decir, es de la forma
a(1,1)·x(1) = b(1) a(2,1)·x(1) + a(2,2)·x(2) = b(2) a(3,1)·x(1) + a(3,2)·x(2) + a(3,3)·x(3) = b(3) ... a(n,1)·x(1) + a(n,2)·x(2) + a(n,3)·x(3) +...+ a(x,x)·x(n) = b(n)
El sistema es compatible si, y sólo si, el producto de los elementos de la diagonal principal es distinto de cero. En este caso, la solución se puede calcular mediante el algoritmo de bajada:
x(1) = b(1) / a(1,1) x(2) = (b(2) - a(2,1)·x(1)) / a(2,2) x(3) = (b(3) - a(3,1)·x(1) - a(3,2)·x(2)) / a(3,3) ... x(n) = (b(n) - a(n,1)·x(1) - a(n,2)·x(2) -...- a(n,n-1)·x(n-1)) / a(n,n)
Definir la función
bajada :: Matrix Double -> Matrix Double -> Matrix Double
tal que (bajada a b) es la solución, mediante el algoritmo de bajada, del sistema compatible triangular superior ax = b. Por ejemplo,
λ> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]] λ> let b = fromLists [[3],[6.5],[10]] λ> bajada a b ( 1.5 ) ( 2.0 ) ( 0.0 )
Es decir, la solución del sistema
2x = 3 3x + y = 6.5 4x + 2y + 5 z = 10
es x=1.5, y=2 y z=0.
Definir la función
mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]]
tal que (mayorProductoAdyacentes n p) es la lista de los segmentos formados por n elementos adyacentes en la misma fila, columna o diagonal de la matriz p cuyo productos son máximo. Por ejemplo,
λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1..12]) [[10,11,12]] λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1]) [[3,7,9]] λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,3,4, 0,3,2]) [[3,4],[4,3]] λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,0,3]) [[2,3],[2,3]] λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,4,3]) [[3,4],[4,3]] λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,5,1, 3,4,3]) [[5,4]] λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1]) [[3,7,9]]
El método de bisección para calcular un cero de una función en el intervalo [a,b] se basa en el teorema de Bolzano:
Si f(x) es una función continua en el intervalo [a, b], y si, además, en los extremos del intervalo la función f(x) toma valores de signo opuesto (f(a) * f(b) < 0), entonces existe al menos un valor c en (a, b) para el que f(c) = 0".
El método para calcular un cero de la función f en el intervalo [a,b] con un error menor que e consiste en tomar el punto medio del intervalo c = (a+b)/2 y considerar los siguientes casos:
Definir la función
biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double
tal que (biseccion f a b e) es una aproximación del punto del intervalo [a,b] en el que se anula la función f, con un error menor que e, calculada mediante el método de la bisección. Por ejemplo,
biseccion (\x -> x^2 - 3) 0 5 0.01 == 1.7333984375 biseccion (\x -> x^3 - x - 2) 0 4 0.01 == 1.521484375 biseccion cos 0 2 0.01 == 1.5625 biseccion (\x -> log (50-x) - 4) (-10) 3 0.01 == -5.125
Un número n es especial si mcm(1,2,...,n-1) = mcm(1,2,...,n). Por ejemplo, el 6 es especial ya que
mcm(1,2,3,4,5) = 60 = mcm(1,2,3,4,5,6)
Definir la sucesión
especiales :: [Integer]
cuyos términos son los números especiales. Por ejemplo,
take 10 especiales == [1,6,10,12,14,15,18,20,21,22] especiales !! 50 == 84 especiales !! 500 == 638 especiales !! 5000 == 5806 especiales !! 50000 == 55746
Definir la función
suma :: Integer -> Integer
tal que (suma n) es la suma 1 * 1! + 2 * 2! + 3 * 3! + ... + n * n!. Por ejemplo,
suma 1 == 1 suma 2 == 5 suma 3 == 23 suma 4 == 119 suma 5 == 719 take 9 (show (suma (70000))) == "823780458"
La integral definida de una función f entre los límites a y b puede calcularse mediante la regla del rectángulo usando la fórmula \[ h \cdot \left( f\left(a + \frac{h}{2}\right) + f\left(a + h + \frac{h}{2}\right) + f\left(a + 2h + \frac{h}{2}\right) + \dots + f\left(a + nh + \frac{h}{2}\right) \right) \] con \[ a + n h + \frac{h}{2} \leq b < a + (n+1) h + \frac{h}{2} \] y usando valores pequeños para \(h\).
Definir la función
integral :: (Fractional a, Ord a) => a -> a -> (a -> a) -> a -> a
tal que (integral a b f h) es el valor de dicha expresión. Por ejemplo, el cálculo de la integral de f(x) = x^3 entre 0 y 1, con paso 0.01, es
integral 0 1 (^3) 0.01 == 0.24998750000000042
Otros ejemplos son
integral 0 1 (^4) 0.01 == 0.19998333362500048 integral 0 1 (\x -> 3*x^2 + 4*x^3) 0.01 == 1.9999250000000026 log 2 - integral 1 2 (\x -> 1/x) 0.01 == 3.124931644782336e-6 pi - 4 * integral 0 1 (\x -> 1/(x^2+1)) 0.01 == -8.333333331389525e-6
El menor número con 2¹ divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).
El menor número con 2² divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).
El menor número con 2³ divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.
El menor número con 2⁴ divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.
El menor número, módulo 100, con 2⁴ divisores es el 20, ya que el menor número con 16 divisores es el 120 y 120 módulo 100 es 20.
Definir la función
menor :: Integer -> Integer -> Integer
tal que (menor n m) es el menor número, módulo m, con 2^n divisores; es decir, es el resto de dividir entre m el menor número con 2^n divisores. Por ejemplo,
menor 4 1000 == 120 menor 4 100 == 20 [menor n (10^9) | n <- [1..8]] == [2,6,24,120,840,7560,83160,1081080] menor 500500 500500506 == 8728302
Definir la función
sumaDePrimos :: Int -> [[Int]]
tal que (sumaDePrimos x) es la lista de las listas no crecientes de números primos que suman x. Por ejemplo,
sumaDePrimos 10 == [[7,3],[5,5],[5,3,2],[3,3,2,2],[2,2,2,2,2]] sumaDePrimos 0 == [] sumaDePrimos 1 == []
Definir, por simulación, la función
distanciaEsperada :: Int -> Double
tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,
distanciaEsperada 10 == 0.4815946544198219 distanciaEsperada 10 == 0.5558438642543654 distanciaEsperada 100 == 0.5699663553203216 distanciaEsperada 100 == 0.5085629461572269 distanciaEsperada 1000 == 0.5376963424746385 distanciaEsperada 1000 == 0.523432374720393
Nota. El valor exacto de la distancia esperada es
(sqrt(2) + 2 + 5*log(1+sqrt(2)))/15 = 0.5214054331647207
Definir las funciones
grafo :: [(Int,Int)] -> Grafo Int Int caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
tales que
λ> grafo [(2,4),(4,5)] G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7) [[1,3,5,7],[1,3,7]] λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7) [[2,5,3,7],[2,5,7]] λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2) [[1,3,5,2],[1,3,7,5,2]] λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4 [] λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10) 109601
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo).
En el juego de las bolas de Dijkstra se dispone de una bolsa con bolas blancas y negras. El juego consiste en elegir al azar dos bolas de la bolsa y añadir una bola negra si las dos bolas elegidas son del mismo color o una bola blanca en caso contrario. El juego termina cuando queda sólo una bola en la bolsa.
Vamos a representar las bolas blancas por 0, las negras por 1 y la bolsa la representaremos por una lista cuyos elementos son 0 ó 1.
Definir las funciones
juego :: [Int] -> [[Int]] ultima :: [Int] -> Int
tales que
juego [1,1,0,0,1] == [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]] juego [1,1,0,0,1] == [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]] juego [1,0,0,0,1] == [[1,0,0,0,1],[0,0,0,1],[0,1,1],[1,0],[0]] juego [1,0,1,1,1] == [[1,0,1,1,1],[1,1,0,1],[1,0,1],[0,1],[0]]
ultima [1,1,0,0,1] == 1 ultima [1,0,0,0,1] == 0 ultima [1,0,1,1,1] == 0
Comprobar con QuickCheck que la bola que queda en la bolsa al final del juego de Dijkstra es blanca si, y sólo si, el número de bolas blancas en la bolsa inicial es impar.
Una matriz latina de orden n es una matriz cuadrada de orden n tal que todos sus elementos son cero salvo los de su fila y columna central, si n es impar; o los de sus dos filas y columnas centrales, si n es par.
Definir la función
latina :: Int -> Array (Int,Int) Int
tal que (latina n) es la siguiente matriz latina de orden n:
| 0 0... 0 1 0 ... 0 0| | 0 0... 0 2 0 ... 0 0| | 0 0... 0 3 0 ... 0 0| | .........................| | 1 2..............n-1 n| | .........................| | 0 0... 0 n-2 0 ... 0 0| | 0 0... 0 n-1 0 ... 0 0| | 0 0... 0 n 0 ... 0 0|
| 0 0... 0 1 n 0 ... 0 0| | 0 0... 0 2 n-1 0 ... 0 0| | 0 0... 0 3 n-2 0 ... 0 0| | ................................| | 1 2.....................n-1 n| | n n-1 .................... 2 1| | ................................| | 0 0... 0 n-2 3 0 ... 0 0| | 0 0... 0 n-1 2 0 ... 0 0| | 0 0... 0 n 1 0 ... 0 0|
Por ejemplo,
λ> elems (latina 5) [0,0,1,0,0, 0,0,2,0,0, 1,2,3,4,5, 0,0,4,0,0, 0,0,5,0,0] λ> elems (latina 6) [0,0,1,6,0,0, 0,0,2,5,0,0, 1,2,3,4,5,6, 6,5,4,3,2,1, 0,0,5,2,0,0, 0,0,6,1,0,0]
Definir la función
refina :: Ord a => Monticulo a -> [a -> Bool] -> Monticulo a
tal que (refina m ps) es el montículo formado por los elementos del montículo m que cumplen todos los predicados de la lista ps. Por ejemplo,
λ> refina (foldr inserta vacio [1..22]) [(<7), even] M 2 1 (M 4 1 (M 6 1 Vacio Vacio) Vacio) Vacio λ> refina (foldr inserta vacio [1..22]) [(<1), even] Vacio
La notas de un examen se pueden representar mediante un vector en el que los valores son los pares formados por los nombres de los alumnos y sus notas.
Definir la función
aprobados :: (Num a, Ord a) => Array Int (String,a) -> Maybe [String]
tal que (aprobados p) es la lista de los nombres de los alumnos que han aprobado y Nothing si todos están suspensos. Por ejemplo,
λ> aprobados (listArray (1,3) [("Ana",5),("Pedro",3),("Lucia",6)]) Just ["Ana","Lucia"] λ> aprobados (listArray (1,3) [("Ana",4),("Pedro",3),("Lucia",4.9)]) Nothing
El sistema D'Hondt es una fórmula electoral, creada por Victor d'Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.
Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten
Definir la función
reparto :: Int -> [Int] -> [(Int,Int)]
tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,
λ> reparto 7 [340000,280000,160000,60000,15000] [(1,3),(2,3),(3,1)] λ> reparto 21 [391000,311000,184000,73000,27000,12000,2000] [(1,9),(2,7),(3,4),(4,1)]
es decir, en el primer ejemplo,
Un número tiene una inversión cuando existe un dígito x a la derecha de otro dígito de forma que x es menor que y. Por ejemplo, en el número 1745 hay dos inversiones ya que 4 es menor que 7 y 5 es menor que 7 y están a la derecha de 7.
Definir la función
nInversiones :: Integer -> Int
tal que (nInversiones n) es el número de inversiones de n. Por ejemplo,
nInversiones 1745 == 2
Definir la función
comienzanCon :: [Int] -> Int -> [Int]
tal que (comienzanCon xs d) es la lista de los elementos de xs que empiezan por el dígito d. Por ejemplo,
comienzanCon [123,51,11,711,52] 1 == [123,11] comienzanCon [123,51,11,711,52] 5 == [51,52] comienzanCon [123,51,11,711,52] 6 == []
Las posiciones frontera de una matriz de orden mxn son aquellas que están en la fila 1 o la fila m o la columna 1 o la columna n. El resto se dirán posiciones interiores. Observa que cada elemento en una posición interior tiene exactamente 8 vecinos en la matriz.
Dada una matriz, un paso de transición genera una nueva matriz de la misma dimensión pero en la que se ha sustituido cada elemento interior por la suma de sus 8 vecinos. Los elementos frontera no varían.
Definir las funciones
marco :: Int -> Int -> Integer -> Matrix Integer paso :: Matrix Integer -> Matrix Integer itPasos :: Int -> Matrix Integer -> Matrix Integer pasosHasta :: Integer -> Int
tales que
λ> marco 5 5 1 ( 1 1 1 1 1 ) ( 1 0 0 0 1 ) ( 1 0 0 0 1 ) ( 1 0 0 0 1 ) ( 1 1 1 1 1 )
λ> paso (marco 5 5 1) ( 1 1 1 1 1 ) ( 1 5 3 5 1 ) ( 1 3 0 3 1 ) ( 1 5 3 5 1 ) ( 1 1 1 1 1 )
λ> itPasos 10 (marco 5 5 1) ( 1 1 1 1 1 ) ( 1 4156075 5878783 4156075 1 ) ( 1 5878783 8315560 5878783 1 ) ( 1 4156075 5878783 4156075 1 ) ( 1 1 1 1 1 )
pasosHasta 4 == 1 pasosHasta 6 == 2 pasosHasta (2^2015) == 887
La parte par de un polinomio de coeficientes enteros es el polinomio formado por sus monomios cuyos coeficientes son números pares. Por ejemplo, la parte par de 4x^3+x^2-7x+6 es 4x^3+6.
Definir la función
partePar :: Integral a => Polinomio a -> Polinomio a
tal que (partePar p) es la parte par de p. Por ejemplo,
λ> partePar (consPol 3 4 (consPol 2 1 (consPol 0 6 polCero))) 4*x^3 + 6
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.
Representamos los árboles binarios con elementos en las hojas y en los nodos mediante el tipo de dato
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show
Definir la función
aplica :: (a -> a) -> (a -> a) -> Arbol a -> Arbol a
tal que (aplica f g a) devuelve el árbol obtenido al aplicar la función f a las hojas del árbol a y la función g a los nodos interiores. Por ejemplo,
λ> aplica (+1)(*2) (N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))) N 10 (N 4 (H 2) (H 3)) (N 6 (H 5) (H 3))
Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),...,v(n)] de nodos de G tal que:
Definir la función
ciclos :: Grafo Int Int -> [[Int]]
tal que (ciclos g) es la lista de ciclos de g. Por ejemplo, si g1 y g2 son los grafos definidos por
g1, g2 :: Grafo Int Int g1 = creaGrafo D (1,4) [(1,2,0),(2,3,0),(2,4,0),(4,1,0)] g2 = creaGrafo D (1,4) [(1,2,0),(2,1,0),(2,4,0),(4,1,0)]
entonces
ciclos g1 == [[1,2,4,1],[2,4,1,2],[4,1,2,4]] ciclos g2 == [[1,2,1],[1,2,4,1],[2,1,2],[2,4,1,2],[4,1,2,4]]
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.
Decimos que un número es alternado si no tiene dos cifras consecutivas iguales ni tres cifras consecutivas en orden creciente no estricto o decreciente no estricto. Por ejemplo, los números 132425 y 92745 son alternados, pero los números 12325 y 29778 no. Las tres primeras cifras de 12325 están en orden creciente y 29778 tiene dos cifras iguales consecutivas.
Definir la constante
alternados :: [Integer]
cuyo valor es la lista infinita de los números alternados. Por ejemplo,
take 10 alternados == [0,1,2,3,4,5,6,7,8,9] length (takeWhile (< 1000) alternados) == 616 alternados !! 1234567 == 19390804
La visibilidad de una lista es el número de elementos que son estrictamente mayores que todos los anteriores. Por ejemplo, la visibilidad de la lista [1,2,5,2,3,6] es 4.
La visibilidad de una matriz P es el par formado por las visibilidades de las filas de P y las visibilidades de las columnas de P. Por ejemplo, dada la matriz
( 4 2 1 )
Q = ( 3 2 5 )
( 6 1 8 )
la visibilidad de Q es ([1,2,2],[2,1,3]).
Definir las funciones
visibilidadLista :: [Int] -> Int visibilidadMatriz :: Matrix Int -> ([Int],[Int])
tales que
visibilidadLista [1,2,5,2,3,6] == 4 visibilidadLista [0,-2,5,1,6,6] == 3 + (visibilidadMatriz p) es la visibilidad de la matriz p. Por ejemplo, ~~~haskell λ> visibilidadMatriz (fromLists [[4,2,1],[3,2,5],[6,1,8]]) ([1,2,2],[2,1,3]) λ> visibilidadMatriz (fromLists [[0,2,1],[0,2,5],[6,1,8]]) ([2,3,2],[2,1,3])
Dado un grafo no dirigido G, un camino en G es una secuencia de nodos [v(1),v(2),v(3),...,v(n)] tal que para todo i entre 1 y n-1, (v(i),v(i+1)) es una arista de G. Por ejemplo, dados los grafos
g1, g2 :: Grafo Int Int g1 = creaGrafo ND (1,3) [(1,2,0),(1,3,0),(2,3,0)] g2 = creaGrafo ND (1,4) [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(3,4,0)]
la lista [1,2,3] es un camino en g1, pero no es un camino en g2 puesto que la arista (2,3) no existe en g2.
Definir la función
camino :: Grafo Int Int -> [Int] -> Bool
tal que (camino g vs) se verifica si la lista de nodos vs es un camino en el grafo g. Por ejemplo,
camino g1 [1,2,3] == True camino g2 [1,2,3] == False
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.
El ejercicio de hoy tiene como objetivo comprobar la veracidad del Teorema de Midy:
Sea a/p una fracción, donde a < p y p > 5 es un número primo. Si esta fracción tiene una expansión decimal periódica, donde la cantidad de dígitos en el período es par, entonces podemos partir el período en dos mitades, cuya suma es un número formado únicamente por nueves.
Por ejemplo, 2/7 = 0'285714285714... El período es 285714, cuya longitud es par (6). Lo partimos por la mitad y las sumamos: 285+714 = 999.
Definir la función
teoremaMidy :: Integer -> Bool
tal que (teoremaMidy n) se verifica si para todo todo número primo p menor que n y mayor que 5 y todo número natural menor que p tales que la cantidad de dígitos en el período de a/p es par, entonces podemos partir el período de a/p en dos mitades, cuya suma es un número formado únicamente por nueves. Por ejemplo,
teoremaMidy 200 == True
Además, comprobar el teorema de Midy usando QuickCheck.
Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,
6/2 = 3 se representa por (3,[],[]) 1/2 = 0.5 se representa por (0,[5],[]) 1/3 = 0.333333... se representa por (0,[],[3]) 23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])
Su tipo es
type Decimal = (Integer,[Integer],[Integer])
Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es
type Racional = (Integer,Integer)
Definir las funciones
decimal :: Racional -> Decimal racional :: Decimal -> Racional
tales que
decimal (1,4) == (0,[2,5],[]) decimal (1,3) == (0,[],[3]) decimal (23,14) == (1,[6],[4,2,8,5,7,1])
racional (0,[2,5],[]) == (1,4) racional (0,[],[3]) == (1,3) racional (1,[6],[4,2,8,5,7,1]) == (23,14)
Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,
λ> let (_,_,p) = decimal (23,14) in concatMap show p "428571" λ> let (_,_,p) = decimal (1,47) in concatMap show p "0212765957446808510638297872340425531914893617" λ> let (_,_,p) = decimal (1,541) in length (concatMap show p) 540
Comprobar con QuickCheck si las funciones decimal y racional son inversas.
Se llaman potencias de Fermi-Dirac a los números de la forma p^(2^k), donde p es un número primo y k es un número natural.
Definir la sucesión
potencias :: [Integer]
cuyos términos sean las potencias de Fermi-Dirac ordenadas de menor a mayor. Por ejemplo,
take 14 potencias == [2,3,4,5,7,9,11,13,16,17,19,23,25,29] potencias !! 60 == 241 potencias !! (10^6) == 15476303
Dado dos números n y m, decimos que m es un múltiplo especial de n si m es un múltiplo de n y m no tiene ningún factor primo que sea congruente con 1 módulo 3.
Definir la función
multiplosEspecialesCota :: Int -> Int -> [Int]
tal que (multiplosEspecialesCota n k) es la lista ordenada de todos los múltiplos especiales de n que son menores o iguales que k. Por ejemplo,
multiplosEspecialesCota 5 50 == [5,10,15,20,25,30,40,45,50] multiplosEspecialesCota 7 50 == []
Definir la función
minMax :: Ord a => Monticulo a -> Maybe (a,a)
tal que (minMax m) es justamente el par formado por el menor y el mayor elemento de m, si el montículo m es no vacío. Por ejemplo,
minMax (foldr inserta vacio [4,8,2,1,5]) == Just (1,8) minMax (foldr inserta vacio [4]) == Just (4,4) minMax vacio == Nothing
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de montículo (I1M.Monticulo) que se encuentra aquí.
Dada una relación r sobre un conjunto de números enteros, la matriz asociada a r es una matriz booleana p (cuyos elementos son True o False), tal que p(i,j) = True si y sólo si i está relacionado con j mediante la relación r.
Las relaciones binarias homogéneas y las matrices booleanas se pueden representar por
type Relacion = ([Int],[(Int,Int)]) type Matriz = Array (Int,Int) Bool
Definir la función
matrizRB:: Relacion -> Matriz
tal que (matrizRB r) es la matriz booleana asociada a r. Por ejemplo,
λ> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)]) array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True), ((2,1),False),((2,2),False),((2,3),False), ((3,1),True) ,((3,2),False),((3,3),True)] λ> matrizRB ([1..3],[(1,3), (3,1)]) array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True), ((2,1),False),((2,2),False),((2,3),False), ((3,1),True) ,((3,2),False),((3,3),False)] λ> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n) False
Un número n es especial si al unir los dígitos de sus factores primos, se obtienen exactamente los dígitos de n, aunque puede ser en otro orden. Por ejemplo, 1255 es especial, pues los factores primos de 1255 son 5 y 251.
Definir la función
esEspecial :: Integer -> Bool
tal que (esEspecial n) se verifica si un número n es especial. Por ejemplo,
esEspecial 1255 == True esEspecial 125 == False
Comprobar con QuickCheck que todo número primo es especial.
Calcular los 5 primeros números especiales que no son primos.
Dada una lista de números naturales xs, la codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificación de xs es
2^6 * 3^0 * 5^4 = 64 * 1 * 625 = 40000.
Definir las funciones
codificaG :: [Integer] -> Integer decodificaG :: Integer -> [Integer]
tales que
codificaG [6,0,4] == 40000 codificaG [3,1,1] == 120 codificaG [3,1,0,0,0,0,0,1] == 456 codificaG [1..6] == 4199506113235182750
decodificaG 40000 == [6,0,4] decodificaG 120 == [3,1,1] decodificaG 456 == [3,1,0,0,0,0,0,1] decodificaG 4199506113235182750 == [1,2,3,4,5,6]
Comprobar con QuickCheck que ambas funciones son inversas.
Definir la función
rotacionesNumero :: Integer -> [Integer]
(rotacionesNumero n) es la lista de las rotaciones obtenidas desplazando el primer dígito de n al final. Por ejemplo,
rotacionesNumero 325 == [325,253,532]
Definir las funciones
agrupa :: Eq a => [a] -> [(a,Int)] expande :: [(a,Int)] -> [a]
tales que
agrupa "aaabzzaa" == [('a',3),('b',1),('z',2),('a',2)]
expande [('a',2),('b',3),('a',1)] == "aabbba"
Comprobar con QuickCheck que dada una lista de enteros, si se la agrupa y después se expande se obtiene la lista inicial.
Una colección de puntos son colineales si esxiste una línea recta tal que todos están en dicha línea. Por ejemplo, los puntos (2,1), (5,7), (4,5) y (20,37) son colineales porque pertenecen a la línea y = 2*x-3.
Definir la función
colineales :: [(Int,Int)] -> Bool
tal que (colineales ps) se verifica si los puntos de la lista ps son colineales. Por ejemplo,
colineales [(2,1),(5,7),(4,5),(20,37)] == True colineales [(2,1),(5,7),(4,5),(21,37)] == False
Un número es capicúa si es igual leído de izquierda a derecha que de derecha a izquierda; por ejemplo, el 4884.
El transformado "invierte y suma" de un número x es la suma de x y su número invertido; es decir, el número resultante de la inversión del orden en el que aparecen sus dígitos. Por ejemplo, el transformado de 124 es 124 + 421 = 545.
Se aplica la transformación "invierte y suma" hasta obtener un capicúa. Por ejemplo, partiendo del número 87, el proceso es
87 + 78 = 165 165 + 561 = 726 726 + 627 = 1353 1353 + 3531 = 4884
El número de pasos de dicho proceso es la distancia capicúa del número; por ejemplo, la distancia capicúa de 87 es 4.
Definir la función
distanciaIS :: Integer -> Integer
tal que (distanciaIS x) es la distancia capicúa de x. Por ejemplo,
distanciaIS 11 == 0 distanciaIS 10 == 1 distanciaIS 19 == 2 distanciaIS 59 == 3 distanciaIS 69 == 4 distanciaIS 166 == 5 distanciaIS 79 == 6 distanciaIS 89 == 24 distanciaIS 10911 == 55 distanciaIS 1000000079994144385 == 259
Un primo circular es un número tal que todas las rotaciones de sus dígitos producen números primos. Por ejemplo, 195 es un primo circular ya que las rotaciones de sus dígitos son 197, 971 y 719 y los tres números son primos.
Definir la constante
circulares :: [Integer]
cuyo valor es la lista de los números primos circulares. Por ejemplo,
take 12 circulares == [2,3,5,7,11,13,17,31,37,71,73,79] circulares !! 50 == 939193
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
Una fracción x/y es cancelativa si se cumplen las siguientes condiciones:
Por ejemplo, 16/64 es cancelativa ya que borrando el 6 en el numerador y el denominador se obtiene 1/4 que es igual a la original: 16/64 = 1/4.
Definir la función
cancelativas :: Int -> Int -> [((Int, Int), (Int, Int))]
tal que (cancelativas m n) es la lista de las fracciones cancelativas con su denominador entre m y n. Por ejemplo,
λ> cancelativas 1 100 [((16,64),(1,4)),((26,65),(2,5)),((19,95),(1,5)),((49,98),(4,8))] λ> cancelativas 101 150 [((22,121),(2,11)),((33,132),(3,12)),((34,136),(4,16)),((44,143),(4,13))] λ> length (cancelativas 1 200) 18
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]
Los números racionales se pueden representar como pares de enteros:
type Racional a = (a,a)
Definir la función
reducida :: Integral a => [Racional a] -> [Racional a]
tal que (reducida xs) es la lista de los números racionales donde cada uno es igual al correspondiente elemento de xs y el denominador de todos los elementos de (reducida xs) es el menor número que cumple dicha condición; es decir, si xs es la lista
[(x_1, y_1), ..., (x_n, y_n)]
entonces (reducida xs) es
[(z_1, d), ..., (z_n, d)]
tales que
z_1/d = x_1/y_1, ..., z_n/d = x_n/y_n
y d es el menor posible. Por ejemplo,
reducida [(1,2),(1,3),(1,4)] == [(6,12),(4,12),(3,12)] reducida [(1,2),(1,3),(6,4)] == [(3,6),(2,6),(9,6)] reducida [(-7,6),(-10,-8)] == [(-14,12),(15,12)] reducida [(8,12)] == [(2,3)]
Definir la funciones
sumas :: Int -> [[Int]] nSumas :: Int -> Integer
tales que
sumas 1 == [[1]] sumas 2 == [[1,1],[2]] sumas 3 == [[1,1,1],[1,2],[2,1]] sumas 4 == [[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]] length (sumas 26) == 196418 length (sumas 33) == 5702887
nSumas 4 == 5 nSumas 123 == 36726740705505779255899443 length (show (nSumas 123456)) == 25801
Un número primo es hereditario si todos los números obtenidos eliminando dígitos por la derecha o por la izquierda son primos. Por ejemplo, 3797 es hereditario ya que los números obtenidos eliminando dígitos por la derecha son 3797, 379, 37 y 3 y los obtenidos eliminando dígitos por la izquierda son 3797, 797, 97 y 7 y todos ellos son primos.
Definir la sucesión
hereditarios :: [Integer]
cuyos elementos son los números hereditarios. Por ejemplo,
λ> take 15 hereditarios [2,3,5,7,23,37,53,73,313,317,373,797,3137,3797,739397]
La constante de Champernowne es el número irracional
0.12345678910111213141516171819202122232425262728293031323334 ...
cuya parte entera es 0 y la parte decimal se obtiene concatenado los números naturales a partir de 1.
Definir la función
productoChampernowne :: [Int] -> Int
tal que (productoChampernowne ns) es el producto de los dígitos de la constante de Champernowne que ocupan las posiciones ns. Por ejemplo,
productoChampernowne [0,1,2] == 6 productoChampernowne [8,20] == 45 productoChampernowne [10^i-1 | i <- [0..7]] == 1470
Se tiene una calle en la que las casas sólo están en un lado de ésta y las casas están numeradas de 1 hasta n, donde n es el número total de casas en la calle. Se dice que el número de una casa es equilibrado si y solamente si la suma de los números de las casas anteriores es igual a la suma de los números posteriores a la casa. Por ejemplo, el número de la 6ª casa, en una calle con 8 casas, es equilibrado ya que
1 + 2 + 3 + 4 + 5 = 7 + 8
Definir la función
soluciones :: Integer -> Integer -> [(Integer,Integer)]
tal que (soluciones x y) es la lista de pares (a,n) tales que a es el número equilibrado de una casa en una calle con n casas y n está entre x e y. Por ejemplo,
soluciones 1 500 == [(1,1),(6,8),(35,49),(204,288)] soluciones 1000 3000 == [(1189,1681)] soluciones (10^5) (10^6) == [(235416,332928)] soluciones (10^6) (10^7) == [(1372105,1940449)] (fst $ head $ soluciones (10^100) (10^101)) `mod` (10^9) == 763728460 (fst $ head $ soluciones (10^800) (10^1000)) `mod` (10^9) == 311156546
Las torres de Hanói es un rompecabeza que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los N discos en el poste C.
Definir la función
hanoi :: Int -> [String]
tal que (hanoi n) es la lista de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,
λ> hanoi 1 ["Mueve el disco 1 de A a C"] λ> hanoi 2 ["Mueve el disco 1 de A a B","Mueve el disco 2 de A a C","Mueve el disco 1 de B a C"] λ> mapM_ putStrLn (hanoi 2) Mueve el disco 1 de A a B Mueve el disco 2 de A a C Mueve el disco 1 de B a C λ> mapM_ putStrLn (hanoi 3) Mueve el disco 1 de A a C Mueve el disco 2 de A a B Mueve el disco 1 de C a B Mueve el disco 3 de A a C Mueve el disco 1 de B a A Mueve el disco 2 de B a C Mueve el disco 1 de A a C
Empezando con el número 1 y moviéndose en el sentido de las agujas del reloj se obtienen las matrices espirales
|1 2| |7 8 9| | 7 8 9 10| |21 22 23 24 25|
|4 3| |6 1 2| | 6 1 2 11| |20 7 8 9 10|
|5 4 3| | 5 4 3 12| |19 6 1 2 11|
|16 15 14 13| |18 5 4 3 12|
|17 16 15 14 13|
La suma los elementos de sus diagonales es
Definir la función
sumaDiagonales :: Integer -> Integer
tal que (sumaDiagonales n) es la suma de los elementos en las diagonales de la matriz espiral de orden nxn. Por ejemplo.
sumaDiagonales 1 == 1 sumaDiagonales 2 == 10 sumaDiagonales 3 == 25 sumaDiagonales 4 == 56 sumaDiagonales 5 == 101 sumaDiagonales (1+10^6) == 666669166671000001 sumaDiagonales (10^2) == 671800 sumaDiagonales (10^3) == 667168000 sumaDiagonales (10^4) == 666716680000 sumaDiagonales (10^5) == 666671666800000 sumaDiagonales (10^6) == 666667166668000000 sumaDiagonales (10^7) == 666666716666680000000 sumaDiagonales (10^8) == 666666671666666800000000 sumaDiagonales (10^9) == 666666667166666668000000000
Comprobar con QuickCheck que el último dígito de (sumaDiagonales n) es 0, 4 ó 6 si n es par y es 1, 5 ó 7 en caso contrario.
Un número pandigital es un número que contiene todos los dígitos del 1 al 9 sólo una vez. Por ejemplo, 192384576 es un número pandigital.
El producto de un número natural x por una lista de números naturales ys es el número obtenido concatenando los productos de x por cada uno de los elementos de ys. Por ejemplo, el producto de 2 por [3,2,5] es 6410.
Un número pandigital x es un múltiplo si existe un y y un n > 1 tales que x es el producto de y por [1,2,3,...,n]. Por ejemplo, 192384576 es un pandigital múltiplo ya que
192 × 1 = 192 192 × 2 = 384 192 × 3 = 576
por tanto, 192384576 es el producto de 192 por [1,2,3]. Otro pandgital múltiplo es el 918273645 ya que es el producto de 9 por [1,2,3,4,5].
Definir la sucesión
pandigitalesMultiplos :: [Integer]
tal que sus elementos son los números pandigitales múltiplos. Por ejemplo,
λ> take 5 pandigitalesMultiplos [123456789,192384576,219438657,273546819,327654981]
El producto de un número natural x por una lista de números naturales ys es el número obtenido concatenando los productos de x por cada uno de los elementos de ys. Por ejemplo, el producto de 2 por [3,2,5] es 26410.
Definir la función
producto :: Integer -> [Integer] -> Integer
tal que (producto x ys) es el producto de x por ys. Por ejemplo,
producto 2 [3,2,5] == 6410 producto 10 [3,2,5] == 302050
El grado perimetral de un número p es la cantidad de tres triángulos rectángulos de lados enteros cuyo perímetro es p. Por ejemplo, el grado perimetral de 120 es 3 ya que sólo hay 3 triángulos rectángulos de lados enteros cuyo perímetro es 120: {20,48,52}, {24,45,51} y {30,40,50}.
Definir la función
maxGradoPerimetral :: Int -> (Int,[Int])
tal que (maxGradoPerimetral n) es el par (m,ps) tal que m es el máximo grado perimetral de los números menores o iguales que n y ps son los perímetros, menores o iguales que n, cuyo grado perimetral es m. Por ejemplo,
maxGradoPerimetral 50 == (1,[12,24,30,36,40,48]) maxGradoPerimetral 100 == (2,[60,84,90]) maxGradoPerimetral 200 == (3,[120,168,180]) maxGradoPerimetral 400 == (4,[240,360]) maxGradoPerimetral 500 == (5,[420]) maxGradoPerimetral 750 == (6,[720]) maxGradoPerimetral 839 == (6,[720]) maxGradoPerimetral 840 == (8,[840]) maxGradoPerimetral 1500 == (8,[840,1260]) maxGradoPerimetral 2000 == (10,[1680]) maxGradoPerimetral 3000 == (12,[2520])
Una progresión aritmética es una sucesión de números tales que la diferencia de dos términos sucesivos cualesquiera de la sucesión es constante.
Definir la función
ausente :: Integral a => [a] -> a
tal que (ausente xs) es el único término ausente de la progresión aritmética xs. Por ejemplo,
ausente [3,7,9,11] == 5 ausente [3,5,9,11] == 7 ausente [3,5,7,11] == 9 ausente ([1..9]++[11..]) == 10 ausente2 ([1..10^6] ++ [2+10^6]) == 1000001
Nota. Se supone que la lista tiene al menos 3 elementos, que puede ser infinita y que sólo hay exactamente un término de la progresión aritmética que no está en la lista.
Un polinomio de coeficientes enteros se dirá par si todos sus coeficientes son números pares. Por ejemplo, el polinomio 2x³ - 4x² + 8 es par y el x² + 2x + 10 no lo es.
Definir el predicado
parPol :: Integral a => Polinomio a -> Bool
tal que (parPol p) se verifica si p es un polinomio par. Por ejemplo,
λ> parPol (consPol 3 2 (consPol 2 (-4) (consPol 0 8 polCero))) True λ> parPol (consPol 2 1 (consPol 1 2 (consPol 0 10 polCero))) False
Comprobar con QuickCheck que la suma de un polinomio con él mismo es un polinomio par.
Nota: Este ejercicio debe realizarse usando la librería I1M.Pol que se encuentra aquí y se describe aquí.
Representamos las matrices mediante el tipo de dato
type Matriz a = Array (Int,Int) a
Por ejemplo,
ejM :: Matriz Int ejM = listArray ((1,1),(2,4)) [1,2,3,0,4,5,6,7]
representa la matriz
|1 2 3 0| |4 5 6 7|
Definir la función
ampliada :: Num a => Matriz a -> Matriz a
tal que (ampliada p) es la matriz obtenida al añadir una nueva fila a p cuyo elemento i-ésimo es la suma de la columna i-ésima de p. Por ejemplo,
|1 2 3 0| |1 2 3 0|
|4 5 6 7| ==> |4 5 6 7|
|5 7 9 7|
En Haskell,
λ> ampliada ejM array ((1,1),(3,4)) [((1,1),1),((1,2),2),((1,3),3),((1,4),0), ((2,1),4),((2,2),5),((2,3),6),((2,4),7), ((3,1),5),((3,2),7),((3,3),9),((3,4),7)]
Representamos los árboles binarios con elementos en las hojas y en los nodos mediante el tipo de dato
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show
Por ejemplo,
ej1 :: Arbol Int ej1 = N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))
Definir la función
ramasCon :: Eq a => Arbol a -> a -> [[a]]
tal que (ramasCon a x) es la lista de las ramas del árbol a en las que aparece el elemento x. Por ejemplo,
ramasCon ej1 2 == [[5,2,1],[5,2,2],[5,3,2]]
Dos enteros positivos a y b se dirán relacionados si poseen, exactamente, un factor primo en común. Por ejemplo, 12 y 20 están relacionados, pero 6 y 30 no lo están.
Definir la lista infinita
paresRel :: [(Int,Int)]
tal que paresRel enumera todos los pares (a,b), con 1 ≤ a < b, tal que a y b están relacionados. Por ejemplo,
λ> take 10 paresRel [(2,4),(2,6),(3,6),(4,6),(2,8),(4,8),(6,8),(3,9),(6,9),(2,10)]
¿Qué lugar ocupa el par (51,111) en la lista infinita paresRel?
Definir las funciones
agrupa :: Eq a => [a] -> [(a,Int)] expande :: [(a,Int)] -> [a]
tales que
agrupa "aaabzzaa" == [('a',3),('b',1),('z',2),('a',2)]
expande [('a',2),('b',3),('a',1)] == "aabbba"
Comprobar con QuickCheck que dada una lista de enteros, si se la agrupa y después se expande se obtiene la lista inicial.
Decimos que un número es de suma prima si la suma de todos sus dígitos es un número primo. Por ejemplo el número 562 es de suma prima pues la suma de sus dígitos es el número primo 13; sin embargo, el número 514 no es de suma prima pues la suma de sus dígitos es 10, que no es primo.
Decimos que un número es de suma prima hereditario por la derecha si es de suma prima y los números que se obtienen eliminando sus últimas cifras también son de suma prima. Por ejemplo 7426 es de suma prima hereditario por la derecha pues 7426, 742, 74 y 7 son todos números de suma prima.
Definir la constante
listaSumaPrimaHD :: [Integer]
cuyo valor es la lista infinita de los números de suma prima hereditarios por la derecha. Por ejemplo,
take 10 listaSumaPrimaHD == [2,3,5,7,20,21,23,25,29,30] listaSumaPrimaHD !! 2000000 == 3800024668046
Todo número par se puede escribir como suma de números pares de varias formas. Por ejemplo,
8 = 8 = 6 + 2 = 4 + 4 = 4 + 2 + 2 = 2 + 2 + 2 + 2
Definir la función
descomposicionesDecrecientes:: Integer -> [[Integer]]
tal que (descomposicionesDecrecientes n) es la lista con las descomposiciones de n como suma de pares, en forma decreciente. Por ejemplo,
λ> descomposicionesDecrecientes 8 [[8],[6,2],[4,4],[4,2,2],[2,2,2,2]] λ> descomposicionesDecrecientes 10 [[10],[8,2],[6,4],[6,2,2],[4,4,2],[4,2,2,2],[2,2,2,2,2]] λ> length (descomposicionesDecrecientes 100) 204226
Los polinomios de Bell forman una sucesión de polinomios, definida como sigue:
B₀(x) = 1 (polinomio unidad) Bₙ(x) = x·[Bₙ(x) + Bₙ'(x)]
donde Bₙ' es la derivada de Bₙ. Por ejemplo,
B₀(x) = 1 = 1 B₁(x) = x·(1+0) = x B₂(x) = x·(x+1) = x²+x B₃(x) = x·(x²+x + 2x+1) = x³+3x²+x B₄(x) = x·(x³+3x²+x + 3x²+6x+1) = x⁴+6x³+7x²+x
Definir la función
polBell :: Integer -> Polinomio Integer
tal que (polBell n) es el polinomio de Bell de grado n. Por ejemplo,
polBell 4 == x^4 + 6*x^3 + 7*x^2 + 1*x coeficiente 2 (polBell 4) == 7 coeficiente 2 (polBell 30) == 536870911 coeficiente 1 (polBell 1000) == 1 length (show (coeficiente 9 (polBell 1000))) == 949
Notas: Se usa la librería I1M.PolOperaciones que se encuentra aquí y se describe aquí. Además, en el último ejemplo se usa la función coeficiente tal que (coeficiente k p) es el coeficiente del término de grado k en el polinomio p definida por
coeficiente :: Num a => Integer -> Polinomio a -> a coeficiente k p | k == n = coefLider p | k > grado (restoPol p) = 0 | otherwise = coeficiente k (restoPol p) where n = grado p
Consideramos las matrices representadas como tablas cuyos índices son pares de números naturales.
type Matriz a = Array (Int,Int) a
Una matriz cruzada es una matriz cuadrada en la que sólo hay elementos distintos de 0 en las diagonales principal y secundaria. Por ejemplo,
| 1 0 0 0 3 | | 1 0 0 3 | | 0 2 0 1 0 | | 0 2 3 0 | | 0 0 3 0 0 | | 0 4 5 0 | | 0 2 0 1 0 | | 2 0 0 3 | | 1 0 0 0 3 |
Definir la función
creaCruzada :: Int -> Matriz Int
tal que (creaCruzada n) es la siguiente matriz cruzada con n filas y n columnas:
| 1 0 0 ... 0 0 1 | | 0 2 0 ... 0 2 0 | | 0 0 3 ... 3 0 0 | | ....................... | | 0 0 n-2 ... n-2 0 0 | | 0 n-1 0 ... 0 n-1 0 | | n 0 0 ... 0 0 n |
Es decir, los elementos de la diagonal principal son [1,...,n], en orden desde la primera fila hasta la última; y los elementos de la diagonal secundaria son [1,...,n], en orden desde la primera fila hasta la última. Por ejemplo,
λ> elems (creaCruzada 3) [1,0,1, 0,2,0, 3,0,3] λ> elems (creaCruzada 4) [1,0,0,1, 0,2,2,0, 0,3,3,0, 4,0,0,4] λ> elems (creaCruzada 5) [1,0,0,0,1, 0,2,0,2,0, 0,0,3,0,0, 0,4,0,4,0, 5,0,0,0,5]
Consideremos los árboles binarios con etiquetas en las hojas y en los nodos. Por ejemplo,
5
/ \
2 4
/ \
7 1
/ \
2 3
Un camino es una sucesión de nodos desde la raiz hasta una hoja. Por ejemplo, [5,2] y [5,4,1,2] son caminos que llevan a 2, mientras que [5,4,1] no es un camino, pues no lleva a una hoja.
Definimos el tipo de dato Arbol y el ejemplo por
data Arbol = H Int | N Arbol Int Arbol deriving Show arb1:: Arbol arb1 = N (H 2) 5 (N (H 7) 4 (N (H 2) 1 (H 3)))
Definir la función
maxLong :: Int -> Arbol -> Int
tal que (maxLong x a) es la longitud máxima de los caminos que terminan en x. Por ejemplo,
maxLong 3 arb1 == 4 maxLong 2 arb1 == 4 maxLong 7 arb1 == 3
Un elemento de una matriz es un máximo local si es mayor que todos sus vecinos. Por ejemplo, en la matriz
[[1,0,0,8], [0,2,0,3], [0,0,0,5], [3,5,7,6], [1,2,3,4]]
los máximos locales son 8 (en la posición (1,4)), 2 (en la posición (2,2)) y 7 (en la posición (4,3)).
Definimos el tipo de las matrices, mediante
type Matriz a = Array (Int,Int) Int
y el ejemplo anterior por
ej1 :: Matriz Int ej1 = listArray ((1,1),(5,4)) (concat [[1,0,0,8], [0,2,0,3], [0,0,0,5], [3,5,7,6], [1,2,3,4]])
Definir la función
maximosLocales :: Matriz Int -> [((Int,Int),Int)]
tal que (maximosLocales p) es la lista de las posiciones en las que hay un máximo local, con el valor correspondiente. Por ejemplo,
maximosLocales ej1 == [((1,4),8),((2,2),2),((4,3),7)]
En lógica temporal, la expresión AFp significa que en algún momento en el futuro se cumple la propiedad p. Trasladado a su interpretación en forma de árbol lo que quiere decir es que en todas las ramas (desde la raíz hasta una hoja) hay un nodo que cumple la propiedad p.
Consideramos el siguiente tipo algebraico de los árboles binarios:
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show,Eq)
y el siguiente árbol
a1 :: Arbol Int a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8)
En este árbol se cumple (AF par); es decir, en todas las ramas hay un número par; pero no se cumple (AF primo); es decir, hay ramas en las que no hay ningún número primo. Donde una rama es la secuencia de nodos desde el nodo inicial o raíz hasta una hoja.
Definir la función
propiedadAF :: (a -> Bool) -> Arbol a -> Bool
tal que (propiedadAF p a) se verifica si se cumple (AF p) en el árbol a; es decir, si en todas las ramas hay un nodo (interno u hoja) que cumple la propiedad p. Por ejemplo
propiedadAF even a1 == True propiedadAF isPrime a1 == False
El cociente entero de un polinomio P(x) por un monomio axⁿ es el polinomio que se obtiene a partir de los términos de P(x) con un grado mayor o igual que n, realizando la división entera entre sus coeficientes y el coeficiente del monomio divisor y restando el valor de n al de sus grados. Por ejemplo,
Definir la función
cocienteEntero :: Polinomio Int -> Int -> Int -> Polinomio Int
tal que (cocienteEntero p a n) es el cociente entero del polinomio p por el monomio de grado n y coeficiente a. Por ejemplo,
λ> let listaApol xs = foldr (\(n,b) -> consPol n b) polCero xs λ> cocienteEntero (listaApol [(4,4),(3,6),(2,7),(1,5),(0,2)]) 3 2 x^2 + 2*x + 2 λ> cocienteEntero (listaApol [(5,6),(4,2),(3,8),(2,5),(1,8),(0,4)]) 4 3 x^2 + 2
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.
Se dice que dos números naturales son parientes sitienen exactamente un factor primo en común, independientemente de su multiplicidad. Por ejemplo,
Se dice que una lista de números naturales es una secuencia de parientes si cada par de números consecutivos son parientes. Por ejemplo,
Definir la función
secuenciaParientes :: [Integer] -> Bool
tal que (secuenciaParientes xs) se verifica si xs es una secuencia de parientes. Por ejemplo,
secuenciaParientes [12,40,35,28] == True secuenciaParientes [12,30,21,49] == False secuenciaParientes [2^n | n <- [1..2000]] == True
En este ejercicio, representamos las fracciones mediante pares de números de enteros.
Definir la función
fraccionesOrd :: Integer -> [(Integer,Integer)]
tal que (fraccionesOrd n) es la lista con las fracciones propias positivas ordenadas, con denominador menor o igual que n. Por ejemplo,
λ> fraccionesOrd 4 [(1,4),(1,3),(1,2),(2,3),(3,4)] λ> fraccionesOrd 5 [(1,5),(1,4),(1,3),(2,5),(1,2),(3,5),(2,3),(3,4),(4,5)]
En 1772, Euler publicó que el polinomio n² + n + 41 genera 40 números primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n=40, 40²+40+41 = 40(40+1)+41 es divisible por 41.
Usando ordenadores, se descubrió el polinomio n² - 79n + 1601 que genera 80 números primos para todos los valores de n entre 0 y 79.
Definir la función
generadoresMaximales :: Integer -> (Int,[(Integer,Integer)])
tal que (generadoresMaximales n) es el par (m,xs) donde
Por ejemplo,
generadoresMaximales 4 == ( 3,[(-2,3),(-1,3),(3,3)]) generadoresMaximales 6 == ( 5,[(-1,5),(5,5)]) generadoresMaximales 50 == (43,[(-5,47)]) generadoresMaximales 100 == (48,[(-15,97)]) generadoresMaximales 200 == (53,[(-25,197)]) generadoresMaximales 1650 == (80,[(-79,1601)])
El triángulo de Floyd, llamado así en honor a Robert Floyd, es un triángulo rectángulo formado con números naturales. Para crear un triángulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se continúa escribiendo la secuencia de los números naturales de manera que cada línea contenga un número más que la anterior. Las 5 primeras líneas del triángulo de Floyd son
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Definir la función
trianguloFloyd :: [[Integer]]
tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,
λ> take 4 trianguloFloyd [[1], [2,3], [4,5,6], [7,8,9,10]] (trianguloFloyd !! (10^5)) !! 0 == 5000050001 (trianguloFloyd !! (10^6)) !! 0 == 500000500001 (trianguloFloyd !! (10^7)) !! 0 == 50000005000001
En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas
41 = 2 + 3 + 5 + 7 + 11 + 13 41 = 11 + 13 + 17
el 240 se puede escribir de tres formas
240 = 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 240 = 53 + 59 + 61 + 67 240 = 113 + 127
y el 311 se puede escribir de 4 formas
311 = 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 311 = 31 + 37 + 41 + 43 + 47 + 53 + 59 311 = 53 + 59 + 61 + 67 + 71 311 = 101 + 103 + 107
Definir la función
sumas :: Integer -> [[Integer]]
tal que (sumas x) es la lista de las formas de escribir x como suma de dos o más números primos consecutivos. Por ejemplo,
λ> sumas 41 [[2,3,5,7,11,13],[11,13,17]] λ> sumas 240 [[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]] λ> sumas 311 [[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],[53,59,61,67,71],[101,103,107]] λ> maximum [length (sumas n) | n <- [1..600]] 4
Definir la función
actualiza :: [a] -> [(Int,a)] -> [a]
tal que (actualiza xs ps) es la lista obtenida sustituyendo en xs los elementos cuyos índices son las primeras componentes de ps por las segundas. Por ejemplo,
actualiza [3,5,2,4] [(2,1),(0,7)] == [7,5,1,4] sum (actualiza2 [1..10^4] [(i,2*i) | i <- [0..10^4-1]]) == 99990000
El orden de divisibilidad de un número x es el mayor n tal que para todo i menor o igual que n, los i primeros dígitos de n es divisible por i. Por ejemplo, el orden de divisibilidad de 74156 es 3 porque
7 es divisible por 1 74 es divisible por 2 741 es divisible por 3 7415 no es divisible por 4
Definir la función
ordenDeDivibilidad :: Integer -> Int
tal que (ordenDeDivibilidad x) es el orden de divisibilidad de x. Por ejemplo,
ordenDeDivibilidad 74156 == 3 ordenDeDivibilidad 3608528850368400786036725 == 25
Una propiedad del número 24 es que entre los números menores o iguales que 24 hay la misma cantidad de números con el dígito 1 que sin el 1; en efecto, los que tienen 1 son
[1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 21]
y los que no lo tienen son
[2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24]
Diremos que un número es especial si cumple dicha propiedad.
Definir la sucesión
especiales :: [Integer]
cuyos elementos son los números especiales. Por ejemplo,
take 10 especiales == [2,16,24,160,270,272,1456,3398,3418,3420]
Los caminos en los árboles binarios
. .
/ \ / \
. . / \
/ \ . .
. . / \ / \
. . . .
son [[I,I],[I,D],[D]] y [[I,I],[I,D],[D,I],[D,D]], donde I indica un movimiento hacia la izquierda y D uno hacia la derecha.
Los árboles binarios se pueden representar por
data Arbol = H | N Arbol Arbol
los movimientos por
data Mov = I | D deriving Show
y los caminos por
type Camino = [Mov]
Definir la función
caminos :: Arbol -> [Camino]
tal que (caminos a) es la lista de los caminos en el árbol binario a. Por ejemplo,
caminos (N (N H H) H) == [[I,I],[I,D],[D]] caminos (N (N H H) (N H H)) == [[I,I],[I,D],[D,I],[D,D]] caminos (N H (N (N H H) (N H H))) == [[I],[D,I,I],[D,I,D],[D,D,I],[D,D,D]]
Sea S un conjunto de números. Las listas de ceros emparejados de S son las listas formadas con los elementos de S y en las cuales los ceros aparecen en sublistas de longitud par. Por ejemplo, si S = {0,1,2} entonces [1], [2], [2,1], [2,0,0,2,0,0,1] y [0,0,0,0,1,2] son listas de ceros emparejados de S; pero [0,0,0,2,1,0,0] y [0,0,1,0,1] no lo son.
Definir las funciones
cerosEmparejados :: Integer -> Integer -> [[Integer]] nCerosEmparejados :: Integer -> Integer -> Integer
tales que + (cerosEmparejados m n) es la lista de las listas de longitud n de ceros emparejados con los números 0, 1, 2,..., m. Por ejemplo,
λ> cerosEmparejados 2 0 [[]] λ> cerosEmparejados 2 1 [[1],[2]] λ> cerosEmparejados 3 1 [[1],[2],[3]] λ> cerosEmparejados 2 2 [[1,1],[1,2],[2,1],[2,2],[0,0]] λ> cerosEmparejados 2 3 [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[1,0,0],[2,1,1],[2,1,2], [2,2,1],[2,2,2],[2,0,0],[0,0,1],[0,0,2]] λ> cerosEmparejados 2 4 [[1,1,1,1],[1,1,1,2],[1,1,2,1],[1,1,2,2],[1,1,0,0],[1,2,1,1], [1,2,1,2],[1,2,2,1],[1,2,2,2],[1,2,0,0],[1,0,0,1],[1,0,0,2], [2,1,1,1],[2,1,1,2],[2,1,2,1],[2,1,2,2],[2,1,0,0],[2,2,1,1], [2,2,1,2],[2,2,2,1],[2,2,2,2],[2,2,0,0],[2,0,0,1],[2,0,0,2], [0,0,1,1],[0,0,1,2],[0,0,2,1],[0,0,2,2],[0,0,0,0]]
nCerosEmparejados 2 2 == 5 nCerosEmparejados 2 3 == 12 nCerosEmparejados 2 4 == 29 nCerosEmparejados 9 27 == 79707842493701635611689499
Definir la función
productos :: Integer -> Integer -> [[Integer]]
tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,
productos 2 6 == [[2,3]] productos 3 6 == [[1,2,3]] productos 4 1680 == [[5,6,7,8]] productos 2 5 == []
Comprobar con QuickCheck que si n > 0 y x > 0, entonces
productos n (product [x..x+n-1]) == [[x..x+n-1]]
Usando productos, definir la función
productosDe2y3consecutivos :: [Integer]
cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,
head productosDe2y3consecutivos == 6
Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.
En este problema se consideran matrices cuyos elementos son 0 y 1. Los valores 1 aparecen en forma de islas rectangulares separadas por 0 de forma que como máximo las islas son diagonalmente adyacentes. Por ejemplo,
ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(6,3)) [0,0,0, 1,1,0, 1,1,0, 0,0,1, 0,0,1, 1,1,0] ej2 = listArray ((1,1),(6,6)) [1,0,0,0,0,0, 1,0,1,1,1,1, 0,0,0,0,0,0, 1,1,1,0,1,1, 1,1,1,0,1,1, 0,0,0,0,1,1]
Definir la función
numeroDeIslas :: Array (Int,Int) Int -> Int
tal que (numeroDeIslas p) es el número de islas de la matriz p. Por ejemplo,
numeroDeIslas ej1 == 3 numeroDeIslas ej2 == 4
Sea \(\{b_i \mid i \geq 1\}\) una sucesión infinita de números enteros mayores que 1. Entonces, todo entero \(x\) mayor que cero se puede escribir de forma única como \[ x = x_0 + x_1 b_1 + x_2 b_1 b_2 + \dots + x_n b_1 b_2 \dotsm b_n, \] donde cada \(x_i\) satisface la condición \(0 \leq x_i < b_{i+1}\). Se dice que \([x_n, x_{n-1}, \dots, x_2, x_1, x_0]\) es la representación de \(x\) en la base \((b_i).
Por ejemplo, la representación de 377 en la base \((2i)_{i \geq 1}\) es \([7,5,0,1]\), ya que \[ 377 = 1 + 0 \times 2 + 5 \times 2 \times 4 + 7 \times 2 \times 4 \times 6, \] y además: \[ 0 \leq 1 < 2, \quad 0 \leq 0 < 4, \quad 0 \leq 5 < 6, \quad 0 \leq 7 < 8. \]
Definir las funciones
decimalAmultiple :: [Int] -> Int -> [Int] multipleAdecimal :: [Int] -> [Int] -> Int
tales que (decimalAmultiple bs x) es la representación del número x en la base bs y (multipleAdecimal bs cs) es el número decimal cuya representación en la base bs es cs. Por ejemplo,
decimalAmultiple [2,4..] 377 == [7,5,0,1] multipleAdecimal [2,4..] [7,5,0,1] == 377 decimalAmultiple [2,5..] 377 == [4,5,3,1] multipleAdecimal [2,5..] [4,5,3,1] == 377 decimalAmultiple [2^n | n <- [1..]] 2015 == [1,15,3,3,1] multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1] == 2015 decimalAmultiple (repeat 10) 2015 == [2,0,1,5] multipleAdecimal (repeat 10) [2,0,1,5] == 2015
Comprobar con QuickCheck que se verifican las siguientes propiedades
prop_inversas :: [Int] -> Int -> Property prop_inversas bs x = x > 0 ==> multipleAdecimal bs (decimalAmultiple bs x) == x prop_coeficientes :: [Int] -> Int -> Property prop_coeficientes bs x = x > 0 ==> and [0 <= c && c < b | (c,b) <- zip cs bs] where cs = reverse (decimalAmultiple bs x)
para distintas bases dadas. Por ejemplo,
λ> quickCheck (prop_inversas [2,4..]) +++ OK, passed 100 tests. λ> quickCheck (prop_inversas [3,5..]) +++ OK, passed 100 tests. λ> quickCheck (prop_coeficientes [2,4..]) +++ OK, passed 100 tests. λ> quickCheck (prop_coeficientes [3,5..]) +++ OK, passed 100 tests.
La diferencia progresiva entre dos elementos de una lista es la resta entre el que ocupa la mayor posición y la menor. Por ejemplo, en la lista [1,5,8,2,9] la diferencia entre los elementos 5 y 8 es 3 y entre 5 y 2 es -3.
Definir la función
mayorDiferencia :: [Int] -> Int
tal que (mayorDiferencia xs) es la mayor diferencia progresiva entre los elementos de xs. Por ejemplo,
mayorDiferencia [1,5,8,2,9] == 8 mayorDiferencia [9,5,8,2,1] == 3 mayorDiferencia [3,2,1] == 0 mayorDiferencia [1..10^7] == 9999999
Los conjuntos de polinomios se pueden representar por listas de listas de la misma longitud. Por ejemplo, los polinomios 3x²+5x+9, 10x³+9 y 8x³+5x²+x-1 se pueden representar por las listas [0,3,5,9], [10,0,0,9] y [8,5,1,-1].
Definir la función
sumaPolinomios :: Num a => [[a]] -> [a]
tal que (sumaPolinomios ps) es la suma de los polinomios ps. Por ejemplo,
λ> sumaPolinomios1 [[0,3,5,9],[10,0,0,9],[8,5,1,-1]] [18,8,6,17] λ> sumaPolinomios6 (replicate 1000000 (replicate 3 1)) [1000000,1000000,1000000]
La matriz zizagueante de orden n es la matriz cuadrada con n filas y n columnas y cuyos elementos son los n² primeros números naturales colocados de manera creciente a lo largo de las diagonales secundarias. Por ejemplo, La matriz zigzagueante de orden 5 es
0 1 5 6 14 2 4 7 13 15 3 8 12 16 21 9 11 17 20 22 10 18 19 23 24
La colocación de los elementos se puede ver gráficamente en
Definir la función
zigZag :: Int -> Array (Int,Int) Int
tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,
λ> elems (zigZag 3) [0,1,5, 2,4,6, 3,7,8] λ> elems (zigZag 4) [0,1,5,6, 2,4,7,12, 3,8,11,13, 9,10,14,15] λ> elems (zigZag 5) [0,1,5,6,14, 2,4,7,13,15, 3,8,12,16,21, 9,11,17,20,22, 10,18,19,23,24] λ> take 15 (elems (zigZag 1000)) [0,1,5,6,14,15,27,28,44,45,65,66,90,91,119]
Definir la función
nMinimoCambios :: Ord a => [a] -> Int
tal que (nMinimoCambios xs) es el menor número de elementos de xs que hay que cambiar para que todos sean iguales. Por ejemplo,
nMinimoCambios [3,5,3,7,9,6] == 4 nMinimoCambios [3,5,3,7,3,3] == 2 nMinimoCambios "Salamanca" == 5 nMinimoCambios (4 : [1..500000]) == 499999
En el primer ejemplo, los elementos que hay que cambiar son 5, 7, 9 y 6.
Definir la función
diagonalesSecundarias :: Matriz a -> [[a]]
tal que (diagonalesSecundarias p) es la lista de las diagonales secundarias de p. Por ejemplo, para la matriz
1 2 3 4 5 6 7 8 9 10 11 12
la lista de sus diagonales secundarias es
[[1],[2,5],[3,6,9],[4,7,10],[8,11],[12]]
En Haskell,
λ> diagonalesSecundarias (listArray ((1,1),(3,4)) [1..12]) [[1],[2,5],[3,6,9],[4,7,10],[8,11],[12]]
La n-ésima densidad de un tipo de número es el cociente entre la cantidad de los números entre 1 y n que son del tipo considerado y n. Por ejemplo, la 7-ésima densidad de los múltiplos de 3 es 2/7 ya que entre los 7 primeros números sólo 2 son múltiplos de 3.
Definir las funciones
densidades :: Int -> (Double,Double,Double) graficas :: Imt -> IO ()
tales que
densidades 100 == (0.22, 2.0e-2, 0.76) densidades 1000 == (0.246, 3.0e-3, 0.751) densidades 10000 == (0.2488, 4.0e-4, 0.7508) densidades 100000 == (0.24795, 4.0e-5, 0.75201)
y (graficas 400) dibuja
Definir la función
sumaDivisoresHasta :: Integer -> [(Integer,Integer)]
tal que (sumaDivisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 1 y n y b es la suma de los divisores propios de a. Por ejemplo,
λ> sumaDivisoresHasta 12 [(1,0),(2,1),(3,1),(4,3),(5,1),(6,6),(7,1),(8,7),(9,4),(10,8),(11,1),(12,16)] λ> maximum (map snd (sumaDivisoresHasta 123456)) 368640
Definir la función
divisoresHasta :: Int -> [(Int,Int)]
tal que (divisoresHasta n) es la lista de los pares (a,b) tales que a es un número entre 2 y n y b es un divisor propio de a. Por ejemplo,
λ> divisoresHasta 6 [(2,1),(3,1),(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)] λ> divisoresHasta 8 [(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(4,2),(6,2),(8,2),(6,3),(8,4)] λ> length (divisoresHasta 1234567) 16272448
La conjetura de Waring sobre los números primos establece que todo número impar es primo o la suma de tres primos. La conjetura de Goldbach afirma que todo número par mayor que 2 es la suma de dos números primos. Ambos problemas siguen abiertos después de más de 200 años. En este problema no se propone su solución, sino una tarea más simple: buscar una manera de expresar los enteros mayores que 7 como suma de exactamente cuatro números primos; es decir, definir la función
suma4primos :: Integer -> (Integer,Integer,Integer,Integer)
tal que (suma4primos n) es una cuádrupla (a,b,c,d) de números primos cuya suma es n (que se supone mayor que 7). Por ejemplo,
suma4primos 24 == (2,2,3,17) suma4primos 1234567890123 == (2,3,29,1234567890089)
Comprobar con QuickCheck que suma4primos es correcta; es decir si (suma4primos n) es (a,b,c,d) entonces los números a, b c y d son primos y su suma es n.
Nota: Para cada n pueden existir distintas cuádruplas que cumplan la especificación. Por ejemplo, para el 16 hay tres: (2,2,5,7), (3,3,3,7) y (3,3,5,5). Cualquiera de ellas se admite como solución.
Definir la función
mezclaTodas :: Ord a => [[a]] -> [a]
tal que (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como sus elementos son listas infinitas ordenadas. Por ejemplo,
λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]]) [2,3,4,5,6,7,8,9,10,11] λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]]) [2,4,6,8,9,10,12,14,16,18]
Un número n es abundante si la suma de los divisores propios de n es mayor que n. El primer número abundante es el 12 (cuyos divisores propios son 1, 2, 3, 4 y 6 cuya suma es 16). Por tanto, el menor número que es la suma de dos números abundantes es el 24.
Definir la sucesión
sumasDeDosAbundantes :: [Integer]
cuyos elementos son los números que se pueden escribir como suma de dos números abundantes. Por ejemplo,
take 10 sumasDeDosAbundantes == [24,30,32,36,38,40,42,44,48,50]
Nota: La sucesión sumasDeDosAbundantes coincide con la sucesión A048260 de The On-Line Encyclopedia of Integer Sequences.
Definir la función
diagonalesPrincipales :: Matriz a -> [[a]]
tal que (diagonalesPrincipales p) es la lista de las diagonales principales de p. Por ejemplo, para la matriz
1 2 3 4 5 6 7 8 9 10 11 12
la lista de sus diagonales principales es
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
En Haskell,
λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
Definir la función
segmentos :: Int -> [a] -> [[a]]
tal que (segmentos n xs) es la lista de los segmentos de longitud n de la lista xs. Por ejemplo,
segmentos 3 [1..5] == [[1,2,3],[2,3,4],[3,4,5]]
Definir la función
esPotenciaDeDos :: Integer -> Bool
tal que (esPotenciaDeDos n) se verifica si n es una potencia de dos (suponiendo que n es mayor que 0). Por ejemplo.
esPotenciaDeDos 1 == True esPotenciaDeDos 2 == True esPotenciaDeDos 6 == False esPotenciaDeDos 8 == True esPotenciaDeDos 1024 == True esPotenciaDeDos 1026 == False esPotenciaDeDos (2^100000) == True
Nota: Comprobar la definición para grandes potencias de 2.
La sucesión de los números triangulares se obtiene sumando los números naturales.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 1 3 6 10 15
Así, el 7º número triangular es
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.
Los primeros 10 números triangulares son
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Los divisores de los primeros 7 números triangulares son:
1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28
Como se puede observar, 28 es el menor número triangular con más de 5 divisores.
Definir la función
menorTriangularConAlMenosNDivisores :: Int -> Integer
tal que (menorTriangularConAlMenosNDivisores n) es el menor número triangular que tiene al menos n divisores. Por ejemplo,
menorTriangularConAlMenosNDivisores 5 == 28 menorTriangularConAlMenosNDivisores 50 == 25200 menorTriangularConAlMenosNDivisores 500 == 76576500
Definir la función
dosCuadrados :: Picture
que dibuje dos cuadrados encajados como se muestra en la siguiente figura
Nota: Escribir las soluciones usando la siguiente plantilla
import Graphics.Gloss main :: IO () main = display (InWindow "Dibujo" (500,300) (20,20)) white dosCuadrados dosCuadrados :: Picture dosCuadrados = undefined
