-- 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
--
-- ----------------------------------------------------------------------------
esArmstrong :: Integer -> Bool
esArmstrong n = n == sum (map (^numDigitos) digitos)
where digitos = [read [x] | x <- show n]
numDigitos = length digitos
-- ----------------------------------------------------------------------------
--
-- 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]
--
-- ----------------------------------------------------------------------------
armstrong :: [Integer]
armstrong = filter esArmstrong [1..]
-- ----------------------------------------------------------------------------
--
-- 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)
arbolDivisores :: Integer -> Arbol
arbolDivisores 1 = N 1 []
arbolDivisores n = N n [arbolDivisores x | x <- divisoresMaximales n]
divisoresMaximales :: Integer -> [Integer]
divisoresMaximales n = filter (divisorMaximal n) [1..n-1]
divisorMaximal :: Integer -> Integer -> Bool
divisorMaximal b a = divisor a b && a /= b && not (any (\ c -> divisor a c && divisor c b) [a+1..b-1])
divisor :: Integer -> Integer -> Bool
divisor i j = j `mod` i == 0
-- ----------------------------------------------------------------------------
--
-- 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
--
-- ----------------------------------------------------------------------------
nOcurrenciasArbolDivisores :: Integer -> Integer -> Integer
nOcurrenciasArbolDivisores x n = cuentaOcurrencias x (arbolDivisores n)
cuentaOcurrencias :: Integer -> Arbol -> Integer
cuentaOcurrencias x (N raiz as) | x == raiz = 1 + sum (map (cuentaOcurrencias x) as)
| otherwise = sum (map (cuentaOcurrencias x) as)
-- ----------------------------------------------------------------------------
--
-- 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
--
-- ----------------------------------------------------------------------------
nEmparejamientos :: Integer -> Integer
nEmparejamientos n = m A.! n
where m = A.listArray (1,n) [ponElem i | i <- [1..n]]
ponElem 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]}
-- ----------------------------------------------------------------------------
grafoDivisibilidad :: Int -> Grafo Int Int
grafoDivisibilidad n = asignaPesos (creaGrafo ND (1,n) aristas) [((v1,v2),v2 `div` v1) | (v1,v2) <- aristas]
where aristas = [(x,y) | x <- [1..n], y <- [x+1..n], y `mod` x ==0]
-- ----------------------------------------------------------------------------
--
-- 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"
--
-- ----------------------------------------------------------------------------
eliminaUnitarias :: Char -> String -> String
eliminaUnitarias c [] = []
eliminaUnitarias c (x:[]) | c == x = []
| otherwise = x:[]
eliminaUnitarias c (x:y:xs) | c /= x = x:(eliminaUnitarias c (y:xs))
| c /= y = (eliminaUnitarias c (y:xs))
| otherwise = x:y:((takeWhile (==c) xs) ++
(eliminaUnitarias c (dropWhile (==c) xs)))
-- ----------------------------------------------------------------------------
--
-- 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)
arbolFib :: Int -> Arbol2
arbolFib n | n == 0 = H2 0
| n == 1 = H2 1
| otherwise = N2 (fib n) (arbolFib (n-1)) (arbolFib (n-2))
where fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
-- ----------------------------------------------------------------------------
--
-- 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))
esMatrizEquis :: M.Matrix Int -> Bool
esMatrizEquis m = any (esElCentroDeLaX) [(i,j) | i <- [1..f], j <- [1..c]]
where f = M.nrows m
c = M.ncols m
esElCentroDeLaX (i,j) = all (==0) [m M.! (ii,jj) | ii <- [1..f], jj <- [1..c], (ii + jj) == (i+j)] &&
all (==0) [m M.! (ii,jj) | ii <- [1..f], jj <- [1..c], (ii - jj) == (i-j)]
-- ----------------------------------------------------------------------------
--
-- 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 )
--
-- ----------------------------------------------------------------------------
matrizEquis :: Int -> Int -> Int -> Int -> M.Matrix Int
matrizEquis p q f c = M.matrix p q (\ (i,j) -> ponElem i j)
where ponElem i j | i + j /= f + c && i - j /= f - c = 0
| otherwise = 1 + abs (f-i)
-- ----------------------------------------------------------------------------
--
-- 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
--
-- ----------------------------------------------------------------------------
polGC :: Int -> Polinomio Int
polGC n = foldr multPol (consPol 0 1 polCero) [creaMultiplo n | n <- [0..n-1]]
creaMultiplo :: Int -> Polinomio Int
creaMultiplo n = consPol 1 1 (consPol 0 (-n) polCero)
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q | esPolCero p = q
| otherwise = consPol (grado p) (coefLider p) (sumaPol (restoPol p) q)
multTermPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multTermPol t p | esPolCero p = polCero
| otherwise = consPol (gt + gp) (ct * cp) (multTermPol t (restoPol p))
where gt = grado t
ct = coefLider t
gp = grado p
cp = coefLider p
restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
restaPol p q = sumaPol p (multTermPol (creaTermino 0 (-1)) q)
multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q | esPolCero p = polCero
| otherwise = sumaPol (multTermPol t q) (multPol (restoPol p) q)
where gp = grado p
cp = coefLider p
t = creaTermino gp cp
creaTermino :: (Num a, Eq a) => Int -> a -> Polinomio a
creaTermino n a = consPol n a polCero
-- ----------------------------------------------------------------------------
--
-- 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
--
-- ----------------------------------------------------------------------------
suma :: Integer -> Integer -> Integer
suma n m = procesaDigitos (reverse (digitos n)) (reverse (digitos m))
where procesaDigitos [] [] = 0
procesaDigitos (x:xs) [] = x + 10 * procesaDigitos xs []
procesaDigitos [] (y:ys) = y + 10 * procesaDigitos [] ys
procesaDigitos (x:xs) (y:ys) = (max x y) + 10 * (procesaDigitos xs ys)
digitos :: Integer -> [Integer]
digitos k = [read [x] | x <- show k]
-- ----------------------------------------------------------------------------
--
-- Ejercicio 9.2. Comprobar con QuickCheck que la suma lunar es conmutativa.
--
-- ----------------------------------------------------------------------------
prop_conmutativa :: Integer -> Integer -> Property
prop_conmutativa n m = n >= 0 && m >= 0 ==> n + m == m + n
-- ----------------------------------------------------------------------------
--
-- 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]
--
-- ----------------------------------------------------------------------------
arbolDivisores2 :: Int -> Arbol2
arbolDivisores2 n | primo n = H2 n
| otherwise = N2 n (H2 divisor) (arbolDivisores2 (n `div` divisor))
where divisor = primerDivisorPropio n
divisores :: Int -> [Int]
divisores n = [x | x <- [1..n], n `mod` x == 0]
primerDivisorPropio :: Int -> Int
primerDivisorPropio n = head (tail (divisores n))
primo :: Int -> Bool
primo n = divisores n == [1,n]
hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores n = buscaHojas (arbolDivisores2 n)
buscaHojas :: Arbol2 -> [Int]
buscaHojas (H2 n) = [n]
buscaHojas (N2 n izq der) = buscaHojas izq ++ buscaHojas der
-- ----------------------------------------------------------------------------
--
-- 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
--
-- ----------------------------------------------------------------------------
distribuciones :: Integer -> Integer
distribuciones n = m A.! n
where m = A.listArray (0,n) [ponElem i | i <- [0..n]]
ponElem 0 = 1
ponElem 1 = 1
ponElem 2 = 2
ponElem 3 = 3
ponElem 4 = 5
ponElem i = m A.! (i-1) + m A.! (i-2) + m 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
--
-- ----------------------------------------------------------------------------
cuentaMonedas :: Integer -> Integer
cuentaMonedas n = m A.! n
where m = A.listArray (0,n) [ponElem i | i <- [0..n]]
ponElem 0 = 0
ponElem 1 = 1
ponElem 2 = 3
ponElem 3 = 7
ponElem 4 = 15
ponElem i = distribuciones (i-1) + distribuciones (i-2) + distribuciones (i-5) +
m A.! (i-1) + m A.! (i-2) + m A.! (i-5)
-- ----------------------------------------------------------------------------
--
-- 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)]
esClique :: Grafo Int Int -> [Int] -> Bool
esClique g vs = all (aristaEn g) [(v1,v2) | v1 <- vs, v2 <- vs, v1 /= v2]
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)