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:

• Para n impar:

| 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|

• Para n par:

| 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]

Leer más…

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

Leer más…

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

Leer más…

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,

• al 1º partido (que obtuvo 340000 votos) le corresponden 3 escaños,
• al 2º partido (que obtuvo 280000 votos) le corresponden 3 escaños,
• al 3º partido (que obtuvo 160000 votos) le corresponden 1 escaño.

Leer más…

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

Leer más…

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 == []

Leer más…

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 m n z) genera la matriz de dimensión mxn que contiene el entero z en las posiciones frontera y 0 en las posiciones interiores. Por ejemplo,

λ> 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 t) calcula la matriz generada tras aplicar un paso de transición a la matriz t. Por ejemplo,

λ> 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 k t) es la matriz obtenida tras aplicar k pasos de transición a partir de la matriz t. Por ejemplo,

λ> 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 k) es el número de pasos de transición a partir de la matriz (marco 5 5 1) necesarios para que en la matriz resultante aparezca un elemento mayor que k. Por ejemplo,

pasosHasta 4         ==  1
pasosHasta 6         ==  2
pasosHasta (2^2015)  ==  887

Leer más…

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í.

Leer más…

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))

Leer más…

Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),...,v(n)] de nodos de G tal que:

• (v(1),v(2)), (v(2),v(3)), (v(3),v(4)), ..., (v(n-1),v(n)) son aristas de G,
• v(1) = v(n), y
• salvo v(1) = v(n), todos los v(i) son distintos entre sí.

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í.

Leer más…

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

Leer más…

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 xs) es la visibilidad de la lista xs. Por ejemplo,

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])

Leer más…

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í.

Leer más…

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.

Leer más…

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 r) es la representación decimal del número racional r. Por ejemplo,

decimal (1,4)    ==  (0,[2,5],[])
decimal (1,3)    ==  (0,[],[3])
decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])

• (racional d) es el número racional cuya representación decimal es d. Por ejemplo,

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.

Leer más…

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

Leer más…

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  ==  []

Leer más…

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í.

Leer más…

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

Leer más…

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.

Leer más…

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 xs) es la codificación de Gödel de xs. Por ejemplo,

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 n) es la lista xs cuya codificación es n. Por ejemplo,

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.

Leer más…

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]

Leer más…

Definir las funciones

agrupa  :: Eq a => [a] -> [(a,Int)]
expande :: [(a,Int)] -> [a]

tales que

• (agrupa xs) es la lista obtenida agrupando las ocurrencias consecutivas de elementos de xs junto con el número de dichas ocurrencias. Por ejemplo:

agrupa "aaabzzaa" == [('a',3),('b',1),('z',2),('a',2)]

• (expande xs) es la lista expandida correspondiente a ps (es decir, es la lista xs tal que la comprimida de xs es ps. Por ejemplo,

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.

Leer más…

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

Leer más…

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

Leer más…

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

Leer más…

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

Leer más…

Una fracción x/y es cancelativa si se cumplen las siguientes condiciones:

• x/y es propia (es decir, x < y),
• ninguno de los números x e y son múltiplos de 10 y
• existe un dígito d tal que al borrar una ocurrencia de d en x y otra en y se obtiene una fracción cuyo valor coincide con x/y.

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

Leer más…

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]

Leer más…

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)]

Leer más…

Definir la funciones

sumas  :: Int -> [[Int]]
nSumas :: Int -> Integer

tales que

• (sumas n) es la lista de las descomposiciones de n como 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 de n como sumas cuyos sumandos son 1 ó 2. Por ejemplo,

nSumas 4                      ==  5
nSumas 123                    ==  36726740705505779255899443
length (show (nSumas 123456)) ==  25801

Leer más…

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]

Leer más…

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

Leer más…

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

Leer más…

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

Leer más…

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 (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.

Leer más…

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]

Leer más…

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

Leer más…

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])

Leer más…

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.

Leer más…

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í.

Leer más…

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)]

Leer más…

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]]

Leer más…

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?

Leer más…

Definir las funciones

agrupa  :: Eq a => [a] -> [(a,Int)]
expande :: [(a,Int)] -> [a]

tales que

• (agrupa xs) es la lista obtenida agrupando las ocurrencias consecutivas de elementos de xs junto con el número de dichas ocurrencias. Por ejemplo:

agrupa "aaabzzaa" == [('a',3),('b',1),('z',2),('a',2)]

• (expande xs) es la lista expandida correspondiente a ps (es decir, es la lista xs tal que la comprimida de xs es ps. Por ejemplo,

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.

Leer más…

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

Leer más…

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

Leer más…

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

Leer más…

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]

Leer más…

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

Leer más…

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)]

Leer más…

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

Leer más…

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,

• El cociente entero de 4x⁴ + 6x³ + 7x² + 5x + 2 por el monomio 3x² se obtiene a partir de los términos 4x⁴ + 6x³ + 7x² realizando la división entera entre sus coeficientes y el número 3 y restando 2 a sus grados. De esta forma se obtiene x² + 2x + 2
• El cociente entero de 6x⁵ + 2x⁴ + 8x³ + 5x² + 8x + 4 por el monomio 4x³ se obtiene a partir de los términos 6x⁵ + 2x⁴ + 8x³ realizando la división entera entre sus coeficientes y el número 4 y restando 3 a sus grados. De esta forma se obtiene x² + 2

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í.

Leer más…

Se dice que dos números naturales son parientes sitienen exactamente un factor primo en común, independientemente de su multiplicidad. Por ejemplo,

• Los números 12 (2²·3) y 40 (2³·5) son parientes, pues tienen al 2 como único factor primo en común.
• Los números 49 (7²) y 63 (3²·7) son parientes, pues tienen al 7 como único factor primo en común.
• Los números 12 (2²·3) y 30 (2·3·5) no son parientes, pues tienen dos factores primos en común.
• Los números 49 (7²) y 25 (5²) no son parientes, pues no tienen factores primos en común.

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,

• La lista [12,40,35,28] es una secuencia de parientes.
• La lista [12,30,21,49] no es una secuencia de parientes.

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

Leer más…

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)]