Descomposiciones triangulares
Los números triangulares se forman como sigue
|
1 2 3 4 |
* * * * * * * * * * 1 3 6 |
La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son
|
1 2 3 4 5 |
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5 |
Definir la función
|
1 |
descomposicionesTriangulares :: Int -> [(Int, Int, Int)] |
tal que descomposicionesTriangulares n es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos, como máximo, formados por números triangulares. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
λ> descomposicionesTriangulares 4 [] λ> descomposicionesTriangulares 5 [(1,1,3)] λ> descomposicionesTriangulares 12 [(1,1,10),(3,3,6)] λ> descomposicionesTriangulares 30 [(1,1,28),(3,6,21),(10,10,10)] λ> descomposicionesTriangulares 61 [(1,15,45),(3,3,55),(6,10,45),(10,15,36)] λ> descomposicionesTriangulares 52 [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)] λ> descomposicionesTriangulares 82 [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)] λ> length (descomposicionesTriangulares (5*10^5)) 124 |
1. Soluciones en Haskell
|
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 130 131 132 133 134 |
import Test.Hspec (Spec, describe, hspec, it, shouldBe) import Test.QuickCheck -- 1ª solución -- =========== descomposicionesTriangulares1 :: Int -> [(Int, Int, Int)] descomposicionesTriangulares1 n = [(x,y,z) | x <- xs, y <- xs, z <- xs, x <= y && y <= z, x + y + z == n] where xs = takeWhile (<=n) triangulares -- triangulares es la lista de los números triangulares. Por ejemplo, -- take 9 triangulares == [1,3,6,10,15,21,28,36,45] triangulares :: [Int] triangulares = scanl (+) 1 [2..] -- 2ª solución -- =========== descomposicionesTriangulares2 :: Int -> [(Int, Int, Int)] descomposicionesTriangulares2 n = [(x,y,z) | x <- xs, y <- xs, x <= y, z <- xs, y <= z, x + y + z == n] where xs = takeWhile (<=n) triangulares -- 3ª solución -- =========== descomposicionesTriangulares3 :: Int -> [(Int, Int, Int)] descomposicionesTriangulares3 n = [(x,y,z) | x <- xs, y <- xs, x <= y, let z = n - x - y, y <= z, z `elem` xs] where xs = takeWhile (<=n) triangulares -- 4ª solución -- =========== descomposicionesTriangulares4 :: Int -> [(Int, Int, Int)] descomposicionesTriangulares4 n = [(x,y,n-x-y) | x <- xs, y <- dropWhile (<x) xs, let z = n - x - y, y <= z, z `elem` xs] where xs = takeWhile (<=n) triangulares -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Int -> [(Int, Int, Int)]) -> Spec specG descomposicionesTriangulares = do it "e1" $ descomposicionesTriangulares 4 `shouldBe` [] it "e2" $ descomposicionesTriangulares 5 `shouldBe` [(1,1,3)] it "e3" $ descomposicionesTriangulares 12 `shouldBe` [(1,1,10),(3,3,6)] it "e4" $ descomposicionesTriangulares 30 `shouldBe` [(1,1,28),(3,6,21),(10,10,10)] it "e5" $ descomposicionesTriangulares 61 `shouldBe` [(1,15,45),(3,3,55),(6,10,45),(10,15,36)] it "e6" $ descomposicionesTriangulares 52 `shouldBe` [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)] it "e7" $ descomposicionesTriangulares 82 `shouldBe` [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)] spec :: Spec spec = do describe "def. 1" $ specG descomposicionesTriangulares1 describe "def. 2" $ specG descomposicionesTriangulares2 describe "def. 3" $ specG descomposicionesTriangulares3 describe "def. 4" $ specG descomposicionesTriangulares4 -- La verificación es -- λ> verifica -- 28 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_descomposicionesTriangulares_equiv :: Positive Int -> Bool prop_descomposicionesTriangulares_equiv (Positive n) = all (== descomposicionesTriangulares1 n) [descomposicionesTriangulares2 n, descomposicionesTriangulares3 n, descomposicionesTriangulares4 n] -- La comprobación es -- λ> quickCheck prop_descomposicionesTriangulares_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (descomposicionesTriangulares1 (2*10^4)) -- (5671,6328,8001) -- (3.34 secs, 1,469,517,168 bytes) -- λ> last (descomposicionesTriangulares2 (2*10^4)) -- (5671,6328,8001) -- (1.29 secs, 461,433,928 bytes) -- λ> last (descomposicionesTriangulares3 (2*10^4)) -- (5671,6328,8001) -- (0.08 secs, 6,574,056 bytes) -- -- λ> last (descomposicionesTriangulares3 (5*10^5)) -- (140185,148240,211575) -- (2.12 secs, 151,137,280 bytes) -- λ> last (descomposicionesTriangulares4 (5*10^5)) -- (140185,148240,211575) -- (2.30 secs, 103,280,216 bytes) |
2. 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 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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
from itertools import count, dropwhile, takewhile from sys import setrecursionlimit from timeit import Timer, default_timer from typing import Iterator from hypothesis import given from hypothesis import strategies as st setrecursionlimit(10**6) # 1ª solución # =========== # triangular(n) es el n-ésimo número triangular. Por ejemplo, # triangular(9) == 45 def triangular(n: int) -> int: if n == 1: return 1 return triangular(n-1) + n # triangulares1() es la lista de los números triangulares. Por ejemplo, # >>> from itertools import islice # >>> list(islice(triangulares1(), 10)) # [1, 3, 6, 10, 15, 21, 28, 36, 45, 55] def triangulares1() -> Iterator[int]: return (triangular(n) for n in count(1)) def descomposicionesTriangulares1(n: int) -> list[tuple[int, int, int]]: xs = list(takewhile(lambda x : x <= n, triangulares1())) return [(x,y,z) for x in xs for y in xs for z in xs if x <= y <= z and x + y + z == n] # 2ª solución # =========== def triangulares2() -> Iterator[int]: return ((n*(n+1)) // 2 for n in count(1)) def descomposicionesTriangulares2(n: int) -> list[tuple[int, int, int]]: xs = list(takewhile(lambda x : x <= n, triangulares2())) return [(x,y,z) for x in xs for y in xs for z in xs if x <= y <= z and x + y + z == n] # 3ª solución # =========== def descomposicionesTriangulares3(n: int) -> list[tuple[int, int, int]]: xs = list(takewhile(lambda x : x <= n, triangulares2())) return [(x,y,z) for x in xs for y in xs if x <= y for z in xs if y <= z if x + y + z == n] # 4ª solución # =========== def descomposicionesTriangulares4(n: int) -> list[tuple[int, int, int]]: xs = list(takewhile(lambda x : x <= n, triangulares2())) ts = [] for x in xs: for y in xs: if x <= y: z = n - x - y if y <= z and z in xs: ts.append((x, y, z)) return ts # 5ª solución # =========== def descomposicionesTriangulares5(n: int) -> list[tuple[int, int, int]]: xs = list(takewhile(lambda a : a <= n, triangulares2())) ts = [] for x in xs: ys = list(dropwhile(lambda y: y < x, xs)) for y in ys: z = n - x - y if y <= z and z in xs: ts.append((x, y, z)) return ts # Verificación # ============ def test_descomposicionesTriangulares() -> None: for descomposicionesTriangulares in [descomposicionesTriangulares1, descomposicionesTriangulares2, descomposicionesTriangulares3, descomposicionesTriangulares4, descomposicionesTriangulares5]: assert descomposicionesTriangulares(4) ==\ [] assert descomposicionesTriangulares(5) ==\ [(1,1,3)] assert descomposicionesTriangulares(12) ==\ [(1,1,10),(3,3,6)] assert descomposicionesTriangulares(30) ==\ [(1,1,28),(3,6,21),(10,10,10)] assert descomposicionesTriangulares(61) ==\ [(1,15,45),(3,3,55),(6,10,45),(10,15,36)] assert descomposicionesTriangulares(52) ==\ [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)] assert descomposicionesTriangulares(82) ==\ [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)] print("Verificado") # La verificación es # >>> test_descomposicionesTriangulares() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_descomposicionesTriangulares_equiv(n: int) -> None: r = descomposicionesTriangulares1(n) assert descomposicionesTriangulares2(n) == r assert descomposicionesTriangulares3(n) == r assert descomposicionesTriangulares4(n) == r # La comprobación es # >>> test_descomposicionesTriangulares_equiv() # >>> # 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('descomposicionesTriangulares1(6*10**4)[-1]') # 2.16 segundos # >>> tiempo('descomposicionesTriangulares2(6*10**4)[-1]') # 2.05 segundos # >>> tiempo('descomposicionesTriangulares3(6*10**4)[-1]') # 1.04 segundos # >>> tiempo('descomposicionesTriangulares4(6*10**4)[-1]') # 0.10 segundos |