Una triangulaci\u00f3n de un pol\u00edgono es una divisi\u00f3n del \u00e1rea en un conjunto de tri\u00e1ngulos, de forma que la uni\u00f3n de todos ellos es igual al pol\u00edgono original, y cualquier par de tri\u00e1ngulos es disjunto o comparte \u00fanicamente un v\u00e9rtice o un lado. En el caso de pol\u00edgonos convexos, la cantidad de triangulaciones posibles depende \u00fanicamente del n\u00famero de v\u00e9rtices del pol\u00edgono.<\/p>\n
Si llamamos T(n) al n\u00famero de triangulaciones de un pol\u00edgono de n v\u00e9rtices, se verifica la siguiente relaci\u00f3n de recurrencia:<\/p>\n
\n T(2) = 1\n T(n) = T(2)*T(n-1) + T(3)*T(n-2) + ... + T(n-1)*T(2)\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n numeroTriangulaciones :: Integer -> Integer\n<\/pre>\ntal que (numeroTriangulaciones n) es el n\u00famero de triangulaciones de un pol\u00edgono convexo de n v\u00e9rtices. Por ejemplo,<\/p>\n
\n numeroTriangulaciones 3 == 1\n numeroTriangulaciones 5 == 5\n numeroTriangulaciones 6 == 14\n numeroTriangulaciones 7 == 42\n numeroTriangulaciones 50 == 131327898242169365477991900\n length (show (numeroTriangulaciones 800)) == 476\n length (show (numeroTriangulaciones 1000)) == 597\n length (show (numeroTriangulaciones 10000)) == 6014\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Array (Array, (!), array)\nimport Data.List (genericIndex)\nimport qualified Data.Vector as V\n\n-- 1\u00aa soluci\u00f3n (por recursi\u00f3n)\n-- ===========================\n\nnumeroTriangulaciones :: Integer -> Integer\nnumeroTriangulaciones 2 = 1\nnumeroTriangulaciones n = sum (zipWith (*) ts (reverse ts))\n where ts = [numeroTriangulaciones k | k <- [2..n-1]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\n-- \u03bb> map numeroTriangulaciones2 [2..15]\n-- [1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900]\nnumeroTriangulaciones2 :: Integer -> Integer\nnumeroTriangulaciones2 n = \n head (sucNumeroTriangulacionesInversas `genericIndex` (n-2))\n\n-- \u03bb> mapM_ print (take 10 sucNumeroTriangulacionesInversas)\n-- [1]\n-- [1,1]\n-- [2,1,1]\n-- [5,2,1,1]\n-- [14,5,2,1,1]\n-- [42,14,5,2,1,1]\n-- [132,42,14,5,2,1,1]\n-- [429,132,42,14,5,2,1,1]\n-- [1430,429,132,42,14,5,2,1,1]\n-- [4862,1430,429,132,42,14,5,2,1,1]\nsucNumeroTriangulacionesInversas :: [[Integer]] \nsucNumeroTriangulacionesInversas = iterate f [1]\n where f ts = sum (zipWith (*) ts (reverse ts)) : ts\n\n-- 3\u00aa soluci\u00f3n (con programaci\u00f3n din\u00e1mica)\n-- =======================================\n\nnumeroTriangulaciones3 :: Integer -> Integer\nnumeroTriangulaciones3 n = vectorTriang n ! n\n\n-- \u03bb> vectorTriang 9\n-- array (2,9) [(2,1),(3,1),(4,2),(5,5),(6,14),(7,42),(8,132),(9,429)]\nvectorTriang :: Integer -> Array Integer Integer\nvectorTriang n = v\n where v = array (2,n) [(i, f i) | i <-[2..n]]\n f 2 = 1\n f i = sum [v!j*v!(i-j+1) | j <-[2..i-1]]\n\n-- 4\u00aa soluci\u00f3n (con los n\u00fameros de Catalan)\n-- ========================================\n\n-- Al calcular por primeros n\u00fameros de triangulaciones se obtiene\n-- \u03bb> map numeroTriangulaciones [2..12]\n-- [1,1,2,5,14,42,132,429,1430,4862,16796]\n-- Se observa que se corresponden con los n\u00fameros de Catalan\n-- http:\/\/bit.ly\/2FOc1S1\n-- \n-- El n-\u00e9simo n\u00famero de Catalan es\n-- (2n)! \/ (n! * (n+1)!)\n-- El n\u00famero de triangulaciones de un pol\u00edgono de n lados es el\n-- (n-2)-\u00e9simo n\u00famero de Catalan.\n\nnumeroTriangulaciones4 :: Integer -> Integer\nnumeroTriangulaciones4 n = numeroCatalan (n-2) \n\nnumeroCatalan :: Integer -> Integer\nnumeroCatalan n =\n factorial (2*n) `div` (factorial (n+1) * factorial n)\n\nfactorial :: Integer -> Integer\nfactorial n = product [1..n]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nnumeroTriangulaciones5 :: Integer -> Integer\nnumeroTriangulaciones5 n = v V.! (m-2)\n where v = V.constructN m\n (\\w -> if V.null w then 1\n else V.sum (V.zipWith (*) w (V.reverse w)))\n m = fromIntegral n\n\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nnumeroTriangulaciones6 :: Integer -> Integer\nnumeroTriangulaciones6 n = nCr (2*n-4, n-2) `div` (n-1)\n where nCr (n,m) = factorial n `div` (factorial (n-m) * factorial m)\n factorial n = product [1..n]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- \u03bb> numeroTriangulaciones 22\n-- 6564120420\n-- (3.97 secs, 668,070,936 bytes)\n-- \u03bb> numeroTriangulaciones2 22\n-- 6564120420\n-- (0.01 secs, 180,064 bytes)\n-- \u03bb> numeroTriangulaciones3 22\n-- 6564120420\n-- (0.01 secs, 285,792 bytes)\n-- \n-- \u03bb> length (show (numeroTriangulaciones2 800))\n-- 476\n-- (0.59 secs, 125,026,824 bytes)\n-- \u03bb> length (show (numeroTriangulaciones3 800))\n-- 476\n-- (1.95 secs, 334,652,936 bytes)\n-- \u03bb> length (show (numeroTriangulaciones4 800))\n-- 476\n-- (0.01 secs, 2,960,088 bytes)\n-- \u03bb> length (show (numeroTriangulaciones5 800))\n-- 476\n-- (0.65 secs, 200,415,640 bytes)\n-- \u03bb> length (show (numeroTriangulaciones6 800))\n-- 476\n-- (0.01 secs, 2,960,224 bytes)\n-- \n-- \u03bb> length (show (numeroTriangulaciones4 (10^4)))\n-- 6014\n-- (1.80 secs, 542,364,320 bytes)\n-- \u03bb> length (show (numeroTriangulaciones6 (10^4)))\n-- 6014\n-- (1.87 secs, 542,351,136 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Una triangulaci\u00f3n de un pol\u00edgono es una divisi\u00f3n del \u00e1rea en un conjunto de tri\u00e1ngulos, de forma que la uni\u00f3n de todos ellos es igual al pol\u00edgono original, y cualquier par de tri\u00e1ngulos es disjunto o comparte \u00fanicamente un v\u00e9rtice o un lado. En el caso de pol\u00edgonos convexos, la cantidad de triangulaciones posibles depende…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[250,8,286,30,256,71,50,11,157,6,32,40,76],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4041"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=4041"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4041\/revisions"}],"predecessor-version":[{"id":4074,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4041\/revisions\/4074"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4041"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4041"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4041"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}