-- I1M 2021-22: Relación 21
-- Programación dinámica.
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================
-- ============================================================================
-- Librerías auxiliares
-- ============================================================================
import qualified Data.Matrix as M
import qualified Data.Array as A
import qualified Data.Vector as V
-- ----------------------------------------------------------------------------
-- Ejercicio 1: Definir la función
-- fib :: Int -> Integer
-- tal que '(fib n)' es el n-ésimo de programación dinámica. Por ejemplo,
-- fib 10 == 55
-- fib 100 == 354224848179261915075
-- fib 1000 `mod` 10^20 == 76137795166849228875
-- fib 10000 `mod` 10^20 == 66073310059947366875
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
fib :: Int -> Integer
fib n = v A.! n
where v = A.array (0,n) [(i, f i)| i <- [0..n]]
f 0 = 0
f 1 = 1
f n = v A.! (n-1) + v A.! (n-2)
-- ----------------------------------------------------------------------------
-- Ejercicio 2: Los números combinatorios se pueden calcular de forma recursiva
-- mediante el uso de la siguiente ecuación en recurrencia:
-- C(n,m) = C(n-1,m-1) + C(n-1,m)
-- Para ello se puede crear esta matriz, llamada triángulo de Tartaglia:
-- 1
-- 1 1
-- 1 2 1
-- 1 3 3 1
-- 1 4 6 4 1
-- 1 5 10 10 5 1
-- ...
-- Que también nos da, para cada fila "i", los coeficientes del binomio de
-- Newton (a+b)^i
-- Crear una función (numerosCombinatorios n m) que devuelva el valor del
-- número combinatorio C(n,m)
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
numerosCombinatorios :: Int -> Int -> Integer
numerosCombinatorios n m = (matrizTrianguloTartaglia n m) A.! (n,m)
matrizTrianguloTartaglia :: Int -> Int -> A.Array (Int,Int) Integer
matrizTrianguloTartaglia n m = A.array ((0,0),(n,m)) [((i,j),f i j)| i <- [0..n], j <- [0..m]]
where f i 0 = 1
f i j | i == j = 1
| otherwise = (matrizTrianguloTartaglia n m) A.! (i-1,j) + (matrizTrianguloTartaglia n m) A.! (i-1,j-1)
-- ----------------------------------------------------------------------------
-- Ejercicio 3: Un montón de barriles se construye apilando unos encima de
-- otros por capas, de forma que en cada capa todos los barriles estén apoyados
-- sobre dos de la capa inferior y todos los barriles de una misma capa estén
-- pegados unos a otros. Por ejemplo, los siguientes montones son válidos:
-- _ _ _ _
-- / \ / \ / \ / \
-- _\_/_ _\_/_\_/_ _ _ _\_/_ _
-- / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
-- \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/
--
-- y los siguientes no son válidos:
-- _ _ _ _ _ _
-- / \ / \ / \ / \ / \ / \
-- \_/_\_/_ _\_/_ _\_/_ _ _\_/_\_/
-- / \ / \ / \ / \ / \ / \ / \ / \ / \
-- \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/
--
-- Se puede comprobar que el número de formas distintas de construir montones
-- con n barriles en la base (M_n) viene dado por la siguiente fórmula:
--
-- (n-1)
-- -------
-- \
-- \
-- M_n = 1 + ) (n-j) * M_j
-- /
-- /
-- -------
-- j = 1
-- Intente razonar la fórmula anterior.
-- Definir la función
-- montones :: Int -> Integer
-- tal que '(montones base)' es el número de formas distintas de construir
-- montones con 'base' barriles en la base, calculado mediante la técnica de
-- programación dinámica. Por ejemplo,
-- montones 1 == 1
-- montones 10 == 4181
-- montones 20 == 63245986
-- montones 30 == 956722026041
-- montones 40 == 14472334024676221
-- montones 50 == 218922995834555169026
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
montones :: Integer -> Integer
montones n = m A.! n
where m = A.listArray (0,n) [f i| i <-[0..n]]
f i | i == 0 = 0
| otherwise = 1 + sum [(i-j)*(m A.! j) | j <- [1..(i-1)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 4. Definir la función
-- numeroFactoresPrimos :: Int -> Int
-- tal que '(numeroFactoresPrimos n)' es el número de factores primos
-- (contando repeticiones) de 'n', calculado
-- mediante la técnica de programación dinámica. Por ejemplo,
-- numeroFactoresPrimos 2 == 1
-- numeroFactoresPrimos 10 == 2
-- numeroFactoresPrimos 100 == 4
-- numeroFactoresPrimos 1000 == 6
-- numeroFactoresPrimos (2*3*5*7*11*13) = 6
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
numeroFactoresPrimos :: Integer -> Integer
numeroFactoresPrimos n = m A.! n
where m = A.listArray (0,n) [f i| i <- [0..n]]
f i | i == 0 = 0
| i == 1 = 1
| otherwise = 1 + m A.! (div' i (head' [x | x <- (listaPrimos i), mod i x == 0]))
primo :: Integer -> Bool
primo n = and [mod n x /= 0| x <- [2..(n-1)]]
listaPrimos :: Integer -> [Integer]
listaPrimos n = [x | x <- [2..(n-1)], and[mod x y /= 0| y <- [2..(x-1)]]]
head' xs = if xs == [] then 0 else head xs
div' x y = if y == 0 then 0 else div x y
-- ----------------------------------------------------------------------------
-- Ejercicio 5. Problema número 15 de 'Project Euler': Comenzando en la esquina
-- superior izquierda de una rejilla de dimensiones 2x2, y moviéndose sólo
-- hacia la derecha y hacia abajo, hay exactamente 6 caminos distintos que
-- llegan a la esquina inferior derecha.
--
-- ╒═══╤═══╗ ╒═══╗───┐ ╒═══╗───┐ ╓───┬───┐ ╓───┬───┐ ╓───┬───┐
-- │ │ ║ │ ║ │ │ ║ │ ║ │ │ ║ │ │ ║ │ │
-- ├───┼───╢ ├───╚═══╗ ├───║───┤ ╚═══╪═══╗ ╚═══╗───┤ ╟───┼───┤
-- │ │ ║ │ │ ║ │ ║ │ │ │ ║ │ ║ │ ║ │ │
-- └───┴───╜ └───┴───╜ └───╚═══╛ └───┴───╜ └───╚═══╛ ╚═══╧═══╛
--
-- Definir la función:
-- caminos :: Int -> Int -> Integer
-- tal que '(caminos n m)' es el número de caminos que hay en una rejilla de
-- 'n' filas y 'm' columnas, desde la esquina superior izquierda hasta la
-- esquina inferior derecha, moviéndose sólo hacia la derecha y hacia abajo,
-- calculado mediante la técnica de programación dinámica. Por ejemplo,
-- caminos 3 3 == 6
-- caminos 3 4 == 10
-- caminos 4 4 == 20
-- caminos 4 5 == 35
-- caminos 5 5 == 70
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
caminos :: Int -> Int -> Int
caminos f c = m A.! (f,c)
where m = A.listArray ((0,0),(f,c)) [g i j| i <- [0..f], j <- [0..c]]
g i j | i == 0 || j == 0 = 0
| i == 1 || j == 1 = 1
| otherwise = 2 *(m A.! (i-1,j-1)) + (m A.! (i-2,j)) + (m A.! (i,j-2))
-- ----------------------------------------------------------------------------
-- Ejercicio 6: Problema número 116 de 'Project Euler': En una rejilla de 5
-- cuadros de longitud se pueden colocar de distintas formas piezas rojas de 2
-- cuadros de longitud, piezas verdes de 3 cuadros de longitud o piezas azules
-- de 4 cuadros de longitud.
--
-- En concreto, hay 7 formas distintas de colocar piezas rojas en la rejilla de
-- 5 cuadros:
-- ╔═══════╗───┬───┬───┐ ┌───╔═══════╗───┬───┐ ┌───┬───╔═══════╗───┐
-- ║ ║ │ │ │ │ ║ ║ │ │ │ │ ║ ║ │
-- ╚═══════╝───┴───┴───┘ └───╚═══════╝───┴───┘ └───┴───╚═══════╝───┘
-- ┌───┬───┬───╔═══════╗ ╔═══════╦═══════╗───┐ ╔═══════╗───╔═══════╗
-- │ │ │ ║ ║ ║ ║ ║ │ ║ ║ ║ ║
-- └───┴───┴───╚═══════╝ ╚═══════╩═══════╝───┘ ╚═══════╝───╚═══════╝
-- ┌───╔═══════╦═══════╗
-- │ ║ ║ ║
-- └───╚═══════╩═══════╝
--
-- Hay 3 formas distintas de colocar piezas verdes:
-- ╔═══════════╗───┬───┐ ┌───╔═══════════╗───┐ ┌───┬───╔═══════════╗
-- ║ ║ │ │ │ ║ ║ │ │ │ ║ ║
-- ╚═══════════╝───┴───┘ └───╚═══════════╝───┘ └───┴───╚═══════════╝
--
-- Finalmente, hay 2 formas distintas de colocar piezas azules:
-- ╔═══════════════╗───┐ ┌───╔═══════════════╗
-- ║ ║ │ │ ║ ║
-- ╚═══════════════╝───┘ └───╚═══════════════╝
--
-- Suponiendo que las piezas de colores no se pueden mezclar, hay 12 formas
-- distintas de colocar piezas en una rejilla de 5 cuadros.
--
-- Definir la función
-- combinaciones116 :: Int -> Integer
-- tal que '(combinaciones116 n)' es el número de formas distintas de colocar
-- piezas rojas de 2 cuadros de longitud, piezas verdes de 3 cuadros de
-- longitud o piezas azules de 4 cuadros de longitud, en una rejilla de 'n'
-- cuadros de longitud, sin mezclar piezas de distintos colores y usando al
-- menos una, calculado mediante la técnica de programación dinámica. Por
-- ejemplo,
-- combinaciones116 5 == 12
-- combinaciones116 10 == 128
-- combinaciones116 15 == 1242
-- combinaciones116 20 == 12566
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
combinaciones116 :: Int -> Integer
combinaciones116 n = sum [m A.! (x,n) | x <- [0,1,2]]
where m = A.listArray ((0,0),(2,n)) [f i j | i <- [0..2], j <- [0..n]]
f i j | j < (i+2) = 0
| j == (i+2) = 1
| j > (i+2) = (m A.! (i,j-1)) + (m A.! (i,j-(i+2))) + 1
-- ----------------------------------------------------------------------------
-- Ejercicio 7: Problema número 117 de 'Project Euler': En una rejilla de 5
-- cuadros de longitud se pueden colocar de distintas formas piezas rojas de 2
-- cuadros de longitud, piezas verdes de 3 cuadros de longitud y piezas azules
-- de 4 cuadros de longitud.
--
-- Hay 15 formas distintas de colocar las piezas:
--
-- ┌───┬───┬───┬───┬───┐ ╔═══════╗───┬───┬───┐ ┌───╔═══════╗───┬───┐
-- │ │ │ │ │ │ ║ ║ │ │ │ │ ║ ║ │ │
-- └───┴───┴───┴───┴───┘ ╚═══════╝───┴───┴───┘ └───╚═══════╝───┴───┘
-- ┌───┬───╔═══════╗───┐ ┌───┬───┬───╔═══════╗ ╔═══════╦═══════╗───┐
-- │ │ ║ ║ │ │ │ │ ║ ║ ║ ║ ║ │
-- └───┴───╚═══════╝───┘ └───┴───┴───╚═══════╝ ╚═══════╩═══════╝───┘
-- ╔═══════╗───╔═══════╗ ┌───╔═══════╦═══════╗ ╔═══════════╗───┬───┐
-- ║ ║ ║ ║ │ ║ ║ ║ ║ ║ │ │
-- ╚═══════╝───╚═══════╝ └───╚═══════╩═══════╝ ╚═══════════╝───┴───┘
-- ┌───╔═══════════╗───┐ ┌───┬───╔═══════════╗ ╔═══════╦═══════════╗
-- │ ║ ║ │ │ │ ║ ║ ║ ║ ║
-- └───╚═══════════╝───┘ └───┴───╚═══════════╝ ╚═══════╩═══════════╝
-- ╔═══════════╦═══════╗ ╔═══════════════╗───┐ ┌───╔═══════════════╗
-- ║ ║ ║ ║ ║ │ │ ║ ║
-- ╚═══════════╩═══════╝ ╚═══════════════╝───┘ └───╚═══════════════╝
--
-- Definir la función
-- combinaciones117 :: Int -> Integer
-- tal que '(combinaciones117 n)' es el número de formas distintas de colocar
-- piezas rojas de 2 cuadros de longitud, piezas verdes de 3 cuadros de
-- longitud y piezas azules de 4 cuadros de longitud, en una rejilla de 'n'
-- cuadros de longitud, calculado mediante la técnica de programación
-- dinámica. Por ejemplo,
-- combinaciones117 5 == 15
-- combinaciones117 10 == 401
-- combinaciones117 15 == 10671
-- combinaciones117 20 == 283953
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
combinaciones117 :: Int -> Integer
combinaciones117 n = sum [m A.! (x,n) | x <- [0,1,2]] + (w A.! n) + 1
where m = A.listArray ((0,0),(2,n)) [f i j | i <- [0..2], j <- [0..n]]
f i j | j < (i+2) = 0
| j == (i+2) = 1
| j > (i+2) = (m A.! (i,j-1)) + (m A.! (i,j-(i+2))) + 1
w = A.listArray (0,n) [g i| i <- [0..n]]
g i | i < 5 = 0
| i >= 5 = sum [w A.! (i-x) | x <- [1,2,3,4]] + (sum [m A.! (0,i-x) | x <- [3,4]]) + (sum [m A.! (1,i-x) | x <- [2,4]]) + (sum [m A.! (2,i-x) | x <- [2,3]])
-- ----------------------------------------------------------------------------
-- Ejercicio 8. Problema número 114 de 'Project Euler': En una fila de 7
-- cuadros de longitud se pueden colocar de distintas formas piezas de longitud
-- mayor o igual que 3, de forma que haya al menos un cuadro de separación
-- entre cada dos de ellas consecutivas. Hay exactamente 17 formas de hacerlo:
--
-- ┌───┬───┬───┬───┬───┬───┬───┐ ╔═══════════╗───┬───┬───┬───┐
-- │ │ │ │ │ │ │ │ ║ ║ │ │ │ │
-- └───┴───┴───┴───┴───┴───┴───┘ ╚═══════════╝───┴───┴───┴───┘
-- ┌───╔═══════════╗───┬───┬───┐ ┌───┬───╔═══════════╗───┬───┐
-- │ ║ ║ │ │ │ │ │ ║ ║ │ │
-- └───╚═══════════╝───┴───┴───┘ └───┴───╚═══════════╝───┴───┘
-- ┌───┬───┬───╔═══════════╗───┐ ┌───┬───┬───┬───╔═══════════╗
-- │ │ │ ║ ║ │ │ │ │ │ ║ ║
-- └───┴───┴───╚═══════════╝───┘ └───┴───┴───┴───╚═══════════╝
-- ╔═══════════╗───╔═══════════╗ ╔═══════════════╗───┬───┬───┐
-- ║ ║ ║ ║ ║ ║ │ │ │
-- ╚═══════════╝───╚═══════════╝ ╚═══════════════╝───┴───┴───┘
-- ┌───╔═══════════════╗───┬───┐ ┌───┬───╔═══════════════╗───┐
-- │ ║ ║ │ │ │ │ ║ ║ │
-- └───╚═══════════════╝───┴───┘ └───┴───╚═══════════════╝───┘
-- ┌───┬───┬───╔═══════════════╗ ╔═══════════════════╗───┬───┐
-- │ │ │ ║ ║ ║ ║ │ │
-- └───┴───┴───╚═══════════════╝ ╚═══════════════════╝───┴───┘
-- ┌───╔═══════════════════╗───┐ ┌───┬───╔═══════════════════╗
-- │ ║ ║ │ │ │ ║ ║
-- └───╚═══════════════════╝───┘ └───┴───╚═══════════════════╝
-- ╔═══════════════════════╗───┐ ┌───╔═══════════════════════╗
-- ║ ║ │ │ ║ ║
-- ╚═══════════════════════╝───┘ └───╚═══════════════════════╝
-- ╔═══════════════════════════╗
-- ║ ║
-- ╚═══════════════════════════╝
--
-- Aunque no se de el caso en el ejemplo anterior, es posible utilizar piezas
-- de distinta longitud.
--
-- Definir la función
-- combinaciones114 :: Int -> Integer
-- tal que '(combinaciones114 n)' es el número de formas distintas de colocar
-- piezas de longitud mayor o igual que 3 en una fila de 'n' cuadros de
-- longitud, de forma que haya al menos un cuadro de separación entre cada dos
-- de ellas consecutivas, calculado mediante la técnica de programación
-- dinámica. Por ejemplo,
-- combinaciones114 7 == 17
-- combinaciones114 10 == 72
-- combinaciones114 15 == 798
-- combinaciones114 20 == 8855
-- ----------------------------------------------------------------------------
combinaciones114 :: Int -> Integer
combinaciones114 = undefined
-- ----------------------------------------------------------------------------
-- Ejercicio 9. Problema número 18 de 'Project Euler': Comenzando desde el
-- extremo superior del siguiente triángulo de números y desplazándose siempre
-- hacia los números adyacentes de la fila inferior, se pueden describir un
-- total de 8 caminos que llevan hasta la última fila.
--
-- 3
-- 7 4
-- 2 4 6
-- 8 5 9 3
--
-- Si para cada camino calculamos la suma de los números por los que pasa,
-- se tendrá que el valor máximo es 3 + 7 + 4 + 9 = 23.
--
-- Definir la función
-- sumaMaxima :: [Int] -> Int
-- tal que '(sumaMaxima xs)' calcula el valor máximo de la suma de los números
-- de los caminos que van desde el extremo superior hasta un número de la
-- última fila en un triángulo de números formado por los elementos de la lista
-- 'xs', calculado mediante la técnica de programación dinámica. Por ejemplo,
-- sumaMaxima [3,7,4,2,4,6,8,5,9,3] == 23
--
-- Calcular el valor máximo de la suma de los números de los caminos que van
-- desde el extremo superior hasta un número de la última fila en el siguiente
-- triángulo de números:
--
-- 75
-- 95 64
-- 17 47 82
-- 18 35 87 10
-- 20 04 82 47 65
-- 19 01 23 75 03 34
-- 88 02 77 73 07 63 67
-- 99 65 04 28 06 16 70 92
-- 41 41 26 56 83 40 80 70 33
-- 41 48 72 33 47 32 37 16 94 29
-- 53 71 44 65 25 43 91 52 97 51 14
-- 70 11 33 28 77 73 17 78 39 68 17 57
-- 91 71 52 38 17 14 91 43 58 50 27 29 48
-- 63 66 04 68 89 53 67 30 73 16 69 87 40 31
-- 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
--
-- sumaMaxima numeros18 == 1074
-- Aplicar la función 'sumaMaxima' para resolver también el problema número 67
-- del proyecto Euler.
-- ----------------------------------------------------------------------------
numerosEjemplo :: [Int]
numerosEjemplo = [03,00,00,00,
07,04,00,00,
02,04,06,00,
08,05,09,03]
numeros18 :: [Int]
numeros18 = [75,00,00,00,00,00,00,00,00,00,00,00,00,00,00,
95,64,00,00,00,00,00,00,00,00,00,00,00,00,00 ,
17,47,82,00,00,00,00,00,00,00,00,00,00,00,00,
18,35,87,10,00,00,00,00,00,00,00,00,00,00,00,
20,04,82,47,65,00,00,00,00,00,00,00,00,00,00,
19,01,23,75,03,34,00,00,00,00,00,00,00,00,00,
88,02,77,73,07,63,67,00,00,00,00,00,00,00,00,
99,65,04,28,06,16,70,92,00,00,00,00,00,00,00,
41,41,26,56,83,40,80,70,33,00,00,00,00,00,00,
41,48,72,33,47,32,37,16,94,29,00,00,00,00,00,
53,71,44,65,25,43,91,52,97,51,14,00,00,00,00,
70,11,33,28,77,73,17,78,39,68,17,57,00,00,00,
91,71,52,38,17,14,91,43,58,50,27,29,48,00,00,
63,66,04,68,89,53,67,30,73,16,69,87,40,31,00,
04,62,98,27,23,09,70,98,73,93,38,53,60,04,23]
-- Álvaro Galisteo:
sumaMaxima :: [Int] -> Int
sumaMaxima xs = maximum [w A.! (x,y) | y <- [0..x]]
where m = A.listArray ((0,0),(x,x)) xs
x = (round (sqrt(sum [1 | x <- xs]))) - 1
w = A.listArray ((0,0),(x,x)) [f i j | i <- [0..x], j <- [0..x]]
f i j | i == 0 && j == 0 = m A.! (0,0)
| j > i = 0
| j == 0 = m A.! (i,j) + w A.! (i-1,j)
| otherwise = m A.! (i,j) + max (w A.! (i-1,j)) (w A.! (i-1,j-1))
-- ----------------------------------------------------------------------------
-- Ejercicio 10. Para multiplicar una matriz de orden AxB por otra de orden BxC
-- se necesitan realizar un total de A*B*C multiplicaciones de elementos. El
-- problema del producto de cadenas de matrices consiste en determinar la mejor
-- forma de multiplicar una secuencia de matrices (con las dimensiones
-- adecuadas) minimizando el número de multiplicaciones de elementos.
--
-- Por ejemplo, si tenemos cuatro matrices A(30x1), B(1x40), C(40x10) y
-- D(10x25), los productos necesarios en las posibles asociaciones de la cadena
-- de multiplicaciones de matrices A*B*C*D son:
-- ((A*B)*C)*D : 30x1x40 + 30x40x10 + 30x10x25 = 20700
-- A*(B*(C*D)) : 40x10x25 + 1x40x25 + 30x1x25 = 11750
-- (A*B)*(C*D) : 30x1x40 + 40x10x25 + 30x40x25 = 41200
-- A*((B*C)*D) : 1x40x10 + 1x10x25 + 30x1x25 = 1400
-- (A*(B*C))*D : 1x40x10 + 30x1x10 + 30x10x25 = 8200
--
-- De forma general, consideremos un total de n matrices A1, A2, A3, ..., An
-- tales que tienen dimensiones coherentes para realizar la multiplicación
-- A1*A2*A3*...*An, y la lista de sus dimensiones es [d0,d1,d2,...,dn], es
-- decir la dimensión de A1 es d0xd1, la dimensión de A2 es d1xd2, la dimensión
-- de A3 es d2xd3, ... Si cij es el mínimo número de operaciones necesarias
-- para multiplicar las matrices desde la i-ésima hasta la j-ésima entonces se
-- tiene:
-- - cii = 0, para todo i = 1..n
-- - cij = minimo { cik + c(k+1)j + d(i-1)*dk*dj | i <= k < j }
-- - c1n es la solución del problema
--
-- Definir la función
-- pcm :: [Int] -> Int
-- tal que '(pcm ds)' es el menor número de operaciones necesarias para
-- multiplicar matrices de las dimensiones indicadas en 'ds', calculado
-- mediante la técnica de programación dinámica. Por ejemplo,
-- pcm [30,1,40,10,25] == 1400
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
pcm :: [Int] -> Int
pcm ds = c A.! (1,n)
where n = (length ds) - 1
d = A.listArray (0,n) ds
c = A.listArray ((1,1),(n,n)) [f i j | i <- [1..n], j <- [1..n]]
f i j | i == j = 0
| otherwise = minimum [c A.! (i,k) + c A.! (k+1,j) + (d A.! (i-1)) * (d A.! k) * (d A.! j) | k <- [i..j-1]]
-- ----------------------------------------------------------------------------
-- Ejercicio 11. Una triangulación de un polígono es una división del área en
-- un conjunto de triángulos, de forma que la unión de todos ellos es igual al
-- polígono original, y cualquier par de triángulos es disjunto o comparte
-- únicamente un vértice o un lado. En el caso de polígonos convexos, la
-- cantidad de triangulaciones posibles depende únicamente del número de
-- vértices del polígono.
--
-- Si llamamos T(n) al número de triangulaciones de un polígono de n vértices,
-- se verifica la siguiente relación de recurrencia:
-- T(2) = 1
-- T(n) = T(2)*T(n-1) + T(3)*T(n-2) + ... + T(n-1)*T(2)
--
-- Definir la función
-- numeroTriangulaciones :: Integer -> Integer
-- tal que '(numeroTriangulaciones n)' es el número de triangulaciones de un
-- polígono convexo de n vértices, calculado mediante la técnica de
-- programación dinámica. Por ejemplo,
-- numeroTriangulaciones 3 == 1
-- numeroTriangulaciones 5 == 5
-- numeroTriangulaciones 6 == 14
-- numeroTriangulaciones 7 == 42
-- numeroTriangulaciones 50 == 131327898242169365477991900
-- numeroTriangulaciones 100 ==
-- 57743358069601357782187700608042856334020731624756611000
-- ----------------------------------------------------------------------------
-- Álvaro Galisteo:
numeroTriangulaciones :: Int -> Integer
numeroTriangulaciones n = m A.! n
where m = A.listArray (2,n) [f i | i <- [2..n]]
f i | i == 2 = 1
| otherwise = sum [(m A.! x)*(m A.! (i-(x-1)))| x <- [2..(i-1)]]
-- ----------------------------------------------------------------------------
-- Ejercicio 12. En el siguiente gráfico se representa en una cuadrícula el
-- plano de Manhattan. Cada línea es una opción a seguir; el número representa
-- las atracciones que se pueden visitar si se elige esa opción.
--
-- * ---3--- * ---2--- * ---4--- * ---0--- *
-- | | | | |
-- 1 0 2 4 3
-- | | | | |
-- * ---3--- * ---2--- * ---4--- * ---2--- *
-- | | | | |
-- 4 6 5 2 1
-- | | | | |
-- * ---0--- * ---7--- * ---3--- * ---4--- *
-- | | | | |
-- 4 4 5 2 1
-- | | | | |
-- * ---3--- * ---3--- * ---0--- * ---2--- *
-- | | | | |
-- 5 6 8 5 3
-- | | | | |
-- * ---1--- * ---3--- * ---2--- * ---2--- *
--
-- El turista entra por el extremo superior izquierdo y sale por el extremo
-- inferior derecho. Sólo puede moverse en las direcciones Sur y Este (es
-- decir, hacia abajo o hacia la derecha).
--
-- Representamos el mapa mediante una matriz p tal que p(i,j) = (a,b), donde
-- a = nº de atracciones si se va hacia el sur y
-- b = nº de atracciones si se va hacia el este
-- Además, ponemos un 0 en el valor del número de atracciones por un camino que
-- no se puede elegir. De esta forma, el mapa anterior se representa por la
-- siguiente matriz:
--
-- ( (1,3) (0,2) (2,4) (4,0) (3,0) )
-- ( (4,3) (6,2) (5,4) (2,2) (1,0) )
-- ( (4,0) (4,7) (5,3) (2,4) (1,0) )
-- ( (5,3) (6,3) (8,0) (5,2) (3,0) )
-- ( (0,1) (0,3) (0,2) (0,2) (0,0) )
--
-- En este caso, si se hace el recorrido
-- [S, E, S, E, S, S, E, E],
-- el número de atracciones es
-- 1 3 6 7 5 8 2 2
-- cuya suma es 34.
--
-- Definir la función
-- mayorNumeroV :: M.Matrix (Int,Int) -> Int
-- tal que '(mayorNumeroV p)' es el máximo número de atracciones que se pueden
-- visitar en el plano representado por la matriz 'p', calculado mediante la
-- técnica de programación dinámica. Por ejemplo, si se define la matriz
-- anterior por
-- ej1b :: M.Matrix (Int,Int)
-- ej1b = M.fromLists [[(1,3),(0,2),(2,4),(4,0),(3,0)],
-- [(4,3),(6,2),(5,4),(2,2),(1,0)],
-- [(4,0),(4,7),(5,3),(2,4),(1,0)],
-- [(5,3),(6,3),(8,0),(5,2),(3,0)],
-- [(0,1),(0,3),(0,2),(0,2),(0,0)]]
-- entonces
-- mayorNumeroV ej1b == 34
-- mayorNumeroV (M.fromLists [[(1,3),(0,0)],
-- [(0,3),(0,0)]]) == 4
-- mayorNumeroV (M.fromLists [[(1,3),(0,2),(2,0)],
-- [(4,3),(6,2),(5,0)],
-- [(0,0),(0,7),(0,0)]]) == 17
-- ----------------------------------------------------------------------------
ej1b :: M.Matrix (Int,Int)
ej1b = M.fromLists [[(1,3),(0,2),(2,4),(4,0),(3,0)],
[(4,3),(6,2),(5,4),(2,2),(1,0)],
[(4,0),(4,7),(5,3),(2,4),(1,0)],
[(5,3),(6,3),(8,0),(5,2),(3,0)],
[(0,1),(0,3),(0,2),(0,2),(0,0)]]
-- Álvaro Galisteo:
mayorNumeroV :: M.Matrix (Int,Int) -> Int
mayorNumeroV p = (\ (x,y) -> max x y) (m M.! (x,y))
where x = M.nrows p
y = M.ncols p
m = M.matrix x y f
mejorCamino i j = max (snd(m M.! (i, j-1))) (fst(m M.! (i-1,j)))
f (i,j) | i == 1 && j == 1 = p M.! (1,1)
| i == 1 = (\ (x,y) -> (snd(m M.! (1,j-1)) + x, snd(m M.! (1,j-1)) + y)) (p M.! (1,j))
| j == 1 = (\ (x,y) -> (fst(m M.! (i-1,1)) + x, fst(m M.! (i-1,1)) + y)) (p M.! (i,1))
| otherwise = (\ (x,y) -> ((mejorCamino i j) + x, (mejorCamino i j) + y)) (p M.! (i,j))
-- ----------------------------------------------------------------------------
-- Ejercicio 13. Una partición prima de un número natural n es un conjunto de
-- primos cuya suma es n. Por ejemplo, el número 7 tiene 3 particiones primas
-- ya que
-- 7 = 7 = 5 + 2 = 3 + 2 + 2
--
-- Definir la función
-- particiones :: Int -> Integer
-- tal que '(particiones n)' es el número de particiones primas del número
-- natural 'n', calculado mediante la técnica de programación dinámica. Por
-- ejemplo,
-- particiones 7 == 3
-- particiones 8 == 3
-- particiones 9 == 47
-- particiones 90 == 20636
-- particiones 100 == 40899
-- particiones 500 == 414270104287
-- particiones 1000 == 48278613741845757
-- ----------------------------------------------------------------------------
particiones :: Int -> Integer
particiones = undefined
primos :: Integer -> [Integer]
primos n = [x | x <- [2..n], and[mod x y /= 0| y <- [2..(x-1)]]]
-- ============================================================================
data Mat = Mat [[String]] Int
instance Show Mat where
show (Mat x m) = "/ " ++ (showRow (x !! 0) m) ++ "\\\n" ++
(showIntermediateRows x 1 m) ++
"\\ " ++ (showRow (x !! (length x - 1)) m) ++ "/"
showRow :: [String] -> Int -> String
showRow [] m = []
showRow (x:xs) m = (replicate (m - (length x)) ' ') ++ x ++ " " ++ (showRow xs m)
showIntermediateRows :: [[String]] -> Int -> Int -> String
showIntermediateRows xxs i m | i >= length xxs - 1 = []
| otherwise = "| " ++ showRow (xxs !! i) m ++ "|\n" ++
showIntermediateRows xxs (i+1) m
printMatrix :: Show a => M.Matrix a -> Mat
printMatrix m = Mat (M.toLists nm) mx
where nm = (M.mapPos (\ (i,j) e -> show e) m)
mx = maximum (map (length) (M.toList nm))
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)