Números triangulares con n cifras distintas
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 |
triangularesConCifras :: Int -> [Integer] |
tal que triangularesConCifras n es la lista de los números triangulares con n cifras distintas. Por ejemplo,
|
1 2 3 4 5 |
take 6 (triangularesConCifras 1) == [1,3,6,55,66,666] take 6 (triangularesConCifras 2) == [10,15,21,28,36,45] take 6 (triangularesConCifras 3) == [105,120,136,153,190,210] take 5 (triangularesConCifras 4) == [1035,1275,1326,1378,1485] take 2 (triangularesConCifras 10) == [1062489753,1239845706] |
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 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
import Data.List (nub) import Test.Hspec (Spec, describe, hspec, it, shouldBe) import Test.QuickCheck -- 1ª solución -- =========== triangularesConCifras1 :: Int -> [Integer] triangularesConCifras1 n = [x | x <- triangulares1, nCifras x == n] -- triangulares1 es la lista de los números triangulares. Por ejemplo, -- take 10 triangulares1 == [1,3,6,10,15,21,28,36,45,55] triangulares1 :: [Integer] triangulares1 = map triangular [1..] triangular :: Integer -> Integer triangular 1 = 1 triangular n = triangular (n-1) + n -- (nCifras x) es el número de cifras distintas del número x. Por -- ejemplo, -- nCifras 325275 == 4 nCifras :: Integer -> Int nCifras = length . nub . show -- 2ª solución -- =========== triangularesConCifras2 :: Int -> [Integer] triangularesConCifras2 n = [x | x <- triangulares2, nCifras x == n] triangulares2 :: [Integer] triangulares2 = [(n*(n+1)) `div` 2 | n <- [1..]] -- 3ª solución -- =========== triangularesConCifras3 :: Int -> [Integer] triangularesConCifras3 n = [x | x <- triangulares3, nCifras x == n] triangulares3 :: [Integer] triangulares3 = 1 : [x+y | (x,y) <- zip [2..] triangulares3] -- 4ª solución -- =========== triangularesConCifras4 :: Int -> [Integer] triangularesConCifras4 n = [x | x <- triangulares4, nCifras x == n] triangulares4 :: [Integer] triangulares4 = 1 : zipWith (+) [2..] triangulares4 -- 5ª solución -- =========== triangularesConCifras5 :: Int -> [Integer] triangularesConCifras5 n = [x | x <- triangulares5, nCifras x == n] triangulares5 :: [Integer] triangulares5 = scanl (+) 1 [2..] -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Int -> [Integer]) -> Spec specG triangularesConCifras = do it "e1" $ take 6 (triangularesConCifras 1) `shouldBe` [1,3,6,55,66,666] it "e2" $ take 6 (triangularesConCifras 2) `shouldBe` [10,15,21,28,36,45] it "e3" $ take 6 (triangularesConCifras 3) `shouldBe` [105,120,136,153,190,210] it "e4" $ take 5 (triangularesConCifras 4) `shouldBe` [1035,1275,1326,1378,1485] spec :: Spec spec = do describe "def. 1" $ specG triangularesConCifras1 describe "def. 2" $ specG triangularesConCifras2 describe "def. 3" $ specG triangularesConCifras3 describe "def. 4" $ specG triangularesConCifras4 describe "def. 5" $ specG triangularesConCifras5 -- La verificación es -- λ> verifica -- 20 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La 1ª propiedad es prop_triangularesConCifras1 :: Bool prop_triangularesConCifras1 = [take 2 (triangularesConCifras1 n) | n <- [1..7]] == [take 2 (triangularesConCifras2 n) | n <- [1..7]] -- La comprobación es -- λ> prop_triangularesConCifras1 -- True -- La 2ª propiedad es prop_triangularesConCifras2 :: Int -> Bool prop_triangularesConCifras2 n = all (== take 5 (triangularesConCifras2 n')) [take 5 (triangularesConCifras3 n'), take 5 (triangularesConCifras4 n'), take 5 (triangularesConCifras5 n')] where n' = 1 + n `mod` 9 -- La comprobación es -- λ> quickCheck prop_triangularesConCifras -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> (triangularesConCifras1 3) !! 220 -- 5456556 -- (2.48 secs, 1,228,690,120 bytes) -- λ> (triangularesConCifras2 3) !! 220 -- 5456556 -- (0.01 secs, 4,667,288 bytes) -- -- λ> (triangularesConCifras2 3) !! 600 -- 500010500055 -- (1.76 secs, 1,659,299,872 bytes) -- λ> (triangularesConCifras3 3) !! 600 -- 500010500055 -- (1.67 secs, 1,603,298,648 bytes) -- λ> (triangularesConCifras4 3) !! 600 -- 500010500055 -- (1.20 secs, 1,507,298,248 bytes) -- λ> (triangularesConCifras5 3) !! 600 -- 500010500055 -- (1.15 secs, 1,507,298,256 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 |
from itertools import count, islice from sys import setrecursionlimit from timeit import Timer, default_timer from typing import Iterator 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, # >>> 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)) # nCifras(x) es el número de cifras distintas del número x. Por # ejemplo, # nCifras(325275) == 4 def nCifras(x: int) -> int: return len(set(str(x))) def triangularesConCifras1(n: int) -> Iterator[int]: return (x for x in triangulares1() if nCifras(x) == n) # 2ª solución # =========== def triangulares2() -> Iterator[int]: return ((n*(n+1)) // 2 for n in count(1)) def triangularesConCifras2(n: int) -> Iterator[int]: return (x for x in triangulares2() if nCifras(x) == n) # 3ª solución # =========== def triangulares3() -> Iterator[int]: x = 0 for n in count(1): x += n yield x def triangularesConCifras3(n: int) -> Iterator[int]: return (x for x in triangulares3() if nCifras(x) == n) # Verificación # ============ def test_triangularesConCifras() -> None: for triangularesConCifras in [triangularesConCifras1, triangularesConCifras2, triangularesConCifras3]: assert list(islice(triangularesConCifras(1), 6)) == \ [1,3,6,55,66,666] assert list(islice(triangularesConCifras(2), 6)) == \ [10,15,21,28,36,45] assert list(islice(triangularesConCifras(3), 6)) == \ [105,120,136,153,190,210] assert list(islice(triangularesConCifras(4), 5)) == \ [1035,1275,1326,1378,1485] print("Verificado") # La verificación es # >>> test_triangularesConCifras() # Verificado # 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('list(islice(triangularesConCifras1(3), 300))') # 11.18 segundos # >>> tiempo('list(islice(triangularesConCifras2(3), 300))') # 0.03 segundos # >>> tiempo('list(islice(triangularesConCifras3(3), 300))') # 0.03 segundos # # >>> tiempo('list(islice(triangularesConCifras2(3), 700))') # 2.19 segundos # >>> tiempo('list(islice(triangularesConCifras3(3), 700))') # 2.01 segundos |