Las matrices se pueden representar como lista de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.
Definir la función
diagonal :: [[a]] -> [a]
tal que (diagonal xss) es la diagonal de la matriz xss. Por ejemplo,
diagonal [[3,5,2],[4,7,1],[6,9,0]] == [3,7,0] diagonal [[3,5],[4,7],[6,9]] == [3,7] diagonal [[3,5,2],[4,7,1]] == [3,7] sum (diagonal (replicate 20000 [1..20000])) == 200010000
Definir la función
sumas :: Int -> [Int] -> [Int]
tal que (sumas n xs) es la lista de los números que se pueden obtener como suma de n, o menos, elementos de xs. Por ejemplo,
sumas 0 [2,5] == [0] sumas 1 [2,5] == [0,2,5] sumas 2 [2,5] == [0,2,4,5,7,10] sumas 3 [2,5] == [0,2,4,5,6,7,9,10,12,15] sumas 2 [2,3,5] == [0,2,3,4,5,6,7,8,10] sumas 3 [2,3,5] == [0,2,3,4,5,6,7,8,9,10,11,12,13,15] length (sumas 8 [1..200]) == 1601
Los árboles binarios con datos en los nodos y hojas se definen por
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Eq, Show)
Por ejemplo, el árbol
3
/ \
/ \
4 7
/ \ / \
5 0 0 3
/ \
2 0
se representa por
ejArbol :: Arbol Integer ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))
Anotando cada elemento del árbol anterior con su profundidad, se obtiene el árbol siguiente
3-0
/ \
/ \
/ \
4-1 7-1
/ \ / \
5-2 0-2 0-2 3-0
/ \
2-3 0-3
Definir la función
anotado :: Arbol a -> Arbol (a,Int)
tal que (anotado x) es el árbol obtenido anotando los elementos de x con su profundidad. Por ejemplo,
λ> anotado ejArbol N (3,0) (N (4,1) (N (5,2) (H (2,3)) (H (0,3))) (H (0,2))) (N (7,1) (H (0,2)) (H (3,2)))
Definir la función
compactada :: [Maybe Int] -> [Int]
tal que (compacta xs) es la lista obtenida al compactar xs con las siguientes reglas:
Por ejemplo,
λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6] [2,5,3,6] λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6] [2,1,4,3,6] λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6] [2,1,5,6] λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4] [2,1,4,3,4] λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4] [2,2,4,3,4]
Definir la función
sinEspaciosExtremos :: String -> String
tal que (sinEspaciosExtremos cs) es la cadena obtenida eliminando los espacios blancos de los extremos de la cadena cs. Por ejemplo,
λ> sinEspaciosExtremos " El lunes a las 12:30. " "El lunes a las 12:30."
Sea \( n \) un número natural cuya factorización prima es \[ n = 2^a \cdot p_1^{b_1} \cdots p_n^{b_n} \cdot q_1^{c_1} \cdots q_m^{c_m} \] donde los \( p_i \) son los divisores primos de \( n \) congruentes con \( 3 \) módulo \( 4 \) y los \( q_j \) son los divisores primos de \( n \) congruentes con \( 1 \) módulo \( 4 \). Entonces, el número de formas de descomponer \( n \) como suma de dos cuadrados es \( 0 \), si algún \( b_i \) es impar y es el techo (es decir, el número entero más próximo por exceso) de \[ \frac{(1+c_1) \cdots (1+c_m)}{2} \] en caso contrario. Por ejemplo, el número \( 2^3 \cdot (3^9 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) no se puede descomponer como sumas de dos cuadrados (porque el exponente de \( 3 \) es impar) y el número \( 2^3 \cdot (3^2 \cdot 7^8) \cdot (5^3 \cdot 13^6) \) tiene \( 14 \) descomposiciones como suma de dos cuadrados (porque los exponentes de \( 3 \) y \( 7 \) son pares y el techo de \( \frac{(1+3)(1+6)}{2} \) es \( 14 \)).
Definir la función
nRepresentaciones :: Integer -> Integer
tal que (nRepresentaciones n) es el número de formas de representar n como suma de dos cuadrados. Por ejemplo,
nRepresentaciones (2^3*3^9*5^3*7^8*13^6) == 0 nRepresentaciones (2^3*3^2*5^3*7^8*13^6) == 14 head [n | n <- [1..], nRepresentaciones n > 8] == 71825
Usando la función representaciones del ejercicio anterior, comprobar con QuickCheck la siguiente propiedad
prop_nRepresentaciones :: Integer -> Property prop_nRepresentaciones n = n > 0 ==> nRepresentaciones2 n == genericLength (representaciones n)
Definir la función
representaciones :: Integer -> [(Integer,Integer)]
tal que (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2. Por ejemplo.
representaciones 20 == [(2,4)] representaciones 25 == [(0,5),(3,4)] representaciones 325 == [(1,18),(6,17),(10,15)] representaciones 100000147984 == [(0,316228)]
Comprobar con QuickCheck que un número natural n se puede representar como suma de dos cuadrados si, y sólo si, en la factorización prima de n todos los exponentes de sus factores primos congruentes con 3 módulo 4 son pares.
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...
Definir la función
factorizacionesH :: Integer -> [[Integer]]
tal que (factorizacionesH n) es la listas de primos de Hilbert cuyo producto es el número de Hilbert n. Por ejemplo,
factorizacionesH 25 == [[5,5]] factorizacionesH 45 == [[5,9]] factorizacionesH 441 == [[9,49],[21,21]]
Comprobar con QuickCheck que todos los números de Hilbert son factorizables como producto de primos de Hilbert (aunque laa factorización, como para el 441, puede no ser única).
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, ...
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, ...
Definir la sucesión
primosH :: [Integer]
tal que sus elementos son los primos de Hilbert. Por ejemplo,
take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! 20000 == 203221
La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son
[0] [0,1] [0,1,1,0] [0,1,1,0,1,0,0,1] [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]
De esta forma se va formando una sucesión
0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,...
que se conoce como la sucesión de Thue-Morse.
Definir la sucesión
sucThueMorse :: [Int]
cuyos elementos son los de la sucesión de Thue-Morse. Por ejemplo,
λ> take 30 sucThueMorse [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0] λ> map (sucThueMorse4 !!) [1234567..1234596] [1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1,0,0,1,0] λ> map (sucThueMorse4 !!) [4000000..4000030] [1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,0,0,1,0,1,1]
Comprobar con QuickCheck que si s(n) representa el término n-ésimo de la sucesión de Thue-Morse, entonces
s(2n) = s(n) s(2n+1) = 1 - s(n)