Definir la función
comienzanCon :: [Int] -> Int -> [Int]
tal que (comienzanCon xs d) es la lista de los elementos de xs que empiezan por el dígito d. Por ejemplo,
comienzanCon [123,51,11,711,52] 1 == [123,11] comienzanCon [123,51,11,711,52] 5 == [51,52] comienzanCon [123,51,11,711,52] 6 == []
Las posiciones frontera de una matriz de orden mxn son aquellas que están en la fila 1 o la fila m o la columna 1 o la columna n. El resto se dirán posiciones interiores. Observa que cada elemento en una posición interior tiene exactamente 8 vecinos en la matriz.
Dada una matriz, un paso de transición genera una nueva matriz de la misma dimensión pero en la que se ha sustituido cada elemento interior por la suma de sus 8 vecinos. Los elementos frontera no varían.
Definir las funciones
marco :: Int -> Int -> Integer -> Matrix Integer paso :: Matrix Integer -> Matrix Integer itPasos :: Int -> Matrix Integer -> Matrix Integer pasosHasta :: Integer -> Int
tales que
λ> marco 5 5 1 ( 1 1 1 1 1 ) ( 1 0 0 0 1 ) ( 1 0 0 0 1 ) ( 1 0 0 0 1 ) ( 1 1 1 1 1 )
λ> paso (marco 5 5 1) ( 1 1 1 1 1 ) ( 1 5 3 5 1 ) ( 1 3 0 3 1 ) ( 1 5 3 5 1 ) ( 1 1 1 1 1 )
λ> itPasos 10 (marco 5 5 1) ( 1 1 1 1 1 ) ( 1 4156075 5878783 4156075 1 ) ( 1 5878783 8315560 5878783 1 ) ( 1 4156075 5878783 4156075 1 ) ( 1 1 1 1 1 )
pasosHasta 4 == 1 pasosHasta 6 == 2 pasosHasta (2^2015) == 887
La parte par de un polinomio de coeficientes enteros es el polinomio formado por sus monomios cuyos coeficientes son números pares. Por ejemplo, la parte par de 4x^3+x^2-7x+6 es 4x^3+6.
Definir la función
partePar :: Integral a => Polinomio a -> Polinomio a
tal que (partePar p) es la parte par de p. Por ejemplo,
λ> partePar (consPol 3 4 (consPol 2 1 (consPol 0 6 polCero))) 4*x^3 + 6
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.
Representamos los árboles binarios con elementos en las hojas y en los nodos mediante el tipo de dato
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show
Definir la función
aplica :: (a -> a) -> (a -> a) -> Arbol a -> Arbol a
tal que (aplica f g a) devuelve el árbol obtenido al aplicar la función f a las hojas del árbol a y la función g a los nodos interiores. Por ejemplo,
λ> aplica (+1)(*2) (N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2))) N 10 (N 4 (H 2) (H 3)) (N 6 (H 5) (H 3))
Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),...,v(n)] de nodos de G tal que:
Definir la función
ciclos :: Grafo Int Int -> [[Int]]
tal que (ciclos g) es la lista de ciclos de g. Por ejemplo, si g1 y g2 son los grafos definidos por
g1, g2 :: Grafo Int Int g1 = creaGrafo D (1,4) [(1,2,0),(2,3,0),(2,4,0),(4,1,0)] g2 = creaGrafo D (1,4) [(1,2,0),(2,1,0),(2,4,0),(4,1,0)]
entonces
ciclos g1 == [[1,2,4,1],[2,4,1,2],[4,1,2,4]] ciclos g2 == [[1,2,1],[1,2,4,1],[2,1,2],[2,4,1,2],[4,1,2,4]]
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.
Decimos que un número es alternado si no tiene dos cifras consecutivas iguales ni tres cifras consecutivas en orden creciente no estricto o decreciente no estricto. Por ejemplo, los números 132425 y 92745 son alternados, pero los números 12325 y 29778 no. Las tres primeras cifras de 12325 están en orden creciente y 29778 tiene dos cifras iguales consecutivas.
Definir la constante
alternados :: [Integer]
cuyo valor es la lista infinita de los números alternados. Por ejemplo,
take 10 alternados == [0,1,2,3,4,5,6,7,8,9] length (takeWhile (< 1000) alternados) == 616 alternados !! 1234567 == 19390804
La visibilidad de una lista es el número de elementos que son estrictamente mayores que todos los anteriores. Por ejemplo, la visibilidad de la lista [1,2,5,2,3,6] es 4.
La visibilidad de una matriz P es el par formado por las visibilidades de las filas de P y las visibilidades de las columnas de P. Por ejemplo, dada la matriz
( 4 2 1 )
Q = ( 3 2 5 )
( 6 1 8 )
la visibilidad de Q es ([1,2,2],[2,1,3]).
Definir las funciones
visibilidadLista :: [Int] -> Int visibilidadMatriz :: Matrix Int -> ([Int],[Int])
tales que
visibilidadLista [1,2,5,2,3,6] == 4 visibilidadLista [0,-2,5,1,6,6] == 3 + (visibilidadMatriz p) es la visibilidad de la matriz p. Por ejemplo, ~~~haskell λ> visibilidadMatriz (fromLists [[4,2,1],[3,2,5],[6,1,8]]) ([1,2,2],[2,1,3]) λ> visibilidadMatriz (fromLists [[0,2,1],[0,2,5],[6,1,8]]) ([2,3,2],[2,1,3])
Dado un grafo no dirigido G, un camino en G es una secuencia de nodos [v(1),v(2),v(3),...,v(n)] tal que para todo i entre 1 y n-1, (v(i),v(i+1)) es una arista de G. Por ejemplo, dados los grafos
g1, g2 :: Grafo Int Int g1 = creaGrafo ND (1,3) [(1,2,0),(1,3,0),(2,3,0)] g2 = creaGrafo ND (1,4) [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(3,4,0)]
la lista [1,2,3] es un camino en g1, pero no es un camino en g2 puesto que la arista (2,3) no existe en g2.
Definir la función
camino :: Grafo Int Int -> [Int] -> Bool
tal que (camino g vs) se verifica si la lista de nodos vs es un camino en el grafo g. Por ejemplo,
camino g1 [1,2,3] == True camino g2 [1,2,3] == False
Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.
El ejercicio de hoy tiene como objetivo comprobar la veracidad del Teorema de Midy:
Sea a/p una fracción, donde a < p y p > 5 es un número primo. Si esta fracción tiene una expansión decimal periódica, donde la cantidad de dígitos en el período es par, entonces podemos partir el período en dos mitades, cuya suma es un número formado únicamente por nueves.
Por ejemplo, 2/7 = 0'285714285714... El período es 285714, cuya longitud es par (6). Lo partimos por la mitad y las sumamos: 285+714 = 999.
Definir la función
teoremaMidy :: Integer -> Bool
tal que (teoremaMidy n) se verifica si para todo todo número primo p menor que n y mayor que 5 y todo número natural menor que p tales que la cantidad de dígitos en el período de a/p es par, entonces podemos partir el período de a/p en dos mitades, cuya suma es un número formado únicamente por nueves. Por ejemplo,
teoremaMidy 200 == True
Además, comprobar el teorema de Midy usando QuickCheck.
Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,
6/2 = 3 se representa por (3,[],[]) 1/2 = 0.5 se representa por (0,[5],[]) 1/3 = 0.333333... se representa por (0,[],[3]) 23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])
Su tipo es
type Decimal = (Integer,[Integer],[Integer])
Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es
type Racional = (Integer,Integer)
Definir las funciones
decimal :: Racional -> Decimal racional :: Decimal -> Racional
tales que
decimal (1,4) == (0,[2,5],[]) decimal (1,3) == (0,[],[3]) decimal (23,14) == (1,[6],[4,2,8,5,7,1])
racional (0,[2,5],[]) == (1,4) racional (0,[],[3]) == (1,3) racional (1,[6],[4,2,8,5,7,1]) == (23,14)
Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,
λ> let (_,_,p) = decimal (23,14) in concatMap show p "428571" λ> let (_,_,p) = decimal (1,47) in concatMap show p "0212765957446808510638297872340425531914893617" λ> let (_,_,p) = decimal (1,541) in length (concatMap show p) 540
Comprobar con QuickCheck si las funciones decimal y racional son inversas.