Coeficientes binomiales (con programación dinámica)
El coeficiente binomial n sobre k es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.
Definir la función
|
1 |
binomial :: Integer -> Integer -> Integer |
tal que binomial n k es el coeficiente binomial n sobre k. Por ejemplo,
|
1 2 3 |
binomial 6 3 == 20 binomial 5 2 == 10 binomial 5 3 == 10 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 |
module Coeficientes_binomiales where import Data.Array (Array, (!), array) import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición (por recursión) -- ============================= binomial1 :: Integer -> Integer -> Integer binomial1 _ 0 = 1 binomial1 n k | n == k = 1 | otherwise = binomial1 (n-1) (k-1) + binomial1 (n-1) k -- 2ª definición (con programación dinámica) -- ========================================= binomial2 :: Integer -> Integer -> Integer binomial2 n k = matrizBinomial2 n k ! (n,k) -- (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el -- valor en la posición (i,j) (con j <= i) es el coeficiente binomial i -- sobre j. Por ejemplo, -- λ> [[(matrizBinomial2 3 3)!(i,j) | j <- [0..i]] | i <- [0..3]] -- [[1],[1,1],[1,2,1],[1,3,3,1]] matrizBinomial2 :: Integer -> Integer -> Array (Integer,Integer) Integer matrizBinomial2 n k = q where q = array ((0,0),(n,k)) [((i,j),f i j) | i <- [0..n], j <- [0..k]] f _ 0 = 1 f i j | i == j = 1 | otherwise = q!(i-1,j-1) + q!(i-1,j) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> binomial1 25 12 -- 5200300 -- (6.45 secs, 2,654,797,776 bytes) -- λ> binomial2 25 12 -- 5200300 -- (0.00 secs, 826,272 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ binomial1 6 3 `shouldBe` 20 it "e2" $ binomial1 5 2 `shouldBe` 10 it "e3" $ binomial1 5 3 `shouldBe` 10 it "e4" $ binomial2 6 3 `shouldBe` 20 it "e5" $ binomial2 5 2 `shouldBe` 10 it "e6" $ binomial2 5 3 `shouldBe` 10 -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- e4 -- e5 -- e6 -- -- Finished in 0.0006 seconds -- 6 examples, 0 failures |
|
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 |
from sys import setrecursionlimit from timeit import Timer, default_timer import numpy as np import numpy.typing as npt setrecursionlimit(10**6) # 1ª definición (por recursión) # ============================= def binomial1(n: int, k: int) -> int: if k == 0: return 1 if n == k: return 1 return binomial1(n-1, k-1) + binomial1(n-1, k) # 2ª definición (con programación dinámica) # ========================================= def binomial2(n: int, k: int) -> int: return matrizBinomial2(n, k)[n][k] # (matrizBinomial2 n k) es la matriz de orden (n+1)x(k+1) tal que el # valor en la posición (i,j) (con j <= i) es el coeficiente binomial i # sobre j. Por ejemplo, # >>> matrizBinomial2(3, 3) # [[1, 0, 0, 0], [1, 1, 0, 0], [1, 2, 1, 0], [1, 3, 3, 1]] def matrizBinomial2(n: int, k: int) -> list[list[int]]: q = [[0 for i in range(k + 1)] for j in range(n + 1)] for i in range(n + 1): for j in range(min(i, k) + 1): if j == 0: q[i][j] = 1 elif i == j: q[i][j] = 1 else: q[i][j] = q[i - 1][j - 1] + q[i - 1][j] return q # 3ª definición (con programación dinámica y numpy) # ================================================ def binomial3(n: int, k: int) -> int: return matrizBinomial3(n, k)[n][k] # (matrizBinomial3 n k) es la matriz de orden (n+1)x(k+1) tal que el # valor en la posición (i,j) (con j <= i) es el coeficiente binomial i # sobre j. Por ejemplo, # >>> matrizBinomial3(3, 3) # array([[1, 0, 0, 0], # [1, 1, 0, 0], # [1, 2, 1, 0], # [1, 3, 3, 1]]) def matrizBinomial3(n: int, k: int) -> npt.NDArray[np.int_]: q = np.zeros((n + 1, k + 1), dtype=object) for i in range(n + 1): for j in range(min(i, k) + 1): if j == 0: q[i, j] = 1 elif i == j: q[i, j] = 1 else: q[i, j] = q[i - 1, j - 1] + q[i - 1, j] return q # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('binomial1(27, 12)') # 4.26 segundos # >>> tiempo('binomial2(27, 12)') # 0.00 segundos # >>> tiempo('binomial3(27, 12)') # 0.00 segundos # # >>> tiempo('binomial2(50000, 12)') # 0.18 segundos # >>> tiempo('binomial3(50000, 12)') # 0.26 segundos # Verificación # ============ def test_binomial() -> None: assert binomial1(6, 3) == 20 assert binomial1(5, 2) == 10 assert binomial1(5, 3) == 10 assert binomial2(6, 3) == 20 assert binomial2(5, 2) == 10 assert binomial2(5, 3) == 10 assert binomial3(6, 3) == 20 assert binomial3(5, 2) == 10 assert binomial3(5, 3) == 10 print("Verificado") # La verificación es # >>> test_binomial() # Verificado |