Número de triangulaciones de un polígono
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:
|
1 2 |
T(2) = 1 T(n) = T(2)*T(n-1) + T(3)*T(n-2) + ... + T(n-1)*T(2) |
Definir la función
|
1 |
numeroTriangulaciones :: Integer -> Integer |
tal que (numeroTriangulaciones n) es el número de triangulaciones de un polígono convexo de n vértices. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
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
[schedule expon=’2019-06-05′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 05 de junio.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
No es la belleza el gran incentivo del amor, sino la sed metafísica de lo esencialmente otro.
Antonio Machado
[/schedule]
[schedule on=’2019-06-05′ at=»06:00″]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
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) |
[/schedule]
Me gustaria sabeer si hay una formula matematica para calcular el numero de triangulos formados en un poligono por sus lados y diagonales , que no fuese con programacion. Gracias. La programacion no la domino, lo siento.
Sí, es la que se usa en la 4ª solución
Gracias por la respuesta. Pero he hecho pruebas y no consigo los 110 de un hexagono 0 los 287 de un heptagono. Podrias detallare la operacion con un ejemplo numerico ?? Perdona las molestias . Gracias.