-- I1M: Relación 30
-- Repaso del curso
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================
-- ============================================================================
-- Librerías
-- ============================================================================
import Data.List
import Test.QuickCheck
import qualified Data.Array as A
import qualified Data.Matrix as M
import PolinomioConListaDispersa
import GrafoConMatrizDeAdyacencia
-- ----------------------------------------------------------------------------
--
-- Ejercicio 1.1. Un número de n dígitos es un número de Armstrong si
-- es igual a la suma de las n-ésimas potencias de sus dígitos. Por ejemplo,
-- 371, 8208 y 4210818 son números de Armstrong ya que
-- 371 = 3^3 + 7^3 + 1^3
-- 8208 = 8^4 + 2^4 + 0^4 + 8^4
-- 4210818 = 4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7
--
-- Definir la función
-- esArmstrong :: Integer -> Bool
-- tal que '(esArmstrong m)' se verifica si el número natural 'm' es un número
-- de Armstrong. Por ejemplo,
-- esArmstrong 371 == True
-- esArmstrong 8208 == True
-- esArmstrong 4210818 == True
-- esArmstrong 2022 == False
-- esArmstrong 115132219018763992565095597973971522401 == True
-- esArmstrong 115132219018763992565095597973971522402 == False
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
esArmstrong :: Integer -> Bool
esArmstrong m = sum [(read [x] :: Integer)^n | x <- show m] == m
where n = length (show m)
-- ----------------------------------------------------------------------------
--
-- Ejercicio 1.2. Definir la función
-- armstrong :: [Integer]
-- tal que 'armstrong' es la lista formada por todos los números de Armstrong
-- en orden creciente. Por ejemplo,
-- take 18 armstrong ==
-- [1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727]
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
armstrong :: [Integer]
armstrong = [x | x <- [1..], esArmstrong x]
-- ----------------------------------------------------------------------------
--
-- Ejercicio 2.1. Se dice que el número A es un divisor propio maximal
-- del número B si A es un divisor de B distinto de B y no existe ningún número
-- C tal que A < C < B, con A divisor de C y C divisor de B. Por ejemplo, 15 es
-- un divisor propio maximal de 30, pero 5 no lo es.
--
-- El árbol de los divisores de un número N es el árbol que tiene como raíz el
-- número N y cada nodo tiene como hijos sus divisores propios maximales. Por
-- ejemplo, el árbol de divisores de 30 es
--
-- 30
-- /|\
-- / | \
-- / | \
-- / | \
-- / | \
-- 6 10 15
-- / \ / \ / \
-- 2 3 2 5 3 5
-- | | | | | |
-- 1 1 1 1 1 1
--
-- Usando el tipo de dato
-- data Arbol = N Integer [Arbol]
-- deriving (Eq, Show)
-- el árbol anterior se representa por
-- N 30
-- [N 6
-- [N 2 [N 1 []],
-- N 3 [N 1 []]],
-- N 10
-- [N 2 [N 1 []],
-- N 5 [N 1 []]],
-- N 15
-- [N 3 [N 1 []],
-- N 5 [N 1 []]]]
--
-- Definir la función
-- arbolDivisores :: Integer -> Arbol
-- tal que '(arbolDivisores n)' es el árbol de los divisores del número natural
-- 'n'. Por ejemplo,
-- arbolDivisores 30 ==
-- N 30 [N 6 [N 2 [N 1 []],N 3 [N 1 []]],
-- N 10 [N 2 [N 1 []],N 5 [N 1 []]],
-- N 15 [N 3 [N 1 []],N 5 [N 1 []]]]
-- ----------------------------------------------------------------------------
data Arbol = N Integer [Arbol]
deriving (Eq, Show)
-- Álvaro Galisteo:
arbolDivisores :: Integer -> Arbol
arbolDivisores n | n == 1 = N 1 []
| otherwise = N n (map arbolDivisores (divisoresMaximales n))
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..(div n 2)], mod n x == 0]
divisoresMaximales :: Integer -> [Integer]
divisoresMaximales n = filter (\ a -> not (any (\ b -> mod b a == 0) (tail(dropWhile (/= a) (divisores n)))) ) (divisores n)
-- ----------------------------------------------------------------------------
--
-- Ejercicio 2.2 Definir la función
-- nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
-- tal que '(nOcurrenciasArbolDivisores x n) es el número de veces que aparece
-- el número 'x' en el árbol de los divisores del número natural 'n'. Por
-- ejemplo,
-- nOcurrenciasArbolDivisores 3 30 == 2
-- nOcurrenciasArbolDivisores 6 30 == 1
-- nOcurrenciasArbolDivisores 30 30 == 1
-- nOcurrenciasArbolDivisores 1 30 == 6
-- nOcurrenciasArbolDivisores 9 30 == 0
-- nOcurrenciasArbolDivisores 2 (product [1..10]) == 360360
-- nOcurrenciasArbolDivisores 3 (product [1..10]) == 180180
-- nOcurrenciasArbolDivisores 5 (product [1..10]) == 90090
-- nOcurrenciasArbolDivisores 7 (product [1..10]) == 45045
-- nOcurrenciasArbolDivisores 6 (product [1..10]) == 102960
-- nOcurrenciasArbolDivisores 10 (product [1..10]) == 51480
-- nOcurrenciasArbolDivisores 14 (product [1..10]) == 25740
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
nOcurrenciasArbolDivisores x n = nOcurrenciasAux (arbolDivisores n) x
nOcurrenciasAux :: Arbol -> Integer -> Integer
nOcurrenciasAux (N n a) x | n == x = sum [nOcurrenciasAux z x | z <- a] + 1
| otherwise = sum [nOcurrenciasAux z x | z <- a]
-- ----------------------------------------------------------------------------
--
-- Ejercicio 3. El problema del número de emparejamientos de amigos
-- consiste en calcular el número de formas de emparejar n amigos teniendo en
-- cuenta que cada uno puede permanecer soltero o puede ser emparejado con
-- algún otro amigo y que cada amigo puede ser emparejado sólo una vez. Por
-- ejemplo, los 4 posibles emparejamientos de 3 amigos son
-- {1}, {2}, {3}
-- {1}, {2, 3}
-- {1, 2}, {3}
-- {1, 3}, {2}
--
-- Definir, usando programación dinámica, la función
-- nEmparejamientos :: Integer -> Integer
-- tal que '(nEmparejamientos n)' es el número de formas de emparejar a los 'n'
-- amigos. Por ejemplo,
-- nEmparejamientos 2 == 2
-- nEmparejamientos 3 == 4
-- nEmparejamientos 4 == 10
-- nEmparejamientos 10 == 9496
-- nEmparejamientos 30 == 606917269909048576
-- length (show (nEmparejamientos (10^4))) == 17872
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
nEmparejamientos :: Integer -> Integer
nEmparejamientos n = m A.! n
where m = A.array (1,n) [(i,f i) | i <- [1..n]]
f i | i == 1 = 1
| i == 2 = 2
| otherwise = m A.! (i-1) + (i - 1 ) * m A.! (i-2)
-- ----------------------------------------------------------------------------
--
-- Ejercicio 4. El grafo de divisibilidad de orden n es el grafo cuyos nodos
-- son los números naturales entre 1 y n, cuyas aristas son los pares (x,y)
-- tales que x divide a y o y divide a y el coste de cada arista es el cociente
-- entre su mayor y menor elemento.
--
-- Definir la siguiente función:
-- grafoDivisibilidad :: Int -> Grafo Int Int
-- tal que
-- (grafoDivisibilidad n) es el grafo de divisibilidad de orden n. Por ejemplo,
-- grafoDivisibilidad 12 ==
-- G[ND] N:{1,2,3,4,5,6,7,8,9,10,11,12}
-- A:{(1,2)[2],(1,3)[3],(1,4)[4],(1,5)[5],(1,6)[6],
-- (1,7)[7],(1,8)[8],(1,9)[9],(1,10)[10],(1,11)[11],(1,12)[12],
-- (2,1)[2],(2,4)[2],(2,6)[3],(2,8)[4],(2,10)[5],(2,12)[6],
-- (3,1)[3],(3,6)[2],(3,9)[3],(3,12)[4],
-- (4,1)[4],(4,2)[2],(4,8)[2],(4,12)[3],
-- (5,1)[5],(5,10)[2],
-- (6,1)[6],(6,2)[3],(6,3)[2],(6,12)[2],
-- (7,1)[7],
-- (8,1)[8],(8,2)[4],(8,4)[2],
-- (9,1)[9],(9,3)[3],
-- (10,1)[10],(10,2)[5],(10,5)[2],
-- (11,1)[11],(12,1)[12],
-- (12,2)[6],(12,3)[4],(12,4)[3],(12,6)[2]}
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
grafoDivisibilidad :: Int -> Grafo Int Int
grafoDivisibilidad n = asignaPesos (creaGrafo ND (1,n) [(i,j) | i <- [1..n], j <- [1..n], mod i j == 0 || mod j i == 0, i /= j]) [((i,j), f (i,j)) | i <- [1..n], j <- [1..n], mod i j == 0 || mod j i == 0, i /= j]
where f (i,j) = div (max i j) (min i j)
-- ----------------------------------------------------------------------------
--
-- Ejercicio 5. Definir la función
-- eliminaUnitarias :: Char -> String -> String
-- tal que '(eliminaUnitarias c cs)' es la lista obtenida eliminando de la
-- cadena 'cs' las ocurrencias unitarias del carácter 'c' (es decir, aquellas
-- ocurrencias de 'c' tales que su elemento anterior y posterior es distinto de
-- 'c'). Por ejemplo,
-- eliminaUnitarias 'X' "" == ""
-- eliminaUnitarias 'X' "X" == ""
-- eliminaUnitarias 'X' "XX" == "XX"
-- eliminaUnitarias 'X' "XXX" == "XXX"
-- eliminaUnitarias 'X' "abcd" == "abcd"
-- eliminaUnitarias 'X' "Xabcd" == "abcd"
-- eliminaUnitarias 'X' "XXabcd" == "XXabcd"
-- eliminaUnitarias 'X' "XXXabcd" == "XXXabcd"
-- eliminaUnitarias 'X' "abcdX" == "abcd"
-- eliminaUnitarias 'X' "abcdXX" == "abcdXX"
-- eliminaUnitarias 'X' "abcdXXX" == "abcdXXX"
-- eliminaUnitarias 'X' "abXcd" == "abcd"
-- eliminaUnitarias 'X' "abXXcd" == "abXXcd"
-- eliminaUnitarias 'X' "abXXXcd" == "abXXXcd"
-- eliminaUnitarias 'X' "XabXcdX" == "abcd"
-- eliminaUnitarias 'X' "XXabXXcdXX" == "XXabXXcdXX"
-- eliminaUnitarias 'X' "XXXabXXXcdXXX" == "XXXabXXXcdXXX"
-- eliminaUnitarias 'X' "XabXXcdXeXXXfXx" == "abXXcdeXXXfx"
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
eliminaUnitarias :: Char -> String -> String
eliminaUnitarias c cs = if length cs == 1 then if [c] == cs then "" else cs
else filter (/= ' ') (map snd (A.assocs (v A.// [ f n | n <- [0..x], v A.! n == c])))
where v = A.array (0,x) [(i, cs !! i) | i <- [0..x]]
x = length cs - 1
f n | n == 0 = if v A.! 0 /= v A.! 1 then (0,' ') else (0, v A.! 0)
| n == x = if v A.! (x-1) /= v A.! x then (x,' ') else (x, v A.! x)
| otherwise = if (v A.! n /= v A.! (n-1)) && (v A.! n /= v A.! (n+1)) then (n,' ') else (n, v A.! n)
-- ----------------------------------------------------------------------------
--
-- Ejercicio 6. La sucesión de Fibonacci es
-- 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,...
-- cuyos dos primeros términos son 0 y 1 y los restantes se obtienen sumando
-- los dos anteriores.
--
-- El árbol de computación de su 5º término es
-- 5
-- / \
-- / \
-- / \
-- / \
-- / \
-- 3 2
-- / \ / \
-- / \ 1 1
-- 2 1 / \
-- / \ / \ 1 0
-- 1 1 1 0
-- / \
-- 1 0
-- que, usando los árboles definidos por
-- data Arbol = H Int
-- | N Int Arbol Arbol
-- deriving (Eq, Show)
-- se puede representar por
-- N 5
-- (N 3
-- (N 2
-- (N 1 (H 1) (H 0))
-- (H 1))
-- (N 1 (H 1) (H 0)))
-- (N 2
-- (N 1 (H 1) (H 0))
-- (H 1))
--
-- Definir la función
-- arbolFib :: Int -> Arbol
-- tal que '(arbolFib n)' es el árbol de computación del 'n'-ésimo término de
-- la sucesión de Fibonacci. Por ejemplo,
-- arbolFib 5 ==>
-- N 5
-- (N 3
-- (N 2
-- (N 1 (H 1) (H 0))
-- (H 1))
-- (N 1 (H 1) (H 0)))
-- (N 2
-- (N 1 (H 1) (H 0))
-- (H 1))
-- arbolFib 6 ==>
-- N 8
-- (N 5
-- (N 3
-- (N 2
-- (N 1 (H 1) (H 0))
-- (H 1))
-- (N 1 (H 1) (H 0)))
-- (N 2
-- (N 1 (H 1) (H 0))
-- (H 1)))
-- (N 3
-- (N 2
-- (N 1 (H 1) (H 0)) (H 1))
-- (N 1 (H 1) (H 0)))
--
-- ----------------------------------------------------------------------------
data Arbol2 = H2 Int
| N2 Int Arbol2 Arbol2
deriving (Eq, Show)
-- Álvaro Galisteo:
arbolFib :: Int -> Arbol2
arbolFib 0 = H2 0
arbolFib 1 = H2 1
arbolFib n = N2 (sumaNodos (arbolFib (n-1)) (arbolFib (n-2))) (arbolFib (n-1)) (arbolFib (n-2))
sumaNodos :: Arbol2 -> Arbol2 -> Int
sumaNodos (N2 a _ _) (N2 b _ _) = a+b
sumaNodos (N2 a _ _) (H2 b) = a+b
sumaNodos (H2 b) (N2 a _ _) = a+b
sumaNodos (H2 a) (H2 b) = a+b
-- ----------------------------------------------------------------------------
--
-- Ejercicio 7.1. Una matriz equis es una matriz en la que hay una
-- posición (i,j) tal que todos los elementos que están fuera de las diagonales
-- que pasan por dicha posición son nulos. Por ejemplo,
--
-- ( 0 2 0 2 ) ( 2 0 0 0 1 ) ( 3 0 0 0 5 )
-- ( 0 0 4 0 ) ( 0 0 0 3 0 ) ( 0 4 0 2 0 )
-- ( 0 3 0 7 ) ( 0 0 1 0 0 ) ( 0 0 1 0 0 )
-- ( 5 0 0 0 ) ( 0 7 0 6 0 )
--
-- Utilizaremos la librería Matrix para desarrollar este ejercicio.
--
-- Definir la función
-- esMatrizEquis :: M.Matrix Int -> Bool
-- tal que '(esMatrizEquis m)' comprueba si la matriz 'm' es una matriz equis.
-- Por ejemplo, dadas las matrices
-- m1 = M.matrix 3 3 (\ (i,j) -> (if (all odd [i,j]) then 1 else 0))
-- m2 = M.matrix 3 4 (\ (i,j) -> (i+j))
-- entonces
-- esMatrizEquis m1 == True
-- esMatrizEquis m2 == False
--
-- ----------------------------------------------------------------------------
m1, m2 :: M.Matrix Int
m1 = M.matrix 3 3 (\ (i,j) -> (if (all odd [i,j]) then 1 else 0))
m2 = M.matrix 3 4 (\ (i,j) -> (i+j))
-- Álvaro Galisteo:
esMatrizEquis :: M.Matrix Int -> Bool
esMatrizEquis m = or [centroEquis (y,z) m | y <- [1..a], z <- [1..b]]
where a = M.nrows m
b = M.ncols m
centroEquis :: (Int, Int) -> M.Matrix Int -> Bool
centroEquis (i,j) m = all (==0) [m M.! (y,z) | y <- [1..a], z <- [1..b], y-z /= i-j, not (elem (y,z) (otraDiagonal (i,j) m))]
where a = M.nrows m
b = M.ncols m
otraDiagonal :: (Int, Int) -> M.Matrix Int -> [(Int, Int)]
otraDiagonal (i,j) m = [(i+(1*k),j-(1*k)) | k <- [1..(max a b)], i+(1*k) <= a && j-(1*k) >= 1] ++ [(i-(1*k),j+(1*k)) | k <- [1..(max a b)], i-(1*k) >= 1 && j+(1*k) <= b]
where a = M.nrows m
b = M.ncols m
-- ----------------------------------------------------------------------------
--
-- Ejercicio 7.2. Definir la función
-- matrizEquis :: Int -> Int -> Int -> Int -> M.Matrix Int
-- tal que '(matrizEquis p q f c)' es la matriz equis de dimensión '(p,q)' con
-- respecto a la posición '(f,c)', en la que el valor de cada elemento no nulo
-- es la distancia en línea recta a la posición '(f,c)', contando también esta
-- última. Por ejemplo,
-- matrizEquis 3 3 2 2 =>
-- ( 2 0 2 )
-- ( 0 1 0 )
-- ( 2 0 2 )
-- matrizEquis 4 5 2 3 =>
-- ( 0 2 0 2 0 )
-- ( 0 0 1 0 0 )
-- ( 0 2 0 2 0 )
-- ( 3 0 0 0 3 )
-- matrizEquis 5 3 2 3 =>
-- ( 0 2 0 )
-- ( 0 0 1 )
-- ( 0 2 0 )
-- ( 3 0 0 )
-- ( 0 0 0 )
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
matrizEquis :: Int -> Int -> Int -> Int -> M.Matrix Int
matrizEquis p q f c = M.matrix p q (putElem p q f c)
putElem :: Int -> Int -> Int -> Int -> (Int,Int) -> Int
putElem p q f c (i,j) | elem (i,j) (otraDiagonal (f,c) (M.zero p q)) = abs (i-f) + 1
| f-c == i-j = abs (i-f) +1
| i == f && j == c = 1
| otherwise = 0
-- ----------------------------------------------------------------------------
--
-- Ejercicio 8. El polinomio cromático de un grafo calcula el número
-- de maneras en las cuales puede ser coloreado el grafo usando un número de
-- colores dado, de forma que dos vértices adyacentes no tengan el mismo color.
--
-- En el caso del grafo completo de n vértices, su polinomio cromático es
-- P(n)(x) = x(x-1)(x-2) ... (x-(n-1)). Por ejemplo,
-- P(3)(x) = x(x-1)(x-2) = x^3 - 3*x^2 + 2*x
-- P(4)(x) = x(x-1)(x-2)(x-3) = x^4 - 6*x^3 + 11*x^2 - 6*x
-- Lo que significa que P(4)(x) es el número de formas de colorear el grafo
-- completo de 4 vértices con x colores. Por tanto,
-- P(4)(2) = 0 (no se puede colorear con 2 colores)
-- P(4)(4) = 24 (hay 24 formas de colorearlo con 4 colores)
--
-- Ejercicio 3.1. Definir la función
-- polGC :: Int -> Polinomio Int
-- tal que '(polGC n)' es el polinomio cromático del grafo completo de 'n'
-- vértices. Por ejemplo,
-- polGC 4 == x^4 + -6*x^3 + 11*x^2 + -6*x
-- polGC 5 == x^5 + -10*x^4 + 35*x^3 + -50*x^2 + 24*x
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
polGC :: Int -> Polinomio Int
polGC 1 = consPol 1 1 polCero
polGC n = multPol (n-1) (polGC (n-1))
multPol :: Int -> Polinomio Int -> Polinomio Int
multPol n p1 = dispersaToPol ((map (\ (a,b) -> (a,b*(-n))) (dispersa p1)) ++ (map (\ (a,b) -> (a+1,b)) (dispersa p1)))
dispersa :: Polinomio Int -> [(Int,Int)]
dispersa p1 | esPolCero p1 = []
| otherwise = (grado p1, coefLider p1):(dispersa (restoPol p1))
dispersaToPol :: [(Int,Int)] -> Polinomio Int
dispersaToPol [] = polCero
dispersaToPol (x:xs) = consPol (fst x) (snd x) (dispersaToPol xs)
-- ----------------------------------------------------------------------------
--
-- Ejercicio 9.1. En la aritmética lunar la suma se hace como en la
-- terrícola salvo que sus tablas de sumar son distintas. La suma lunar de dos
-- dígitos es su máximo (por ejemplo, 1 + 3 = 3 y 7 + 4 = 7). Por tanto,
-- 3 5 7
-- + 6 4
-- -------
-- 3 6 7
--
-- Ejercicio 1.1. Definir la función
-- suma :: Integer -> Integer -> Integer
-- tal que '(suma x y)' es la suma lunar de los números 'x' e 'y'. Por ejemplo,
-- suma 357 64 == 367
-- suma 64 357 == 367
-- suma 1 3 == 3
-- suma 7 4 == 7
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
suma :: Integer -> Integer -> Integer
suma x y = f (replicate (maxLen - (length (show x))) '0' ++ (show x)) (replicate (maxLen - (length (show y))) '0' ++ (show y))
where maxLen = max (length (show x)) (length (show y))
f xs ys = read (reverse (map (\ (a,b) -> max a b) (zip (reverse xs) (reverse ys)))) :: Integer
-- ----------------------------------------------------------------------------
--
-- Ejercicio 9.2. Comprobar con QuickCheck que la suma lunar es conmutativa.
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
prop_conmutativa :: Integer -> Integer -> Property
prop_conmutativa n m = n >= 0 && m >= 0 ==> n + m == m + n
-- *Main> quickCheck prop_conmutativa
-- +++ OK, passed 100 tests; 257 discarded.
-- ----------------------------------------------------------------------------
--
-- Ejercicio 10.
--
-- El árbol binario de los divisores de 24 es
-- 90
-- /\
-- 2 45
-- /\
-- 3 15
-- /\
-- 3 5
--
-- Se puede representar por
-- N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))
-- usando el tipo de dato definido por
--
-- data Arbol = H Int
-- | N Int Arbol Arbol
-- deriving (Eq, Show)
-- Análogamente se obtiene el árbol binario de cualquier número x: se comienza
-- en x y en cada paso se tiene dos hijos (su menor divisor y su cociente)
-- hasta obtener números primos en las hojas.
--
-- Definir las funciones
-- arbolDivisores2 :: Int -> Arbol
-- hojasArbolDivisores :: Int -> [Int]
-- tales que
-- (arbolDivisores2 x) es el árbol binario de los divisores de x. Por ejemplo,
-- arbolDivisores2 90 == N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))
-- arbolDivisores2 24 == N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3)))
-- arbolDivisores2 300 == N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5))))
--
-- (hojasArbolDivisores x) es la lista de las hojas del árbol binario de los
-- divisores de x. Por ejemplo
-- hojasArbolDivisores 90 == [2,3,3,5]
-- hojasArbolDivisores 24 == [2,2,2,3]
-- hojasArbolDivisores 300 == [2,2,3,5,5]
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
arbolDivisores2 :: Int -> Arbol2
arbolDivisores2 x | (divisores' x) == [1] = H2 x
| otherwise = N2 x (arbolDivisores2 y) (arbolDivisores2 (div x y))
where y = head (tail (divisores' x))
divisores' :: Int -> [Int]
divisores' n = [x | x <- [1..(div n 2)], mod n x == 0]
hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores x = listaDivAux (arbolDivisores2 x)
listaDivAux :: Arbol2 -> [Int]
listaDivAux (N2 e l r) = listaDivAux l ++ listaDivAux r
listaDivAux (H2 e) = [e]
-- ----------------------------------------------------------------------------
--
-- Ejercicio 11.1. Sheldon Cooper tiene que pagar 10$ por el
-- aparcamiento, pero sólo tiene monedas de 1$, de 2$ y de 5$. Entonces dice:
-- "podría hacer esto de 128 formas distintas y necesitaría un total de 831
-- monedas para hacerlo de todas las formas posibles". Está contando las formas
-- de disponer las monedas en la máquina para pagar los 10$ y el número de
-- monedas que necesita para hacerlas todas. Por ejemplo, si tuviese que pagar
-- 4$ entonces habría 5 formas de pagar: [2,2], [2,1,1], [1,2,1], [1,1,2] y
-- [1,1,1,1] y el total de monedas que se necesitan para hacerlas todas es
-- 2 + 3 + 3 + 3 + 4 = 15.
--
-- Definir la función (mediante programación dinámica)
-- distribuciones :: Integer -> Integer
-- tal que '(distribuciones n)' es el número de formas distintas de distribuir
-- la cantidad 'n' como una secuencia de monedas de 1$, 2$ y 5$, con un valor
-- total igual a 'n'. Por ejemplo,
-- distribuciones 5 == 9
-- distribuciones 10 == 128
-- distribuciones 100 == 91197869007632925819218
-- length (show (distribuciones 1000)) == 232
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
distribuciones :: Integer -> Integer
distribuciones n = v A.! n
where v = A.array (1,n) [(i,f i) | i <- [1..n]]
f i | i == 1 = 1
| i == 2 = 2
| i == 3 = 3
| i == 4 = 5
| i == 5 = 9
| otherwise = v A.! (i-1) + v A.! (i-2) + v A.! (i-5)
-- ----------------------------------------------------------------------------
--
-- Ejercicio 11.2 Definir la función
-- cuentaMonedas :: Integer -> Integer
-- tal que '(cuentaMonedas n)' es el número de monedas que le hacen falta a
-- Sheldon Cooper para construir todas las distribuciones de la cantidad 'n'
-- como una secuencia de monedas de 1$, 2$ y 5$, con un valor total igual a
-- 'n'. Por ejemplo,
-- cuentaMonedas 5 == 31
-- cuentaMonedas 10 == 841
-- cuentaMonedas 100 == 5660554507743281845750870
-- length (show (cuentaMonedas 1000)) == 235
--
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
cuentaMonedas :: Integer -> Integer
cuentaMonedas n = v A.! n
where v = A.array (1,n) [(i,f i) | i <- [1..n]]
f i | i == 1 = 1
| i == 2 = 3
| i == 3 = 7
| i == 4 = 15
| i == 5 = 31
| otherwise = v A.! (i-1) + v A.! (i-2) + v A.! (i-5) + distribuciones i
-- ----------------------------------------------------------------------------
--
-- Ejercicio 12. Un clique de un grafo no dirigido G es un conjunto de vértices
-- V tal que el subgrafo de G inducido por V es un grafo completo. Por ejemplo,
-- en el grafo,
--
-- 6
-- \
-- 4 ---- 5
-- | | \
-- | | 1
-- | | /
-- 3 ---- 2
--
-- el conjunto de vértices {1,2,5} es un clique y el conjunto {2,3,4,5} no lo
-- es.
--
-- En Haskell se puede representar el grafo anterior por
-- g1 :: Grafo Int Int
-- g1 = creaGrafo ND (1,6) [(1,2),(1,5),(2,3),(3,4),(5,2),(4,5),(4,6)]
--
-- Definir la función
-- esClique :: Grafo Int Int -> [Int] -> Bool
-- tal que '(esClique g xs)' se verifica si el conjunto de vértices 'xs' es un
-- clique del grafo 'g'. Por ejemplo,
-- esClique g1 [1,2,5] == True
-- esClique g1 [2,3,4,5] == False
--
-- ----------------------------------------------------------------------------
g1 :: Grafo Int Int
g1 = creaGrafo ND (1,6) [(1,2),(1,5),(2,3),(3,4),(5,2),(4,5),(4,6)]
-- Álvaro Galisteo:
esClique :: Grafo Int Int -> [Int] -> Bool
esClique g xs = (intersect (filter (\ (a,b) -> elem a xs && elem b xs) (aristas g)) [(i,j) | i <- xs, j <- xs, i /= j]) == [(i,j) | i <- xs, j <- xs, i /= j]
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)