Menu Close

Etiqueta: Dinámica

Número de sumandos en suma de cuadrados

José A. Alonso, ,

El teorema de Lagrange de los cuatro cuadrados asegura que cualquier número entero positivo es la suma de, como máximo,cuatro cuadrados de números enteros. Por ejemplo,

   16 = 4²
   29 = 2² + 5²  
   14 = 1² + 2² + 3²
   15 = 1² + 1² + 2² + 3²

Definir las funciones

   ordenLagrange        :: Integer -> Int
   graficaOrdenLagrange :: Integer -> IO ()

tales que

  • (ordenLagrange n) es el menor número de cuadrados necesarios para escribir n como suma de cuadrados. Por ejemplo.
     ordenLagrange 16     ==  1
     ordenLagrange 29     ==  2
     ordenLagrange 14     ==  3
     ordenLagrange 15     ==  4
     ordenLagrange 10000  ==  1
     ordenLagrange 10001  ==  2
     ordenLagrange 10002  ==  3
     ordenLagrange 10007  ==  4
  • (graficaOrdenLagrange n) dibuja la gráfica de los órdenes de Lagrange de los n primeros números naturales. Por ejemplo, (graficaOrdenLagrange 100) dibuja

Comprobar con QuickCheck que. para todo entero positivo k, el orden de Lagrange de k es menos o igual que 4, el de 4k+3 es distinto de 2 y el de 8k+7 es distinto de 3.

Soluciones

import Data.Array (Array, (!), array)
import Graphics.Gnuplot.Simple
 
import Test.QuickCheck
 
-- 1ª definición
-- =============
 
ordenLagrange :: Integer -> Int
ordenLagrange n
  | esCuadrado n = 1
  | otherwise    = 1 + minimum [ ordenLagrange (n - x^2)
                               | x <- [1..raizEntera n]]
 
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = (raizEntera x)^2 == x
 
-- (raizEntera n) es el mayor entero cuya raíz cuadrada es menor o igual
-- que n. Por ejemplo,
--    raizEntera 15  ==  3
--    raizEntera 16  ==  4
--    raizEntera 17  ==  4
raizEntera :: Integer -> Integer
raizEntera = floor . sqrt . fromIntegral 
 
-- 2ª definición
-- =============
 
ordenLagrange2 :: Integer -> Int
ordenLagrange2 n = (vectorOrdenLagrange n) ! n
 
vectorOrdenLagrange :: Integer -> Array Integer Int
vectorOrdenLagrange n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f i | esCuadrado i = 1
      | otherwise    = 1 + minimum [ v ! (i - j^2)
                                   | j <- [1..raizEntera i]]
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> ordenLagrange 50
--    2
--    (10.39 secs, 1,704,144,464 bytes)
--    λ> ordenLagrange2 50
--    2
--    (0.01 secs, 341,920 bytes)
 
-- Definición de graficaOrdenLagrange
-- ==================================
 
graficaOrdenLagrange :: Integer -> IO ()
graficaOrdenLagrange n = 
  plotList [ Key Nothing
           , PNG ("Numero_de_sumandos_en_suma_de_cuadrados.png")
           ]
           (map ordenLagrange2 [0..n-1])
 
-- Comprobación de la propiedad
-- ============================
 
-- La propiedad es
prop_OrdenLagrange :: Positive Integer -> Bool
prop_OrdenLagrange (Positive k) =
  ordenLagrange2 k <= 4 &&
  ordenLagrange2 (4*k+3) /= 2 &&
  ordenLagrange2 (8*k+7) /= 3
 
-- La comprobación es
--    λ> quickCheck prop_OrdenLagrange
--    +++ OK, passed 100 tests.

Pensamiento

— Nuestro español bosteza.
¿Es hambre? ¿Sueño? ¿Hastío?
Doctor, ¿tendrá el estómago vacío?
— El vacío es más bien en la cabeza.

Antonio Machado

Leer más →

Sucesión fractal

José A. Alonso, ,

La sucesión fractal

   0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 
   10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, ...

está construida de la siguiente forma:

  • los términos pares forman la sucesión de los números naturales 
     0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
  • los términos impares forman la misma sucesión original
     0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, ...

Definir las funciones

   sucFractal     :: [Integer]
   sumaSucFractal :: Integer -> Integer

tales que

  • sucFractal es la lista de los términos de la sucesión fractal. Por ejemplo, 
     take 20 sucFractal   == [0,0,1,0,2,1,3,0,4,2,5,1,6,3,7,0,8,4,9,2]
     sucFractal !! 30     == 15
     sucFractal !! (10^7) == 5000000
  • (sumaSucFractal n) es la suma de los n primeros términos de la sucesión fractal. Por ejemplo,
     sumaSucFractal 10      == 13
     sumaSucFractal (10^5)  == 1666617368
     sumaSucFractal (10^10) == 16666666661668691669
     sumaSucFractal (10^15) == 166666666666666166673722792954
     sumaSucFractal (10^20) == 1666666666666666666616666684103392376198
     length (show (sumaSucFractal (10^15000))) == 30000
     sumaSucFractal (10^15000) `mod` (10^9)    == 455972157

Soluciones

[schedule expon=’2018-06-19′ expat=»06:00″]

  • Las soluciones se pueden escribir en los comentarios hasta el 17 de mayo.
  • El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2018-06-19′ at=»06:00″]

-- 1ª definición de sucFractal
-- ===========================
 
sucFractal1 :: [Integer]
sucFractal1 = 
  map termino [0..]
 
-- (termino n) es el término n de la secuencia anterior. Por ejemplo,
--   termino 0            ==  0
--   termino 1            ==  0
--   map termino [0..10]  ==  [0,0,1,0,2,1,3,0,4,2,5]
termino :: Integer -> Integer
termino 0 = 0
termino n 
  | even n    = n `div` 2
  | otherwise = termino (n `div` 2)
 
-- 2ª definición de sucFractal
-- ===========================
 
sucFractal2 :: [Integer]
sucFractal2 =
    0 : 0 : mezcla [1..] (tail sucFractal2)
 
-- (mezcla xs ys) es la lista obtenida intercalando las listas infinitas
-- xs e ys. Por ejemplo,
--    take 10 (mezcla [0,2..] [0,-2..])  ==  [0,0,2,-2,4,-4,6,-6,8,-8]
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla (x:xs) (y:ys) =
  x : y : mezcla xs ys
 
-- Comparación de eficiencia de definiciones de sucFractal
-- =======================================================
 
--    λ> sum (take (10^6) sucFractal1)
--    166666169612
--    (5.56 secs, 842,863,264 bytes)
--    λ> sum (take (10^6) sucFractal2)
--    166666169612
--    (1.81 secs, 306,262,616 bytes)
 
-- En lo que sigue usaremos la 2ª definición
sucFractal :: [Integer]
sucFractal = sucFractal2
 
-- 1ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal1 :: Integer -> Integer
sumaSucFractal1 n =
  sum (map termino [0..n-1])
 
-- 2ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal2 :: Integer -> Integer
sumaSucFractal2 n =
    sum (take (fromIntegral n) sucFractal)
 
-- 3ª definición de sumaSucFractal
-- ===============================
 
sumaSucFractal3 :: Integer -> Integer
sumaSucFractal3 0 = 0
sumaSucFractal3 1 = 0
sumaSucFractal3 n
  | even n    = sumaN (n `div` 2) + sumaSucFractal3 (n `div` 2)
  | otherwise = sumaN ((n+1) `div` 2) + sumaSucFractal3 (n `div` 2)
  where sumaN n = (n*(n-1)) `div` 2
 
-- Comparación de eficiencia de definiciones de sumaSucFractal
-- ===========================================================
 
--    λ> sumaSucFractal1 (10^6)
--    166666169612
--    (5.25 secs, 810,622,504 bytes)
--    λ> sumaSucFractal2 (10^6)
--    166666169612
--    (1.72 secs, 286,444,048 bytes)
--    λ> sumaSucFractal3 (10^6)
--    166666169612
--    (0.01 secs, 0 bytes)
--    
--    λ> sumaSucFractal2 (10^7)
--    16666661685034
--    (17.49 secs, 3,021,580,920 bytes)
--    λ> sumaSucFractal3 (10^7)
--    16666661685034
--    (0.01 secs, 0 bytes)

Referencia

+ [Fractal sequences and restricted Nim](http://bit.ly/1WX1IjB) por Lionel Levine.
[/schedule]

Leer más →

Descomposiciones de N como sumas de 1, 3 ó 4.

José A. Alonso, ,

El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:

   5 = 1 + 1 + 1 + 1 + 1
   5 = 1 + 1 + 3
   5 = 1 + 3 + 1
   5 = 3 + 1 + 1
   5 = 1 + 4
   5 = 4 + 1

Definir las funciones

   descomposiciones  :: Integer -> [[Integer]]
   nDescomposiciones :: Integer -> Integer

tales que

  • (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
      λ> descomposiciones1 4
      [[4],[3,1],[1,3],[1,1,1,1]]
      λ> descomposiciones1 5
      [[4,1],[1,4],[3,1,1],[1,3,1],[1,1,3],[1,1,1,1,1]]
      λ> descomposiciones1 6
      [[3,3],[4,1,1],[1,4,1],[1,1,4],[3,1,1,1],[1,3,1,1],[1,1,3,1],
       [1,1,1,3],[1,1,1,1,1,1]]
  • (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
     nDescomposiciones 5                       ==  6
     nDescomposiciones 10                      ==  64
     nDescomposiciones 20                      ==  7921
     nDescomposiciones 30                      ==  974169
     length (show (nDescomposiciones (10^5)))  ==  20899

Nota: Se puede usar programación dinámica.

Soluciones

import Data.List (genericLength)
import Data.Array
 
-- 1ª definición de descomposiciones (espacios de estado)
-- ======================================================
 
descomposiciones1 :: Integer -> [[Integer]]
descomposiciones1 n = busca [inicial]
  where
    busca []        = []
    busca (e:es)  
      | esFinal n e = e : busca es
      | otherwise   = busca (es ++ sucesores n e)
 
-- Un estado es la lista de monedas usadas hasta ahora.
type Estado = [Integer] 
 
-- inicial es el estado inicial del problema; es decir, cuando no se
-- ha usado ninguna moneda.
inicial :: Estado
inicial = []
 
-- (esFinal n e) es verifica si e es un estado final del problema n. Por
-- ejemplo, 
--    esFinal (8,5,3) (4,4,0)  ==  True
--    esFinal (8,5,3) (4,0,4)  ==  False
esFinal :: Integer -> Estado -> Bool
esFinal n xs = sum xs == n
 
-- (sucesores n e) es la lista de los sucesores del estado e en el
-- problema n. Por ejemplo, 
--    sucesores (8,5,3) (8,0,0)  ==  [(3,5,0),(5,0,3)]
--    sucesores (8,5,3) (3,5,0)  ==  [(0,5,3),(8,0,0),(3,2,3)]
sucesores :: Integer -> Estado -> [Estado]
sucesores n xs =
     [1:xs | 1 + k <= n]
  ++ [3:xs | 3 + k <= n]
  ++ [4:xs | 4 + k <= n]
  where k = sum xs
 
-- 2ª definición de descomposiciones (espacios de estado)
-- ======================================================
 
descomposiciones2 :: Integer -> [[Integer]]
descomposiciones2 n = busca [inicial2 n]
  where
    busca []       = []
    busca (e:es)  
      | esFinal2 e = snd e : busca es
      | otherwise  = busca (es ++ sucesores2 n e)
 
-- Un estado es una par formado por la cantidad a conseguir y la lista
-- de monedas usadas hasta ahora.
type Estado2 = (Integer,[Integer]) 
 
-- (inicial2 n) es el estado inicial del problema; es decir, cuando no se
-- ha usado ninguna moneda.
inicial2 :: Integer -> Estado2
inicial2 n = (n,[])
 
-- (esFinal2 e) es verifica si e es un estado final del problema. Por
-- ejemplo, 
--    esFinal (8,5,3) (4,4,0)  ==  True
--    esFinal (8,5,3) (4,0,4)  ==  False
esFinal2 :: Estado2 -> Bool
esFinal2 (k,_) = k == 0
 
-- (sucesores2 n e) es la lista de los sucesores del estado e en el
-- problema n. Por ejemplo, 
--    sucesores (8,5,3) (8,0,0)  ==  [(3,5,0),(5,0,3)]
--    sucesores (8,5,3) (3,5,0)  ==  [(0,5,3),(8,0,0),(3,2,3)]
sucesores2 :: Integer -> Estado2 -> [Estado2]
sucesores2 n (k,xs) =
     [(k-1, 1:xs) | k >= 1]
  ++ [(k-3, 3:xs) | k >= 3]
  ++ [(k-4, 4:xs) | k >= 4]
 
-- 3ª definición de descomposiciones
-- =================================
 
descomposiciones3 :: Integer -> [[Integer]]
descomposiciones3 0 = [[]]
descomposiciones3 1 = [[1]]
descomposiciones3 2 = [[1,1]]
descomposiciones3 3 = [[1,1,1],[3]]
descomposiciones3 n =
     [1:xs | xs <- descomposiciones3 (n-1)]
  ++ [3:xs | xs <- descomposiciones3 (n-3)]
  ++ [4:xs | xs <- descomposiciones3 (n-4)]  
 
-- 4ª definición de descomposiciones (dinámica)
-- ============================================
 
descomposiciones4 :: Integer -> [[Integer]]
descomposiciones4 n = v!n
  where v = array (0,n) [(i,aux v i) | i <- [0..n]] 
        aux v 0 = [[]]
        aux v 1 = [[1]]
        aux v 2 = [[1,1]]
        aux v 3 = [[1,1,1],[3]]
        aux v k =    map (1:) (v!(k-1))
                  ++ map (3:) (v!(k-3))
                  ++ map (4:) (v!(k-4))
 
-- 1ª definición de nDescomposiciones
-- ==================================
 
nDescomposiciones1 :: Integer -> Integer
nDescomposiciones1 =
  genericLength . descomposiciones1
 
-- 2ª definición de nDescomposiciones
-- ==================================
 
nDescomposiciones2 :: Integer -> Integer
nDescomposiciones2 =
  genericLength . descomposiciones2
 
-- 3ª definición de nDescomposiciones
-- ==================================
 
nDescomposiciones3 :: Integer -> Integer
nDescomposiciones3 =
  genericLength . descomposiciones3
 
-- 4ª definición de nDescomposiciones
-- ==================================
 
nDescomposiciones4 :: Integer -> Integer
nDescomposiciones4 =
  genericLength . descomposiciones4
 
-- 5ª definición de nDescomposiciones (dinámica)
-- =============================================
 
nDescomposiciones5 :: Integer -> Integer
nDescomposiciones5 n = v!n
  where v = array (0,n) [(i,aux v i) | i <- [0..n]] 
        aux v 0 = 1
        aux v 1 = 1
        aux v 2 = 1
        aux v 3 = 2
        aux v k = v!(k-1) + v!(k-3) + v!(k-4)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> nDescomposiciones1 20
--    7921
--    (3.21 secs, 3,199,383,064 bytes)
--    λ> nDescomposiciones2 20
--    7921
--    (3.17 secs, 3,176,666,880 bytes)
--    λ> nDescomposiciones3 20
--    7921
--    (0.08 secs, 17,714,152 bytes)
--    
--    λ> nDescomposiciones3 27
--    229970
--    (3.73 secs, 628,730,968 bytes)
--    λ> nDescomposiciones4 27
--    229970
--    (0.45 secs, 111,518,016 bytes)
--    
--    λ> nDescomposiciones4 30
--    974169
--    (2.02 secs, 454,484,992 bytes)
--    λ> nDescomposiciones5 30
--    974169
--    (0.00 secs, 0 bytes)
 
--    λ> nDescomposiciones2 30
--    974169
--    (2.10 secs, 441,965,208 bytes)
--    λ> nDescomposiciones3 30
--    974169
--    (0.00 secs, 0 bytes)
--    
--    λ> length (show (nDescomposiciones5 (10^5)))
--    20899
--    (3.00 secs, 1,050,991,880 bytes)
Leer más →

Mayor número de atracciones visitables

José A. Alonso, ,

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 izquierda y sale por el extremo inferior derecha. 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 al 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 matriz siguiente:

   ( (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. Por ejemplo, si se define la matriz anterior por

   ejMapa :: M.Matrix (Int,Int)
   ejMapa = 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 ejMapa                                     ==  34
   mayorNumeroV (fromLists [[(1,3),(0,0)],[(0,3),(0,0)]])  ==  4
   mayorNumeroV (fromLists [[(1,3),(6,0)],[(0,3),(0,0)]])  ==  9

Para los siguientes ejemplos se define un generador de mapas

   genMapa :: Int -> Matrix (Int,Int)
   genMapa n =
     extendTo (0,0) n n (fromList (n-1) (n-1) [(k,k+1) | k <- [1..]])

Entonces,

   mayorNumeroV (genMapa 10)  ==  962
   mayorNumeroV (genMapa 500)  ==  185880992

Soluciones

import Data.Matrix
 
ejMapa :: Matrix (Int,Int)
ejMapa = 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)]]
 
genMapa :: Int -> Matrix (Int,Int)
genMapa n =
  extendTo (0,0) n n (fromList (n-1) (n-1) [(k,k+1) | k <- [1..]])
 
-- 1ª definición (por recursión)
-- =============================
 
mayorNumeroV1 :: Matrix (Int,Int) -> Int
mayorNumeroV1 p = aux m n
  where m = nrows p
        n = ncols p
        aux 1 1 = 0
        aux 1 j = sum [snd (p !(1,k)) | k <- [1..j-1]]
        aux i 1 = sum [fst (p !(k,1)) | k <- [1..i-1]]
        aux i j = max ((aux (i-1) j) + fst (p !(i-1,j)))
                      ((aux i (j-1)) + snd (p !(i,j-1)))
 
-- 2ª solución (con programación dinámica)
-- =======================================
 
mayorNumeroV2 :: Matrix (Int,Int) -> Int
mayorNumeroV2 p = (matrizNumeroV p) ! (m,n)
  where m = nrows p
        n = ncols p
 
matrizNumeroV :: Matrix (Int,Int) -> Matrix Int
matrizNumeroV p = q
  where m = nrows p
        n = ncols p
        q = matrix m n f
        f (1,1) = 0
        f (1,j) = snd (p!(1,j-1)) + q!(1,j-1)
        f (i,1) = fst (p!(i-1,1)) + q!(i-1,1)
        f (i,j) = max (fst (p!(i-1,j)) + q!(i-1,j))
                      (snd (p!(i,j-1)) + q!(i,j-1))
 
-- 3ª solución (con programación dinámica)
-- =======================================
 
mayorNumeroV3 :: Matrix (Int, Int) -> Int
mayorNumeroV3 mapa = m ! (1,1)
  where m = matrix r c f
        r = nrows mapa
        c = ncols mapa
        f (i,j) | i == r && j == c = 0
                | i == r           = e + m !(r,j+1)
                | j == c           = s + m !(i+1,c)
                | otherwise        = max (e + m !(i, j+1)) (s + m !(i+1, j))
          where (s,e) = mapa ! (i,j)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> mayorNumeroV1 (genMapa 11)
--    1334
--    (2.07 secs, 352,208,752 bytes)
--    λ> mayorNumeroV2 (genMapa 11)
--    1334
--    (0.01 secs, 319,792 bytes)
--    λ> mayorNumeroV3 (genMapa 11)
--    1334
--    (0.01 secs, 299,936 bytes)
--    
--    λ> mayorNumeroV2 (genMapa 500)
--    185880992
--    (2.26 secs, 374,557,416 bytes)
--    λ> mayorNumeroV3 (genMapa 500)
--    185880992
--    (3.15 secs, 401,098,336 bytes)
Leer más →

Número de triangulaciones de un polígono

José A. Alonso, ,

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. 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 (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)
Leer más →