José A. AlonsoUna 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. Por ejemplo,
numeroTriangulaciones 3 == 1 numeroTriangulaciones 5 == 5 numeroTriangulaciones 6 == 14 numeroTriangulaciones 7 == 42 numeroTriangulaciones 50 == 131327898242169365477991900 length (show (numeroTriangulaciones 800)) == 476 length (show (numeroTriangulaciones 1000)) == 597 length (show (numeroTriangulaciones 10000)) == 6014 |
Soluciones
import Data.Array import Data.Array (Array, (!), array) import Data.List (genericIndex) import qualified Data.Vector as V -- 1ª solución (por recursión) -- =========================== numeroTriangulaciones :: Integer -> Integer numeroTriangulaciones 2 = 1 numeroTriangulaciones n = sum (zipWith (*) ts (reverse ts)) where ts = [numeroTriangulaciones k | k <- [2..n-1]] -- 2ª solución -- =========== -- λ> map numeroTriangulaciones2 [2..15] -- [1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900] numeroTriangulaciones2 :: Integer -> Integer numeroTriangulaciones2 n = head (sucNumeroTriangulacionesInversas `genericIndex` (n-2)) -- λ> mapM_ print (take 10 sucNumeroTriangulacionesInversas) -- [1] -- [1,1] -- [2,1,1] -- [5,2,1,1] -- [14,5,2,1,1] -- [42,14,5,2,1,1] -- [132,42,14,5,2,1,1] -- [429,132,42,14,5,2,1,1] -- [1430,429,132,42,14,5,2,1,1] -- [4862,1430,429,132,42,14,5,2,1,1] sucNumeroTriangulacionesInversas :: [[Integer]] sucNumeroTriangulacionesInversas = iterate f [1] where f ts = sum (zipWith (*) ts (reverse ts)) : ts -- 3ª solución (con programación dinámica) -- ======================================= numeroTriangulaciones3 :: Integer -> Integer numeroTriangulaciones3 n = vectorTriang n ! n -- λ> vectorTriang 9 -- array (2,9) [(2,1),(3,1),(4,2),(5,5),(6,14),(7,42),(8,132),(9,429)] vectorTriang :: Integer -> Array Integer Integer vectorTriang n = v where v = array (2,n) [(i, f i) | i <-[2..n]] f 2 = 1 f i = sum [v!j*v!(i-j+1) | j <-[2..i-1]] -- 4ª solución (con los números de Catalan) -- ======================================== -- Al calcular por primeros números de triangulaciones se obtiene -- λ> map numeroTriangulaciones [2..12] -- [1,1,2,5,14,42,132,429,1430,4862,16796] -- Se observa que se corresponden con los números de Catalan -- http://bit.ly/2FOc1S1 -- -- El n-ésimo número de Catalan es -- (2n)! / (n! * (n+1)!) -- El número de triangulaciones de un polígono de n lados es el -- (n-2)-ésimo número de Catalan. numeroTriangulaciones4 :: Integer -> Integer numeroTriangulaciones4 n = numeroCatalan (n-2) numeroCatalan :: Integer -> Integer numeroCatalan n = factorial (2*n) `div` (factorial (n+1) * factorial n) factorial :: Integer -> Integer factorial n = product [1..n] -- 5ª solución -- =========== numeroTriangulaciones5 :: Integer -> Integer numeroTriangulaciones5 n = v V.! (m-2) where v = V.constructN m (\w -> if V.null w then 1 else V.sum (V.zipWith (*) w (V.reverse w))) m = fromIntegral n -- 6ª solución -- =========== numeroTriangulaciones6 :: Integer -> Integer numeroTriangulaciones6 n = nCr (2*n-4, n-2) `div` (n-1) where nCr (n,m) = factorial n `div` (factorial (n-m) * factorial m) factorial n = product [1..n] -- Comparación de eficiencia -- ========================= -- λ> numeroTriangulaciones 22 -- 6564120420 -- (3.97 secs, 668,070,936 bytes) -- λ> numeroTriangulaciones2 22 -- 6564120420 -- (0.01 secs, 180,064 bytes) -- λ> numeroTriangulaciones3 22 -- 6564120420 -- (0.01 secs, 285,792 bytes) -- -- λ> length (show (numeroTriangulaciones2 800)) -- 476 -- (0.59 secs, 125,026,824 bytes) -- λ> length (show (numeroTriangulaciones3 800)) -- 476 -- (1.95 secs, 334,652,936 bytes) -- λ> length (show (numeroTriangulaciones4 800)) -- 476 -- (0.01 secs, 2,960,088 bytes) -- λ> length (show (numeroTriangulaciones5 800)) -- 476 -- (0.65 secs, 200,415,640 bytes) -- λ> length (show (numeroTriangulaciones6 800)) -- 476 -- (0.01 secs, 2,960,224 bytes) -- -- λ> length (show (numeroTriangulaciones4 (10^4))) -- 6014 -- (1.80 secs, 542,364,320 bytes) -- λ> length (show (numeroTriangulaciones6 (10^4))) -- 6014 -- (1.87 secs, 542,351,136 bytes) |
