Números de Pentanacci
Los números de Fibonacci se definen mediante las ecuaciones
|
1 2 3 |
F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2), si n > 1 |
Los primeros números de Fibonacci son
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
Una generalización de los anteriores son los números de Pentanacci definidos por las siguientes ecuaciones
|
1 2 3 4 5 6 |
P(0) = 0 P(1) = 1 P(2) = 1 P(3) = 2 P(4) = 4 P(n) = P(n-1) + P(n-2) + P(n-3) + P(n-4) + P(n-5), si n > 4 |
Los primeros números de Pentanacci son
|
1 |
0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ... |
Definir las funciones
|
1 2 |
pentanacci :: Integer -> Integer pentanaccis :: [Integer] |
tales que
pentanacci nes eln-ésimo número de Pentanacci. Por ejemplo,
|
1 2 3 4 5 6 |
λ> pentanacci 14 3525 λ> pentanacci (10^5) `mod` 10^30 482929150584077921552549215816 λ> length (show (pentanacci (10^5))) 29357 |
pentanaccises la lista de los números de Pentanacci. Por ejemplo,
|
1 2 |
λ> take 15 pentanacci [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] |
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 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 |
module Numeros_de_Pentanacci where import Data.List (genericIndex, zipWith5) import Test.Hspec (Spec, hspec, it, shouldBe) import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs) -- 1ª solución -- =========== pentanacci1 :: Integer -> Integer pentanacci1 0 = 0 pentanacci1 1 = 1 pentanacci1 2 = 1 pentanacci1 3 = 2 pentanacci1 4 = 4 pentanacci1 n = sum [pentanacci1 (n-k) | k <- [1..5]] pentanaccis1 :: [Integer] pentanaccis1 = [pentanacci1 n | n <- [0..]] -- 2ª solución -- =========== pentanaccis2 :: [Integer] pentanaccis2 = 0 : 1 : 1 : 2 : 4 : zipWith5 f (r 0) (r 1) (r 2) (r 3) (r 4) where f a b c d e = a+b+c+d+e r n = drop n pentanaccis2 pentanacci2 :: Integer -> Integer pentanacci2 n = pentanaccis2 `genericIndex` n -- 3ª solución -- =========== pentanaccis3 :: [Integer] pentanaccis3 = p (0, 1, 1, 2, 4) where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e) pentanacci3 :: Integer -> Integer pentanacci3 n = pentanaccis3 `genericIndex` n -- 4ª solución -- =========== pentanaccis4 :: [Integer] pentanaccis4 = 0: 1: 1: 2: 4: p pentanaccis4 where p (a:b:c:d:e:xs) = (a+b+c+d+e): p (b:c:d:e:xs) pentanacci4 :: Integer -> Integer pentanacci4 n = pentanaccis4 `genericIndex` n -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "ej1" $ take 15 pentanaccis1 `shouldBe` [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] it "ej2" $ take 15 pentanaccis2 `shouldBe` [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] it "ej3" $ take 15 pentanaccis3 `shouldBe` [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] it "ej4" $ take 15 pentanaccis4 `shouldBe` [0,1,1,2,4,8,16,31,61,120,236,464,912,1793,3525] -- La verificación es -- λ> verifica -- -- 4 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_pentanaccis :: NonNegative Int -> Bool prop_pentanaccis (NonNegative n) = all (== pentanaccis1 !! n) [pentanaccis1 !! n, pentanaccis2 !! n, pentanaccis3 !! n] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=25}) prop_pentanaccis -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> pentanacci1 25 -- 5976577 -- (4.64 secs, 1,865,626,496 bytes) -- λ> pentanacci2 25 -- 5976577 -- (0.00 secs, 578,584 bytes) -- -- λ> length (show (pentanacci2 (10^5))) -- 29357 -- (1.16 secs, 2,543,272,136 bytes) -- λ> length (show (pentanacci3 (10^5))) -- 29357 -- (1.00 secs, 2,560,881,608 bytes) -- λ> length (show (pentanacci4 (10^5))) -- 29357 -- (1.03 secs, 2,592,078,744 bytes) |
|
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 |
from itertools import count, islice from sys import set_int_max_str_digits from timeit import Timer, default_timer from typing import Iterator set_int_max_str_digits(30000) # 1ª solución # =========== def pentanacci1(n: int) -> int: if n == 0: return 0 if n == 1: return 1 if n == 2: return 1 if n == 3: return 2 if n == 4: return 4 return sum((pentanacci1(n-k) for k in range(1, 6))) def pentanaccis1() -> Iterator[int]: return (pentanacci1(n) for n in count()) # 2ª solución # =========== def pentanaccis2() -> Iterator[int]: seq = [0, 1, 1, 2, 4] while True: yield seq[0] seq.append(sum(seq)) seq.pop(0) def nth(i: Iterator[int], n: int) -> int: return list(islice(i, n, n+1))[0] def pentanacci2(n: int) -> int: return nth(pentanaccis2(), n) # Verificación # ============ def test_pentanacci() -> None: assert pentanacci1(14) == 3525 assert list(islice(pentanaccis1(), 15)) == \ [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525] assert pentanacci2(14) == 3525 assert list(islice(pentanaccis2(), 15)) == \ [0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525] print("Verificado") # La verificación es # >>> test_pentanacci() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es def test_pentanacci_equiv() -> bool: return list(islice(pentanaccis1(), 25)) == list(islice(pentanaccis2(), 25)) # La comprobación es # >>> test_pentanacci_equiv() # True # Comparación de eficiencia # ========================= # 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('pentanacci1(28)') # 8.24 segundos # >>> tiempo('pentanacci2(28)') # 0.00 segundos |