Máximo de tres números
Definir la función
maxTres :: Int -> Int -> Int -> Int
tal que (maxTres x y z) es el máximo de x, y y z. Por ejemplo,
maxTres 6 2 4 == 6 maxTres 6 7 4 == 7 maxTres 6 7 9 == 9
Último dígito
Definir la función
ultimoDigito :: Int -> Int
tal que (ultimoDigito x) es el último dígito del número x. Por ejemplo,
ultimoDigito 325 == 5
Área de la corona circular
Definir la función
areaDeCoronaCircular :: Double -> Double -> Double
tal que (areaDeCoronaCircular r1 r2) es el área de una corona circular de radio interior r1 y radio exterior r2. Por ejemplo,
areaDeCoronaCircular 1 2 == 9.42477796076938 areaDeCoronaCircular 2 5 == 65.97344572538566 areaDeCoronaCircular 3 5 == 50.26548245743669
Volumen de la esfera
Definir la función
volumenEsfera :: Double -> Double
tal que (volumenEsfera r) es el volumen de la esfera de radio r. Por ejemplo,
volumenEsfera 10 == 4188.790204786391
Suma si todos los valores son justos
Definir la función
sumaSiTodosJustos :: (Num a, Eq a) => [Maybe a] -> Maybe a
tal que (sumaSiTodosJustos xs) es justo la suma de todos los elementos de xs si todos son justos (es decir, si Nothing no pertenece a xs) y Nothing en caso contrario. Por ejemplo,
sumaSiTodosJustos [Just 2, Just 5] == Just 7 sumaSiTodosJustos [Just 2, Just 5, Nothing] == Nothing
Media aritmética de tres números.
Definir la función
media3 :: Float -> Float -> Float -> Float
tal que (media3 x y z) es la media aritmética de los números x, y y z. Por ejemplo,
media3 1 3 8 == 4.0 media3 (-1) 0 7 == 2.0 media3 (-3) 0 3 == 0.0
Curso de introducción a la programación con Haskell y Python
Mañana comenzará en en este blog un curso práctico de introducción a la programación con Haskell y Python.
Diariamente, se publicará un ejercicio con sus soluciones en Haskell y en Python. El orden de los ejercicios se corresponde con el de los temas del curso de Programación funcional con Haskell. Además, en cada ejercicio se comentarán las diferencias entre ambos lenguajes y se irá extendiendo la tabla de equivalencia entre Haskell y Python.
Sumas de dos primos
Definir la sucesión
sumasDeDosPrimos :: [Integer]
cuyos elementos son los números que se pueden escribir como suma de dos números primos. Por ejemplo,
λ> take 23 sumasDeDosPrimos [4,5,6,7,8,9,10,12,13,14,15,16,18,19,20,21,22,24,25,26,28,30,31] λ> sumasDeDosPrimos !! (5*10^5) 862878
La sucesión de Thue-Morse
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)
La serie de Thue-Morse
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 (es decir, la lista obtenida cambiando el 0 por 1 y el 1 por 0). 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]
Definir la lista
serieThueMorse :: [[Int]]
tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,
λ> take 4 serieThueMorse [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]
Números belgas
Un número n es k-belga si la sucesión cuyo primer elemento es k y cuyos elementos se obtienen sumando reiteradamente las cifras de n contiene a n.
El 18 es 0-belga, porque a partir del 0 vamos a ir sumando sucesivamente 1, 8, 1, 8, ... hasta llegar o sobrepasar el 18: 0, 1, 9, 10, 18, ... Como se alcanza el 18, resulta que el 18 es 0-belga.
El 19 no es 1-belga, porque a partir del 1 vamos a ir sucesivamente 1, 9, 1, 9, ... hasta llegar o sobrepasar el 18: 0, 1, 10, 11, 20, 21, ... Como no se alcanza el 19, resulta que el 19 no es 1-belga.
Definir la función
esBelga :: Int -> Int -> Bool
tal que (esBelga k n) se verifica si n es k-belga. Por ejemplo,
esBelga 0 18 == True esBelga 1 19 == False esBelga 0 2016 == True [x | x <- [0..30], esBelga 7 x] == [7,10,11,21,27,29] [x | x <- [0..30], esBelga 10 x] == [10,11,20,21,22,24,26] length [n | n <- [1..10^6], esBelga 0 n] == 272049
Comprobar con QuickCheck que para todo número entero positivo n, si k es el resto de n entre la suma de los dígitos de n, entonces n es k-belga.
Huecos maximales entre primos
El hueco de un número primo p es la distancia entre p y primo siguiente de p. Por ejemplo, el hueco de 7 es 4 porque el primo siguiente de 7 es 11 y 4 = 11-7. Los huecos de los primeros números son
Primo Hueco 2 1 3 2 7 4 11 2
El hueco de un número primo p es maximal si es mayor que huecos de todos los números menores que p. Por ejemplo, 4 es un hueco maximal de 7 ya que los huecos de los primos menores que 7 son 1 y 2 y ambos son menores que 4. La tabla de los primeros huecos maximales es
Primo Hueco 2 1 3 2 7 4 23 6 89 8 113 14 523 18 887 20
Definir la sucesión
primosYhuecosMaximales :: [(Integer,Integer)]
cuyos elementos son los números primos con huecos maximales junto son sus huecos. Por ejemplo,
λ> take 8 primosYhuecosMaximales [(2,1),(3,2),(7,4),(23,6),(89,8),(113,14),(523,18),(887,20)] λ> primosYhuecosMaximales !! 20 (2010733,148)
La función indicatriz de Euler
La indicatriz de Euler (también función φ de Euler) es una función importante en teoría de números. Si n es un entero positivo, entonces φ(n) se define como el número de enteros positivos menores o iguales a n y coprimos con n. Por ejemplo, φ(36) = 12 ya que los números menores o iguales a 36 y coprimos con 36 son doce: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, y 35.
Definir la función
phi :: Integer -> Integer
tal que (phi n) es igual a φ(n). Por ejemplo,
phi 36 == 12 map phi [10..20] == [4,10,4,12,6,8,8,16,6,18,8] phi (3^10^5) `mod` (10^9) == 681333334 length (show (phi (10^(10^5)))) == 100000
Comprobar con QuickCheck que, para todo n > 0, φ(10^n) tiene n dígitos.
Sucesión de suma de cuadrados de los dígitos
Definir la función
sucSumaCuadradosDigitos :: Integer -> [Integer]
tal que (sucSumaCuadradosDigitos n) es la sucesión cuyo primer término es n y los restantes se obtienen sumando los cuadrados de los dígitos de su término anterior. Por ejemplo,
λ> take 20 (sucSumaCuadradosDigitos1 2000) [2000,4,16,37,58,89,145,42,20,4,16,37,58,89,145,42,20,4,16,37] λ> take 20 (sucSumaCuadradosDigitos 1976) [1976,167,86,100,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] λ> sucSumaCuadradosDigitos 2000 !! (10^9) 20
Potencias perfectas
Un número natural n es una potencia perfecta si existen dos números naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son
4 = 2², 8 = 2³, 9 = 3², 16 = 2⁴, 25 = 5², 27 = 3³, 32 = 2⁵, 36 = 6², 49 = 7², 64 = 2⁶, ...
Definir la sucesión
potenciasPerfectas :: [Integer]
cuyos términos son las potencias perfectas. Por ejemplo,
take 10 potenciasPerfectas == [4,8,9,16,25,27,32,36,49,64] potenciasPerfectas !! 3000 == 7778521
Definir el procedimiento
grafica :: Int -> IO ()
tal que (grafica n) es la representación gráfica de las n primeras potencias perfectas. Por ejemplo, para (grafica 30) dibuja
Sumas alternas de factoriales
Las primeras sumas alternas de los factoriales son números primos; en efecto,
3! - 2! + 1! = 5 4! - 3! + 2! - 1! = 19 5! - 4! + 3! - 2! + 1! = 101 6! - 5! + 4! - 3! + 2! - 1! = 619 7! - 6! + 5! - 4! + 3! - 2! + 1! = 4421 8! - 7! + 6! - 5! + 4! - 3! + 2! - 1! = 35899
son primos, pero
9! - 8! + 7! - 6! + 5! - 4! + 3! - 2! + 1! = 326981
no es primo.
Definir las funciones
sumaAlterna :: Integer -> Integer sumasAlternas :: [Integer] conSumaAlternaPrima :: [Integer]
tales que
- (sumaAlterna n) es la suma alterna de los factoriales desde n hasta 1. Por ejemplo,
sumaAlterna 3 == 5 sumaAlterna 4 == 19 sumaAlterna 5 == 101 sumaAlterna 6 == 619 sumaAlterna 7 == 4421 sumaAlterna 8 == 35899 sumaAlterna 9 == 326981 sumaAlterna (5*10^4) `mod` (10^6) == 577019
- sumasAlternas es la sucesión de las sumas alternas de factoriales. Por ejemplo,
λ> take 10 sumasAlternas1 [0,1,1,5,19,101,619,4421,35899,326981]
- conSumaAlternaPrima es la sucesión de los números cuya suma alterna de factoriales es prima. Por ejemplo,
λ> take 8 conSumaAlternaPrima [3,4,5,6,7,8,10,15]
Primos con cubos
Un primo con cubo es un número primo p para el que existe algún entero positivo n tal que la expresión n^3 + n^2p es un cubo perfecto. Por ejemplo, 19 es un primo con cubo ya que 8^3 + 8^2×19 = 12^3.
Definir la sucesión
primosConCubos :: [Integer]
tal que sus elementos son los primos con cubo. Por ejemplo,
λ> take 6 primosConCubos [7,19,37,61,127,271] λ> length (takeWhile (<1000000) primosConCubos) 173
Primos cubanos
Un primo cubano es un número primo que se puede escribir como diferencia de dos cubos consecutivos. Por ejemplo, el 61 es un primo cubano porque es primo y 61 = 5³-4³.
Definir la sucesión
cubanos :: [Integer]
tal que sus elementos son los números cubanos. Por ejemplo,
λ> take 15 cubanos [7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]
Clausura transitiva de una relación binaria
La clausura transitiva de una relación binaria R es la relación transitiva que contiene a R. Se puede calcular usando la composición de relaciones. Veamos un ejemplo, en el que (R ∘ S) representa la composición de R y S: sea
R = [(1,2),(2,5),(5,6)]
la relación R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea
R1 = R ∪ (R ∘ R) = [(1,2),(2,5),(5,6),(1,5),(2,6)]
la relación R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea
R2 = R1 ∪ (R1 ∘ R1) = [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]
La relación R2 es transitiva y contiene a R. Además, R2 es la clausura transitiva de R.
Definir la función
clausuraTransitiva :: Ord a => [(a,a)] -> [(a,a)]
tal que (clausuraTransitiva r) es la clausura transitiva de r; es decir, la menor relación transitiva que contiene a r. Por ejemplo,
λ> clausuraTransitiva [(1,2),(2,5),(5,6)] [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)] λ> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)] [(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)] λ> length (clausuraTransitiva [(n,n+1) | n <- [1..100]]) 5050
Transitividad de una relación
Una relación binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el tercero.
Definir la función
transitiva :: Ord a => [(a,a)] -> Bool
tal que (transitiva r) se verifica si la relación r es transitiva. Por ejemplo,
transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)] == True transitiva [(1,1),(1,3),(3,1),(5,5)] == False transitiva [(n,n) | n <- [1..10^4]] == True
Composición de relaciones binarias
Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relación de divisibilidad en el conjunto {1,2,3,6} se representa por
[(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]
La composición de dos relaciones binarias R y S en el conjunto A es la relación binaria formada por los pares (x,y) para los que existe un z tal que (x,z) ∈ R y (z,y) ∈ S.
Definir la función
composicion :: Ord a => [(a,a)] -> [(a,a)] -> [(a,a)]
tal que (composicion r s) es la composición de las relaciones binarias r y s. Por ejemplo,
λ> composicion [(1,2)] [(2,3),(2,4)] [(1,3),(1,4)] λ> composicion [(1,2),(5,2)] [(2,3),(2,4)] [(1,3),(1,4),(5,3),(5,4)] λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)] [(1,3)]
Nota: Se supone que las relaciones binarias son listas sin elementos repetidos.
Número de particiones en k subconjuntos
Definir la función
numeroParticiones :: Int -> Int -> Int
tal que (numeroParticiones n k) es el número de particiones de conjunto de n elementos en k subconjuntos disjuntos. Por ejemplo,
numeroParticiones 3 2 == 3 numeroParticiones 3 3 == 1 numeroParticiones 4 3 == 6 numeroParticiones 4 1 == 1 numeroParticiones 4 4 == 1 numeroParticiones 91 89 == 8139495
Particiones en k subconjuntos
Definir la función
particiones :: [a] -> Int -> [[[a]]]
tal que (particiones xs k) es la lista de las particiones de xs en k subconjuntos disjuntos. Por ejemplo,
λ> particiones [2,3,6] 2 [[[2],[3,6]],[[2,3],[6]],[[3],[2,6]]] λ> particiones [2,3,6] 3 [[[2],[3],[6]]] λ> particiones [4,2,3,6] 3 [[[4],[2],[3,6]],[[4],[2,3],[6]],[[4],[3],[2,6]], [[4,2],[3],[6]],[[2],[4,3],[6]],[[2],[3],[4,6]]] λ> particiones [4,2,3,6] 1 [[[4,2,3,6]]] λ> particiones [4,2,3,6] 4 [[[4],[2],[3],[6]]]
Mayor semiprimo menor que n
Un número semiprimo es un número natural es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2·13) y 49 también lo es (porque 49 = 7·7).
Definir la función
mayorSemiprimoMenor :: Integer -> Integer
tal que (mayorSemiprimoMenor n) es el mayor semiprimo menor que n (suponiendo que n > 4). Por ejemplo,
mayorSemiprimoMenor 27 == 26 mayorSemiprimoMenor 50 == 49 mayorSemiprimoMenor 49 == 46 mayorSemiprimoMenor (10^15) == 999999999999998
Intersecciones parciales
Definir la función
interseccionParcial :: Ord a => Int -> [[a]] -> [a]
tal que (interseccionParcial n xss) es la lista de los elementos que pertenecen al menos a n conjuntos de xss. Por ejemplo,
interseccionParcial 1 [[3,4],[4,5,9],[5,4,7]] == [3,4,5,9,7] interseccionParcial 2 [[3,4],[4,5,9],[5,4,7]] == [4,5] interseccionParcial 3 [[3,4],[4,5,9],[5,4,7]] == [4] interseccionParcial 4 [[3,4],[4,5,9],[5,4,7]] == []
Unión e intersección general de conjuntos
Definir las funciones
unionGeneral :: Eq a => [[a]] -> [a] interseccionGeneral :: Eq a => [[a]] -> [a]
tales que
- (unionGeneral xs) es la unión de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a alguno de los elementos de xs). Por ejemplo,
unionGeneral [] == [] unionGeneral [[1]] == [1] unionGeneral [[1],[1,2],[2,3]] == [1,2,3] unionGeneral ([[x] | x <- [1..9]]) == [1,2,3,4,5,6,7,8,9]
- (interseccionGeneral xs) es la intersección de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a todos los elementos de xs). Por ejemplo,
interseccionGeneral [[1]] == [1] interseccionGeneral [[2],[1,2],[2,3]] == [2] interseccionGeneral [[2,7,5],[1,5,2],[5,2,3]] == [2,5] interseccionGeneral ([[x] | x <- [1..9]]) == [] interseccionGeneral (replicate (10^6) [1..5]) == [1,2,3,4,5]
Ceros finales del factorial
Definir la función
cerosDelFactorial :: Integer -> Integer
tal que (cerosDelFactorial n) es el número de ceros en que termina el factorial de n. Por ejemplo,
cerosDelFactorial 24 == 4 cerosDelFactorial 25 == 6 length (show (cerosDelFactorial (10^70000))) == 70000
Números autodescriptivos
Un número n es autodescriptivo cuando para cada posición k de n (empezando a contar las posiciones a partir de 0), el dígito en la posición k es igual al número de veces que ocurre k en n. Por ejemplo, 1210 es autodescriptivo porque tiene 1 dígito igual a "0", 2 dígitos iguales a "1", 1 dígito igual a "2" y ningún dígito igual a "3".
Definir la función
autodescriptivo :: Integer -> Bool
tal que (autodescriptivo n) se verifica si n es autodescriptivo. Por ejemplo,
λ> autodescriptivo 1210 True λ> [x | x <- [1..100000], autodescriptivo x] [1210,2020,21200] λ> autodescriptivo 9210000001000 True
Aproximación del número pi
Una forma de aproximar el número π es usando la siguiente igualdad: \[ \frac{\pi}{2} = 1 + \frac{1}{3} + \frac{1 \cdot 2}{3 \cdot 5} + \frac{1 \cdot 2 \cdot 3}{3 \cdot 5 \cdot 7} + \frac{1 \cdot 2 \cdot 3 \cdot 4}{3 \cdot 5 \cdot 7 \cdot 9} + \cdots \]
Es decir, la serie cuyo término general n-ésimo es el cociente entre el producto de los primeros n números y los primeros n números impares: \[ s(n) = \frac{\prod\limits_{i=1}^n i}{\prod\limits_{i=1}^n (2i + 1)} \]
Definir la función
aproximaPi :: Integer -> Double
tal que (aproximaPi n) es la aproximación del número π calculada con la serie anterior hasta el término n-ésimo. Por ejemplo,
aproximaPi 10 == 3.1411060206 aproximaPi 20 == 3.1415922987403397 aproximaPi 30 == 3.1415926533011596 aproximaPi 40 == 3.1415926535895466 aproximaPi 50 == 3.141592653589793 aproximaPi (10^4) == 3.141592653589793 pi == 3.141592653589793
Pandigitales primos
Un número con n dígitos es pandigital si contiene todos los dígitos del 1 a n exactamente una vez. Por ejemplo, 2143 es un pandigital con 4 dígitos y, además, es primo.
Definir la lista
pandigitalesPrimos :: [Int]
tal que sus elementos son los números pandigitales primos, ordenados de mayor a menor. Por ejemplo,
take 3 pandigitalesPrimos == [7652413,7642513,7641253] 2143 `elem` pandigitalesPrimos == True length pandigitalesPrimos == 538
Codificación de Fibonacci
La codificación de Fibonacci de un número n es una cadena d = d(0)d(1)...d(k-1)d(k) de ceros y unos tal que
n = d(0)·F(2) + d(1)·F(3) +...+ d(k-1)·F(k+1) d(k-1) = d(k) = 1
donde F(i) es el i-ésimo término de la sucesión de Fibonacci
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Por ejemplo, la codificación de Fibonacci de 4 es "1011" ya que los dos últimos elementos son iguales a 1 y
1·F(2) + 0·F(3) + 1·F(4) = 1·1 + 0·2 + 1·3 = 4
La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla
1 = 1 = F(2) ≡ 11 2 = 2 = F(3) ≡ 011 3 = 3 = F(4) ≡ 0011 4 = 1+3 = F(2)+F(4) ≡ 1011 5 = 5 = F(5) ≡ 00011 6 = 1+5 = F(2)+F(5) ≡ 10011 7 = 2+5 = F(3)+F(5) ≡ 01011 8 = 8 = F(6) ≡ 000011 9 = 1+8 = F(2)+F(6) ≡ 100011 10 = 2+8 = F(3)+F(6) ≡ 010011 11 = 3+8 = F(4)+F(6) ≡ 001011 12 = 1+3+8 = F(2)+F(4)+F(6) ≡ 101011 13 = 13 = F(7) ≡ 0000011 14 = 1+13 = F(2)+F(7) ≡ 1000011
Definir la función
codigoFib :: Integer -> String
tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,
λ> codigoFib 65 "0100100011" λ> [codigoFib n | n <- [1..7]] ["11","011","0011","1011","00011","10011","01011"]
Comprobar con QuickCheck las siguientes propiedades:
- Todo entero positivo se puede descomponer en suma de números de la sucesión de Fibonacci.
- Las codificaciones de Fibonacci tienen como mínimo 2 elementos.
- En las codificaciones de Fibonacci, la cadena "11" sólo aparece una vez y la única vez que aparece es al final.
La sucesión del reloj astronómico de Praga
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 sucesión 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] λ> (reloj !! 1000) `mod` (10^50) 23432123432123432123432123432123432123432123432123
Nota: La relación entre la sucesión y el funcionamiento del reloj se puede ver en The Mathematics Behind Prague's Horloge Introduction.
Método de bisección para aproximar raíces de funciones
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:
- Si |f(c)| < e, hemos encontrado una aproximación del punto que anula f en el intervalo con un error aceptable.
- Si f(c) tiene signo distinto de f(a), repetir el proceso en el intervalo [a,c].
- Si no, repetir el proceso en el intervalo [c,b].
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
Números para los que el mcm de 1,2,...n-1 coincide con el de 1,2,...,n
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
Cálculo de la suma 1·1! + 2·2! + 3·3! + ... + n·n!
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"
Cálculo aproximado de integrales definidas
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
Menor número con una cantidad dada de divisores
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 4 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 8 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 16 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.
Definir la función
menor :: Integer -> Integer
tal que (menor n) es el menor número con 2^n divisores. Por ejemplo,
menor 1 == 2 menor 2 == 6 menor 3 == 24 menor 4 == 120 length (show (menor (4*10^4))) == 207945
Comprobar con QuickCheck que, para todo k >=0, (menor (2^k)) es un divisor de (menor (2^(k+1))).
Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2011.
Distancia esperada entre dos puntos de un cuadrado unitario
Definir, por simulación, la función
distanciaEsperada :: Int -> IO 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.43903617921423593 distanciaEsperada 10 == 0.6342350621260004 distanciaEsperada 100 == 0.5180418995364429 distanciaEsperada 100 == 0.5288261085653962 distanciaEsperada 1000 == 0.5143804432569616 distanciaEsperada 10000 == 0.5208360147922616
El valor exacto de la distancia esperada es \[ ve = \frac{\sqrt{2} + 2 + 5 \log(1 + \sqrt{2})}{15} \approx 0.5214054331647207 \]
Definir la función
graficaDistanciaEsperada :: [Int] -> IO ()
tal que (graficaDistanciaEsperada ns) dibuja las gráficas de los pares (n, distanciaEsperada n) para n en la lista creciente ns junto con la recta y = ve, donde ve es el valor exacto. Por ejemplo, (graficaDistanciaEsperada [10,30..4000]) dibuja
Representación matricial de relaciones binarias
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
Codificación de Gödel
Dada una lista de números naturales xs, codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificación de xs es \[2^7 \times 3^1 \times 5^5 = 1200000 \]
Definir las funciones
codificaG :: [Integer] -> Integer decodificaG :: Integer -> [Integer]
tales que
-
(codificaG xs)es la codificación de Gödel dexs. Por ejemplo,
codificaG [6,0,4] == 1200000 codificaG [3,1,1] == 3600 codificaG [3,1,0,0,0,0,0,1] == 4423058640 codificaG [1..6] == 126111168580452537982500
-
(decodificaG n)es la lista xs cuya codificación esn. Por ejemplo,
decodificaG 1200000 == [6,0,4] decodificaG 3600 == [3,1,1] decodificaG 4423058640 == [3,1,0,0,0,0,0,1] decodificaG 126111168580452537982500 == [1,2,3,4,5,6]
Comprobar con QuickCheck que ambas funciones son inversas; es decir,
decodificaG (codificaG xs) = xs codificaG (decodificaG n) = n
Primos circulares
Un primo circular es un número tal que todas las rotaciones de 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 lista
circulares :: [Integer]
cuyo valor es la lista de los números primos circulares. Por ejemplo,
take 16 circulares == [2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,197] circulares !! 50 == 933199
Diccionario de frecuencias
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
Descomposiciones con sumandos 1 ó 2
Definir la funciones
sumas :: Int -> [[Int]] nSumas :: Int -> Integer
tales que
-
(sumas n)es la lista de las descomposiciones dencomo sumas cuyos sumandos son 1 ó 2. Por ejemplo,
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 n)es el número de descomposiciones dencomo sumas cuyos sumandos son 1 ó 2. Por ejemplo,
nSumas 4 == 5 nSumas 123 == 36726740705505779255899443 length (show (nSumas 123456)) == 25801
Suma de los elementos de las diagonales matrices espirales
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
+ en la 2x2: 1+3+2+4 = 10 + en la 3x3: 1+3+5+7+9 = 25 + en la 4x4: 1+2+3+4+7+10+13+16 = 56 + en la 5x5: 1+3+5+7+9+13+17+21+25 = 101
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 (10^6) == 666667166668000000 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.
Término ausente en una progresión aritmética
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 ausente ([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 un término de la progresión aritmética que no está en la lista.
Polinomios de Bell
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ₙ'(x) es la derivada de Bₙ(x))
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 2000))) == 1903
Notas: Se usa la librería I1M.PolOperaciones. 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 => Int -> Polinomio a -> a coeficiente k p | k == n = coefLider p | k > grado (restoPol p) = 0 | otherwise = coeficiente k (restoPol p) where n = grado p
Ordenación de los racionales
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)]
Polinomios cuadráticos generadores de primos
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ó que el polinomio n² - 79n + 1601 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
-
xses la lista de pares(x,y)tales quen²+xn+yes uno de polinomios que genera un número máximo de números primos consecutivos a partir de cero entre todos los polinomios de la forman²+an+b, con|a| ≤ ny|b| ≤ ny -
mes dicho número máximo.
Por ejemplo,
generadoresMaximales 4 == ( 3,[(-2,3),(-1,3),(3,3)]) generadoresMaximales 6 == ( 5,[(-1,5),(5,5)]) generadoresMaximales 41 == (41,[(-1,41)]) 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
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
Numeración con base múltiple
Matriz zigzagueante
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 este enlace.
Definir la función
zigZag :: Int -> Matrix Int
tal que (zigZag n) es la matriz zigzagueante de orden n. Por ejemplo,
λ> 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 │ └ ┘ λ> zigZag 4 ┌ ┐ │ 0 1 5 6 │ │ 2 4 7 12 │ │ 3 8 11 13 │ │ 9 10 14 15 │ └ ┘ λ> maximum (zigZag 1500) 2249999
Densidades de números abundantes, perfectos y deficientes
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 :: Int -> IO ()
tales que
-
(densidades n)es la terna formada por la n-ésima densidad de los números abundantes (es decir, para que la suma de sus divisores propios es mayor que el número), de los números perfectos (es decir, para los que la suma de sus divisores propios es mayor que el número) y de los números deficientes (es decir, para los que la suma de sus divisores propios es menor que el número). Por ejemplo,
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) densidades 1000000 == (0.247545,4.0e-6, 0.752451)
-
(graficas n)dibuja las gráficas de las k-ésimas densidades (para k entre 1 y n) de los números abundantes, de los números perfectos y de los números deficientes. Por ejemplo,(graficas 100)dibuja
y (graficas 400) dibuja
Sumas de divisores propios
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)] λ> last (sumaDivisoresHasta2 (10^7)) (10000000,14902280)
Parejas de números y divisores
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
Sumas de 4 primos
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 par mayor que 2 es la suma de dos números primos. Ambos ha estado abiertos durante 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 la lista de las cuádruplas crecientes (a,b,c,d) de números primos cuya suma es n (que se supone mayor que 7). Por ejemplo,
suma4primos 18 == [(2,2,3,11),(2,2,7,7),(3,3,5,7),(3,5,5,5)] head (suma4primos (10^14)) == (2,2,23,99999999999973)
Comprobar con QuickCheck que todo entero mayor que 7 se puede escribir como suma de exactamente cuatro números primos.
Sucesión de sumas de dos números abundantes
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]
Suma de divisores
Definir la función
sumaDivisores :: Integer -> Integer
tal que (sumaDivisores x) es la suma de los divisores de x. Por ejemplo,
sumaDivisores 12 == 28 sumaDivisores 25 == 31 sumaDivisores (product [1..25]) == 93383273455325195473152000 length (show (sumaDivisores (product [1..30000]))) == 121289 maximum (map sumaDivisores [1..10^5]) == 403200
Número de divisores
Definir la función
numeroDivisores :: Integer -> Integer
tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,
numeroDivisores 12 == 6 numeroDivisores 25 == 3 length (show (numeroDivisores (product [1..3*10^4]))) == 1948
Conjunto de divisores
Definir la función
divisores :: Integer -> [Integer]
tal que (divisores x) es el conjunto de divisores de x. Por ejemplo,
divisores 30 == [1,2,3,5,6,10,15,30] length (divisores (product [1..10])) == 270 length (divisores (product [1..25])) == 340032
Reconocimiento de potencias de 2
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^(10^8)) == True
Particiones de enteros positivos
Una [partición)(https://en.wikipedia.org/wiki/Integer_partition) de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.
Definir la función
particiones :: Int -> [[Int]]
tal que (particiones n) es la lista de las particiones del número n. Por ejemplo,
particiones 4 == [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] particiones 5 == [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]] length (particiones 50) == 204226
Mínimo producto escalar
El producto escalar de los vectores [a1,a2,...,an] y [b1,b2,..., bn] es
a1 * b1 + a2 * b2 + ··· + an * bn.
Definir la función
menorProductoEscalar :: (Ord a, Num a) => [a] -> [a] -> a
tal que (menorProductoEscalar xs ys) es el mínimo de los productos
escalares de las permutaciones de xs y de las permutaciones de
ys. Por ejemplo,
menorProductoEscalar [3,2,5] [1,4,6] == 29 menorProductoEscalar [3,2,5] [1,4,-6] == -19 menorProductoEscalar [1..10^2] [1..10^2] == 171700 menorProductoEscalar [1..10^3] [1..10^3] == 167167000 menorProductoEscalar [1..10^4] [1..10^4] == 166716670000 menorProductoEscalar [1..10^5] [1..10^5] == 166671666700000 menorProductoEscalar [1..10^6] [1..10^6] == 166667166667000000
Puntos en regiones rectangulares
Los puntos se puede representar mediante pares de números
type Punto = (Int,Int)
y las regiones rectangulares mediante el siguiente tipo de dato
data Region = Rectangulo Punto Punto | Union Region Region | Diferencia Region Region deriving (Eq, Show)
donde
-
(Rectangulo p1 p2)es la región formada por un rectángulo cuyo vértice superior izquierdo esp1y su vértice inferior derecho esp2. -
(Union r1 r2)es la región cuyos puntos pertenecen a alguna de las regionesr1yr2. -
(Diferencia r1 r2)es la región cuyos puntos pertenecen a la regiónr1pero no pertenecen a lar2.
Definir la función
enRegion :: Punto -> Region -> Bool
tal que (enRegion p r) se verifica si el punto p pertenece a la región r. Por ejemplo, usando las regiones definidas por
r0021, r3051, r4162 :: Region r0021 = Rectangulo (0,0) (2,1) r3051 = Rectangulo (3,0) (5,1) r4162 = Rectangulo (4,1) (6,2)
se tiene
enRegion (1,0) r0021 == True enRegion (3,0) r0021 == False enRegion (1,1) (Union r0021 r3051) == True enRegion (4,0) (Union r0021 r3051) == True enRegion (4,2) (Union r0021 r3051) == False enRegion (3,1) (Diferencia r3051 r4162) == True enRegion (4,1) (Diferencia r3051 r4162) == False enRegion (4,2) (Diferencia r3051 r4162) == False enRegion (4,2) (Union (Diferencia r3051 r4162) r4162) == True
Comprobar con QuickCheck que si el punto p está en la región r1, entonces, para cualquier región r2, p está en (Union r1 r2) y en (Union r2 r1), pero no está en (Diferencia r2 r1).
Clausura de un conjunto respecto de una función
Un conjunto A está cerrado respecto de una función f si para elemento x de A se tiene que f(x) pertenece a A. La clausura de un conjunto B respecto de una función f es el menor conjunto A que contiene a B y es cerrado respecto de f. Por ejemplo, la clausura de {0,1,2] respecto del opuesto es {-2,-1,0,1,2}.
Definir la función
clausura :: Ord a => (a -> a) -> [a] -> [a]
tal que (clausura f xs) es la clausura de xs respecto de f. Por ejemplo,
clausura (\x -> -x) [0,1,2] == [-2,-1,0,1,2] clausura (\x -> (x+1) `mod` 5) [0] == [0,1,2,3,4] length (clausura (\x -> (x+1) `mod` (10^6)) [0]) == 1000000
Números con todos sus dígitos primos
Definir la lista
numerosConDigitosPrimos :: [Integer]
cuyos elementos son los números con todos sus dígitos primos. Por ejemplo,
λ> take 22 numerosConDigitosPrimos [2,3,5,7,22,23,25,27,32,33,35,37,52,53,55,57,72,73,75,77,222,223] λ> numerosConDigitosPrimos4 !! (10^7) 322732232572
Producto cartesiano de una familia de conjuntos
Definir la función
producto :: [[a]] -> [[a]]
tal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,
λ> producto [[1,3],[2,5]] [[1,2],[1,5],[3,2],[3,5]] λ> producto [[1,3],[2,5],[6,4]] [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] λ> producto [[1,3,5],[2,4]] [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]] λ> producto [] [[]]
Comprobar con QuickCheck que para toda lista de listas de números enteros, xss, se verifica que el número de elementos de (producto xss) es igual al producto de los números de elementos de cada una de las listas de xss.
Representacion_de_Zeckendorf
Los primeros números de Fibonacci son
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...
tales que los dos primeros son iguales a 1 y los siguientes se obtienen sumando los dos anteriores.
El teorema de Zeckendorf establece que todo entero positivo n se puede representar, de manera única, como la suma de números de Fibonacci no consecutivos decrecientes. Dicha suma se llama la representación de Zeckendorf de n. Por ejemplo, la representación de Zeckendorf de 100 es
100 = 89 + 8 + 3
Hay otras formas de representar 100 como sumas de números de Fibonacci; por ejemplo,
100 = 89 + 8 + 2 + 1 100 = 55 + 34 + 8 + 3
pero no son representaciones de Zeckendorf porque 1 y 2 son números de Fibonacci consecutivos, al igual que 34 y 55.
Definir la función
zeckendorf :: Integer -> [Integer]
tal que (zeckendorf n) es la representación de Zeckendorf de n. Por ejemplo,
zeckendorf 100 == [89,8,3] zeckendorf 200 == [144,55,1] zeckendorf 300 == [233,55,8,3,1] length (zeckendorf (10^50000)) == 66097
Ordenada cíclicamente
Se dice que una sucesión x(1), ..., x(n) está ordenada cíclicamente si existe un índice i tal que la sucesión
x(i), x(i+1), ..., x(n), x(1), ..., x(i-1)
está ordenada crecientemente de forma estricta.
Definir la función
ordenadaCiclicamente :: Ord a => [a] -> Maybe Int
tal que (ordenadaCiclicamente xs) es el índice a partir del cual está ordenada, si la lista está ordenado cíclicamente y Nothing en caso contrario. Por ejemplo,
ordenadaCiclicamente [1,2,3,4] == Just 0 ordenadaCiclicamente [5,8,1,3] == Just 2 ordenadaCiclicamente [4,6,7,5,1,3] == Nothing ordenadaCiclicamente [1,0,3,2] == Nothing ordenadaCiclicamente [1,2,0] == Just 2 ordenadaCiclicamente "cdeab" == Just 3
Nota: Se supone que el argumento es una lista no vacía sin elementos repetidos.
Eliminación de las ocurrencias aisladas
Definir la función
eliminaAisladas :: Eq a => a -> [a] -> [a]
tal que (eliminaAisladas x ys) es la lista obtenida eliminando ys las ocurrencias aisladas de x (es decir, aquellas ocurrencias de x tales que su elemento anterior y posterior son distintos de x). Por ejemplo,
eliminaAisladas 'X' "" == "" eliminaAisladas 'X' "X" == "" eliminaAisladas 'X' "XX" == "XX" eliminaAisladas 'X' "XXX" == "XXX" eliminaAisladas 'X' "abcd" == "abcd" eliminaAisladas 'X' "Xabcd" == "abcd" eliminaAisladas 'X' "XXabcd" == "XXabcd" eliminaAisladas 'X' "XXXabcd" == "XXXabcd" eliminaAisladas 'X' "abcdX" == "abcd" eliminaAisladas 'X' "abcdXX" == "abcdXX" eliminaAisladas 'X' "abcdXXX" == "abcdXXX" eliminaAisladas 'X' "abXcd" == "abcd" eliminaAisladas 'X' "abXXcd" == "abXXcd" eliminaAisladas 'X' "abXXXcd" == "abXXXcd" eliminaAisladas 'X' "XabXcdX" == "abcd" eliminaAisladas 'X' "XXabXXcdXX" == "XXabXXcdXX" eliminaAisladas 'X' "XXXabXXXcdXXX" == "XXXabXXXcdXXX" eliminaAisladas 'X' "XabXXcdXeXXXfXx" == "abXXcdeXXXfx"
Emparejamiento de árboles
Los árboles se pueden representar mediante el siguiente tipo de datos
data Arbol a = N a [Arbol a] deriving (Show, Eq)
Por ejemplo, los árboles
1 3
/ \ /|\
6 3 / | \
| 5 4 7
5 | /\
6 2 1
se representan por
ej1, ej2 :: Arbol Int ej1 = N 1 [N 6 [],N 3 [N 5 []]] ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]
Definir la función
emparejaArboles :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c
tal que (emparejaArboles f a1 a2) es el árbol obtenido aplicando la función f a los elementos de los árboles a1 y a2 que se encuentran en la misma posición. Por ejemplo,
λ> emparejaArboles (+) (N 1 [N 2 [], N 3[]]) (N 1 [N 6 []]) N 2 [N 8 []] λ> emparejaArboles (+) ej1 ej2 N 4 [N 11 [],N 7 []] λ> emparejaArboles (+) ej1 ej1 N 2 [N 12 [],N 6 [N 10 []]]
Separación por posición
Definir la función
particion :: [a] -> ([a],[a])
tal que (particion xs) es el par cuya primera componente son los elementos de xs en posiciones pares y su segunda componente son los restantes elementos. Por ejemplo,
particion [3,5,6,2] == ([3,6],[5,2]) particion [3,5,6,2,7] == ([3,6,7],[5,2]) particion "particion" == ("priin","atco")
Número de inversiones
Se dice que en una sucesión de números x(1), x(2), ..., x(n) hay una inversión cuando existe un par de números x(i) > x(j), siendo i < j. Por ejemplo, en la permutación 2, 1, 4, 3 hay dos inversiones (2 antes que 1 y 4 antes que 3) y en la permutación 4, 3, 1, 2 hay cinco inversiones (4 antes 3, 4 antes 1, 4 antes 2, 3 antes 1, 3 antes 2).
Definir la función
numeroInversiones :: Ord a => [a] -> Int
tal que (numeroInversiones xs) es el número de inversiones de xs. Por ejemplo,
numeroInversiones [2,1,4,3] == 2 numeroInversiones [4,3,1,2] == 5
Descomposiciones triangulares
Los números triangulares se forman como sigue
* * * * * * * * * * 1 3 6
La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5
Definir la función
descomposicionesTriangulares :: Int -> [(Int, Int, Int)]
tal que (descomposicionesTriangulares n) es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos formados por números triangulares. Por ejemplo,
descomposicionesTriangulares 4 == [] descomposicionesTriangulares 5 == [(1,1,3)] descomposicionesTriangulares 12 == [(1,1,10),(3,3,6)] descomposicionesTriangulares 30 == [(1,1,28),(3,6,21),(10,10,10)] descomposicionesTriangulares 61 == [(1,15,45),(3,3,55),(6,10,45),(10,15,36)] descomposicionesTriangulares 52 == [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)] descomposicionesTriangulares 82 == [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)]
Índices de valores verdaderos
Definir la función
indicesVerdaderos :: [Int] -> [Bool]
tal que (indicesVerdaderos xs) es la lista infinita de booleanos tal que sólo son verdaderos los elementos cuyos índices pertenecen a la lista estrictamente creciente xs. Por ejemplo,
λ> take 6 (indicesVerdaderos [1,4]) [False,True,False,False,True,False] λ> take 6 (indicesVerdaderos [0,2..]) [True,False,True,False,True,False] λ> take 3 (indicesVerdaderos []) [False,False,False] λ> take 6 (indicesVerdaderos [1..]) [False,True,True,True,True,True] λ> last (take (8*10^7) (indicesVerdaderos [0,5..])) False
Código de las alergias
Para la determinación de las alergia se utiliza los siguientes códigos para los alérgenos:
Huevos ........ 1 Cacahuetes .... 2 Mariscos ...... 4 Fresas ........ 8 Tomates ....... 16 Chocolate ..... 32 Polen ......... 64 Gatos ......... 128
Así, si Juan es alérgico a los cacahuetes y al chocolate, su puntuación es 34 (es decir, 2+32).
Los alérgenos se representan mediante el siguiente tipo de dato
data Alergeno = Huevos | Cacahuetes | Mariscos | Fresas | Tomates | Chocolate | Polen | Gatos deriving (Enum, Eq, Show, Bounded)
Definir la función
alergias :: Int -> [Alergeno]
tal que (alergias n) es la lista de alergias correspondiente a una puntuación n. Por ejemplo,
λ> alergias 1 [Huevos] λ> alergias 2 [Cacahuetes] λ> alergias 3 [Huevos,Cacahuetes] λ> alergias 5 [Huevos,Mariscos] λ> alergias 255 [Huevos,Cacahuetes,Mariscos,Fresas,Tomates,Chocolate,Polen,Gatos]
Reiteración de una función
Definir la función
reiteracion :: (a -> a) -> Int -> a -> a
tal que (reiteracion f n x) es el resultado de aplicar n veces la función f a x. Por ejemplo,
reiteracion (+1) 10 5 == 15 reiteracion (+5) 10 0 == 50 reiteracion (*2) 4 1 == 16 reiteracion (5:) 4 [] == [5,5,5,5]
Elementos de una matriz con algún vecino menor
Las matrices pueden representarse mediante tablas cuyos índices son pares de números naturales. Su tipo se define por
type Matriz = Array (Int,Int) Int
Por ejemplo, la matriz
|9 4 6 5| |8 1 7 3| |4 2 5 4|
se define por
ej :: Matriz ej = listArray ((1,1),(3,4)) [9,4,6,5,8,1,7,3,4,2,5,4]
Los vecinos de un elemento son los que están a un paso en la misma fila, columna o diagonal. Por ejemplo, en la matriz anterior, el 1 tiene 8 vecinos (el 9, 4, 6, 8, 7, 4, 2 y 5) pero el 9 sólo tiene 3 vecinos (el 4, 8 y 1).
Definir la función
algunoMenor :: Matriz -> [Int]
tal que (algunoMenor p) es la lista de los elementos de p que tienen algún vecino menor que él. Por ejemplo,
algunoMenor ej == [9,4,6,5,8,7,4,2,5,4]
pues sólo el 1 y el 3 no tienen ningún vecino menor en la matriz.
Enumeración de árboles binarios
Los árboles binarios se pueden representar mediante el tipo Arbol definido por
data Arbol a = H a | N (Arbol a) a (Arbol a) deriving Show
Por ejemplo, el árbol
"B"
/ \
/ \
/ \
"B" "A"
/ \ / \
"A" "B" "C" "C"
se puede definir por
ej1 :: Arbol String ej1 = N (N (H "A") "B" (H "B")) "B" (N (H "C") "A" (H "C"))
Definir la función
enumeraArbol :: Arbol t -> Arbol Int
tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,
λ> enumeraArbol ej1 N (N (H 0) 1 (H 2)) 3 (N (H 4) 5 (H 6))
Gráficamente,
3
/ \
/ \
/ \
1 5
/ \ / \
0 2 4 6
Números triangulares con n cifras distintas
Los números triangulares se forman como sigue
* * * * * * * * * * 1 3 6
La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5
Definir la función
triangularesConCifras :: Int -> [Integer]
tal que (triangulares n) es la lista de los números triangulares con n cifras distintas. Por ejemplo,
take 6 (triangularesConCifras 1) == [1,3,6,55,66,666] take 6 (triangularesConCifras 2) == [10,15,21,28,36,45] take 6 (triangularesConCifras 3) == [105,120,136,153,190,210] take 5 (triangularesConCifras 4) == [1035,1275,1326,1378,1485] take 2 (triangularesConCifras 10) == [1062489753,1239845706]
Trenzado de listas
Definir la función
trenza :: [a] -> [a] -> [a]
tal que (trenza xs ys) es la lista obtenida intercalando los elementos de xs e ys. Por ejemplo,
trenza [5,1] [2,7,4] == [5,2,1,7] trenza [5,1,7] [2..] == [5,2,1,3,7,4] trenza [2..] [5,1,7] == [2,5,3,1,4,7] take 8 (trenza [2,4..] [1,5..]) == [2,1,4,5,6,9,8,13]
Biparticiones de una lista
Definir la función
biparticiones :: [a] -> [([a],[a])]
tal que (biparticiones xs) es la lista de pares formados por un prefijo de xs y el resto de xs. Por ejemplo,
λ> biparticiones [3,2,5] [([],[3,2,5]),([3],[2,5]),([3,2],[5]),([3,2,5],[])] λ> biparticiones "Roma" [("","Roma"),("R","oma"),("Ro","ma"),("Rom","a"),("Roma","")]
Lista cuadrada
Definir la función
listaCuadrada :: Int -> a -> [a] -> [[a]]
tal que (listaCuadrada n x xs) es una lista de n listas de longitud n formadas con los elementos de xs completada con x, si no xs no tiene suficientes elementos. Por ejemplo,
listaCuadrada 3 7 [0,3,5,2,4] == [[0,3,5],[2,4,7],[7,7,7]] listaCuadrada 3 7 [0..] == [[0,1,2],[3,4,5],[6,7,8]] listaCuadrada 2 'p' "eva" == ["ev","ap"] listaCuadrada 2 'p' ['a'..] == ["ab","cd"]
Máximos locales
Un máximo local de una lista es un elemento de la lista que es que su predecesor y que su sucesor en la lista. Por ejemplo, 5 es un máximo local de [3,2,5,3,7,7,1,6,2] ya que es mayor que 2 (su predecesor) y que 3 (su sucesor).
Definir la función
maximosLocales :: Ord a => [a] -> [a]
tal que (maximosLocales xs) es la lista de los máximos locales de la lista xs. Por ejemplo,
maximosLocales [3,2,5,3,7,7,1,6,2] == [5,6] maximosLocales [1..100] == [] maximosLocales "adbpmqexyz" == "dpq"
Matrices de Toepliz
Una matriz de Toeplitz es una matriz cuadrada que es constante a lo largo de las diagonales paralelas a la diagonal principal. Por ejemplo,
|2 5 1 6| |2 5 1 6| |4 2 5 1| |4 2 6 1| |7 4 2 5| |7 4 2 5| |9 7 4 2| |9 7 4 2|
la primera es una matriz de Toeplitz y la segunda no lo es.
Las anteriores matrices se pueden definir por
ej1, ej2 :: Array (Int,Int) Int ej1 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,5,1,7,4,2,5,9,7,4,2] ej2 = listArray ((1,1),(4,4)) [2,5,1,6,4,2,6,1,7,4,2,5,9,7,4,2]
Definir la función
esToeplitz :: Eq a => Array (Int,Int) a -> Bool
tal que (esToeplitz p) se verifica si la matriz p es de Toeplitz. Por ejemplo,
esToeplitz ej1 == True esToeplitz ej2 == False
Diagonales principales
La lista de las diagonales principales de la matriz
1 2 3 4 5 6 7 8 9 10 11 12
es
[[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
Definir la función
diagonalesPrincipales :: Array (Int,Int) a -> [[a]]
tal que (diagonalesPrincipales p) es la lista de las diagonales principales de p. Por ejemplo,
λ> diagonalesPrincipales (listArray ((1,1),(3,4)) [1..12]) [[9],[5,10],[1,6,11],[2,7,12],[3,8],[4]]
Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.
Posiciones de las diagonales principales
Las posiciones de una matriz con 3 filas y 4 columnas son
(1,1) (1,2) (1,3) (1,4) (2,1) (2,2) (2,3) (2,4) (3,1) (3,2) (3,3) (3,4)
Las posiciones de sus 6 diagonales principales son
[(3,1)] [(2,1),(3,2)] [(1,1),(2,2),(3,3)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)]
Definir la función
posicionesDiagonalesPrincipales :: Int -> Int -> [[(Int, Int)]]
tal que (posicionesdiagonalesprincipales m n) es la lista de las posiciones de las diagonales principales de una matriz con m filas y n columnas. Por ejemplo,
λ> mapM_ print (posicionesDiagonalesPrincipales 3 4) [(3,1)] [(2,1),(3,2)] [(1,1),(2,2),(3,3)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)] λ> mapM_ print (posicionesDiagonalesPrincipales 4 4) [(4,1)] [(3,1),(4,2)] [(2,1),(3,2),(4,3)] [(1,1),(2,2),(3,3),(4,4)] [(1,2),(2,3),(3,4)] [(1,3),(2,4)] [(1,4)] λ> mapM_ print (posicionesDiagonalesPrincipales 4 3) [(4,1)] [(3,1),(4,2)] [(2,1),(3,2),(4,3)] [(1,1),(2,2),(3,3)] [(1,2),(2,3)] [(1,3)]
Primos equidistantes
Definir la función
primosEquidistantes :: Integer -> [(Integer,Integer)]
tal que (primosEquidistantes k) es la lista de los pares de primos cuya diferencia es k. Por ejemplo,
take 3 (primosEquidistantes 2) == [(3,5),(5,7),(11,13)] take 3 (primosEquidistantes 4) == [(7,11),(13,17),(19,23)] take 3 (primosEquidistantes 6) == [(23,29),(31,37),(47,53)] take 3 (primosEquidistantes 8) == [(89,97),(359,367),(389,397)] primosEquidistantes 4 !! (10^5) == (18467047,18467051)
Anagramas
Una palabra es una anagrama de otra si se puede obtener permutando sus letras. Por ejemplo, "mora" y "roma" son anagramas de "amor".
Definir la función
anagramas :: String -> [String] -> [String]
tal que (anagramas x ys) es la lista de los elementos de ys que son anagramas de x. Por ejemplo,
λ> anagramas "amor" ["Roma","mola","loma","moRa", "rama"] ["Roma","moRa"] λ> anagramas "rama" ["aMar","amaRa","roMa","marr","aRma"] ["aMar","aRma"]
Nota: Escribir las soluciones en Haskell, en Python y en Common Lisp.
La bandera tricolor
El problema de la bandera tricolor consiste en lo siguiente: Dada un lista de objetos xs que pueden ser rojos, amarillos o morados, se pide devolver una lista que contiene los elementos de xs, primero los rojos, luego los amarillos y por último los morados.
Definir el tipo de dato Color para representar los colores con los constructores R, A y M correspondientes al rojo, azul y morado y la función
banderaTricolor :: [Color] -> [Color]
tal que (banderaTricolor xs) es la bandera tricolor formada con los elementos de xs. Por ejemplo,
banderaTricolor [M,R,A,A,R,R,A,M,M] == [R,R,R,A,A,A,M,M,M] banderaTricolor [M,R,A,R,R,A] == [R,R,R,A,A,M]
Ordenación por el máximo
Definir la función
ordenadosPorMaximo :: Ord a => [[a]] -> [[a]]
tal que (ordenadosPorMaximo xss) es la lista de los elementos de xss ordenada por sus máximos (se supone que los elementos de xss son listas no vacía) y cuando tiene el mismo máximo se conserva el orden original. Por ejemplo,
λ> ordenadosPorMaximo [[0,8],[9],[8,1],[6,3],[8,2],[6,1],[6,2]] [[6,3],[6,1],[6,2],[0,8],[8,1],[8,2],[9]] λ> ordenadosPorMaximo ["este","es","el","primero"] ["el","primero","es","este"]
Iguales al siguiente
Definir la función
igualesAlSiguiente :: Eq a => [a] -> [a]
tal que (igualesAlSiguiente xs) es la lista de los elementos de xs que son iguales a su siguiente. Por ejemplo,
igualesAlSiguiente [1,2,2,2,3,3,4] == [2,2,3] igualesAlSiguiente [1..10] == []
Nota: Escribir las soluciones en Haskell y en Python.
Primos consecutivos con media capicúa
Definir la list
primosConsecutivosConMediaCapicua :: [(Int,Int,Int)]
formada por las ternas (x,y,z) tales que x e y son primos consecutivos cuya media, z, es capicúa. Por ejemplo,
λ> take 5 primosConsecutivosConMediaCapicua [(3,5,4),(5,7,6),(7,11,9),(97,101,99),(109,113,111)] λ> primosConsecutivosConMediaCapicua !! 500 (5687863,5687867,5687865)
Nota: Escribir las soluciones en Haskell y en Python.
Mastermind
El Mastermind es un juego que consiste en deducir un código numérico formado por una lista de números. Cada vez que se una partida, el programa debe elegir un código, que será lo que el jugador debe adivinar en la menor cantidad de intentos posibles. Cada intento consiste en una propuesta de un código posible que propone el jugador, y una respuesta del programa. Las respuestas le darán pistas al jugadorpara que pueda deducir el código.
Estas pistas indican lo cerca que estuvo el número propuesto de la solución a través de dos valores: la cantidad de aciertos es la cantidad de dígitos que propuso el jugador que también están en el código en la misma posición. La cantidad de coincidencias es la cantidad de dígitos que propuso el jugador que también están en el código pero en una posición distinta.
Por ejemplo, si el código que eligió el programa es el [2,6,0,7] y el jugador propone el [1,4,0,6], el programa le debe responder un acierto (el 0, que está en el código original en el mismo lugar, el tercero), y una coincidencia (el 6, que también está en el código original, pero en la segunda posición, no en el cuarto como fue propuesto). Si el jugador hubiera propuesto el [3,5,9,1], habría obtenido como respuesta ningún acierto y ninguna coincidencia, ya que no hay números en común con el código original. Si se obtienen cuatro aciertos es porque el jugador adivinó el código y ganó el juego.
Definir la función
mastermind :: [Int] -> [Int] -> (Int, Int)
tal que (mastermind xs ys) es el par formado por los números de aciertos y de coincidencias entre xs e ys. Por ejemplo,
mastermind [3,3] [3,2] == (1,0) mastermind [3,5,3] [3,2,5] == (1,1) mastermind [3,5,3,2] [3,2,5,3] == (1,3) mastermind [3,5,3,3] [3,2,5,3] == (2,1) mastermind [1..10^6] [1..10^6] == (1000000,0)
Nota: Escribir las soluciones en Haskell y en Python.
Determinación de los elementos minimales
Definir la función
minimales :: Ord a => [[a]] -> [[a]]
tal que (minimales xss) es la lista de los elementos de xss que no están contenidos en otros elementos de xss. Por ejemplo,
minimales [[1,3],[2,3,1],[3,2,5]] == [[2,3,1],[3,2,5]] minimales [[1,3],[2,3,1],[3,2,5],[3,1]] == [[2,3,1],[3,2,5]] map sum (minimales [[1..n] | n <- [1..300]]) == [45150]
Nota: Escribir las soluciones en Haskell y en Python.
Suma de los números amigos menores que n
Dos números amigos son dos números enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.
Definir la función
sumaAmigosMenores :: Integer -> Integer
tal que (sumaAmigosMenores n) es la suma de los números amigos menores que n. Por ejemplo,
sumaAmigosMenores 2000 == 2898 sumaAmigosMenores (10^5) == 852810
Sucesión de números amigos
Dos números amigos son dos números enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.
Definir la lista
sucesionAmigos :: [(Integer,Integer)]
cuyos elementos son los pares de números amigos con la primera componente menor que la segunda. Por ejemplo,
take 4 sucesionAmigos == [(220,284),(1184,1210),(2620,2924),(5020,5564)] sucesionAmigos6 !! 20 == (185368,203432)
Números amigos
Dos números amigos son dos números enteros positivos distintos tales que la suma de los divisores propios de cada uno es igual al otro. Los divisores propios de un número incluyen la unidad pero no al propio número. Por ejemplo, los divisores propios de 220 son 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 y 110. La suma de estos números equivale a 284. A su vez, los divisores propios de 284 son 1, 2, 4, 71 y 142. Su suma equivale a 220. Por tanto, 220 y 284 son amigos.
Definir la función
amigos :: Integer -> Integer -> Bool
tal que (amigos x y) se verifica si los números x e y son amigos. Por ejemplo,
amigos 220 284 == True amigos 220 23 == False amigos 42262694537514864075544955198125 42405817271188606697466971841875 == True
Máxima suma de caminos en un triángulo
Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo
3 7 4 2 4 6 8 5 9 3
se representa por
[[3],[7,4],[2,4,6],[8,5,9,3]]
Definir la función
maximaSuma :: [[Integer]] -> Integer
tal que (maximaSuma xss) es el máximo de las sumas de los elementos de los caminos en el triángulo xss donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,
maximaSuma [[3],[7,4]] == 10 maximaSuma [[3],[7,4],[2,4,6]] == 14 maximaSuma [[3],[7,4],[2,4,6],[8,5,9,3]] == 23 maximaSuma [[n..n+n] | n <- [0..100]] == 10100 maximaSuma [[n..n+n] | n <- [0..1000]] == 1001000 maximaSuma [[n..n+n] | n <- [0..2000]] == 4002000 maximaSuma [[n..n+n] | n <- [0..3000]] == 9003000 maximaSuma [[n..n+n] | n <- [0..4000]] == 16004000
Caminos en un triángulo
Los triángulos se pueden representar mediante listas de listas. Por ejemplo, el triángulo
3
7 4
2 4 6
8 5 9 3
se representa por
[[3],[7,4],[2,4,6],[8,5,9,3]]
Definir la función
caminos :: [[a]] -> [[a]]
tal que (caminos xss) es la lista de los caminos en el triángulo xss donde los caminos comienzan en el elemento de la primera fila, en cada paso se mueve a uno de sus dos elementos adyacentes en la fila siguiente y terminan en la última fila. Por ejemplo,
λ> caminos [[3],[7,4]] [[3,7],[3,4]] λ> caminos [[3],[7,4],[2,4,6]] [[3,7,2],[3,7,4],[3,4,4],[3,4,6]] λ> caminos [[3],[7,4],[2,4,6],[8,5,9,3]] [[3,7,2,8],[3,7,2,5],[3,7,4,5],[3,7,4,9],[3,4,4,5],[3,4,4,9],[3,4,6,9],[3,4,6,3]]
Mayor órbita de la sucesión de Collatz
Se considera la siguiente operación, aplicable a cualquier número entero positivo:
- Si el número es par, se divide entre 2.
- Si el número es impar, se multiplica por 3 y se suma 1.
Dado un número cualquiera, podemos calcular su órbita; es decir, las imágenes sucesivas al iterar la función. Por ejemplo, la órbita de 13 es
13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
Si observamos este ejemplo, la órbita de 13 es periódica, es decir, se repite indefinidamente a partir de un momento dado). La conjetura de Collatz dice que siempre alcanzaremos el 1 para cualquier número con el que comencemos. Ejemplos:
- Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.
- Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
- Empezando en n = 27, la sucesión tiene 112 pasos, llegando hasta 9232 antes de descender a 1: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.
Definir la función
mayoresGeneradores :: Integer -> [Integer]
tal que (mayoresGeneradores n) es la lista de los números menores o iguales que n cuyas órbitas de Collatz son las de mayor longitud. Por ejemplo,
mayoresGeneradores 20 == [18,19] mayoresGeneradores (10^6) == [837799]