La función de Fibonacci por programación dinámica
Los primeros términos de la sucesión de Fibonacci son
|
1 |
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... |
Escribir dos definiciones (una recursiva y otra con programación dinámica) de la función
|
1 |
fib :: Integer -> Integer |
tal que fib n es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
|
1 |
fib 6 == 8 |
Comparar la eficiencia de las dos definiciones.
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 |
module La_funcion_de_Fibonacci_por_programacion_dinamica where import Data.Array import Test.Hspec (Spec, hspec, it, shouldBe) -- 1ª definición (por recursión) -- ============================= fib1 :: Integer -> Integer fib1 0 = 0 fib1 1 = 1 fib1 n = fib1 (n-1) + fib1 (n-2) -- 2ª definición (con programación dinámica) -- ========================================= fib2 :: Integer -> Integer fib2 n = vectorFib2 n ! n -- (vectorFib2 n) es el vector con índices de 0 a n tal que el valor -- de la posición i es el i-ésimo número de Finonacci. Por ejemplo, -- λ> vectorFib2 7 -- array (0,7) [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13)] vectorFib2 :: Integer -> Array Integer Integer vectorFib2 n = v where v = array (0,n) [(i,f i) | i <- [0..n]] f 0 = 0 f 1 = 1 f m = v!(m-1) + v!(m-2) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> fib1 34 -- 5702887 -- (11.82 secs, 3,504,944,704 bytes) -- λ> fib2 34 -- 5702887 -- (0.01 secs, 587,808 bytes) -- Verificación -- ============ verifica :: IO () verifica = hspec spec spec :: Spec spec = do it "e1" $ fib1 6 `shouldBe` 8 it "e2" $ fib2 6 `shouldBe` 8 it "e3" $ map fib1 [0..9] `shouldBe` map fib2 [0..9] -- La verificación es -- λ> verifica -- -- e1 -- e2 -- e3 -- -- Finished in 0.0007 seconds -- 3 examples, 0 failures -- (0.01 secs, 788,952 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 86 87 |
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 fib1(n: int) -> int: if n == 0: return 0 if n == 1: return 1 return fib1(n - 1) + fib1(n - 2) # 2ª definición (con programación dinámica) # ========================================= def fib2(n: int) -> int: return vectorFib2(n)[n] # (vectorFib2 n) es el vector con índices de 0 a n tal que el valor # de la posición i es el i-ésimo número de Finonacci. Por ejemplo, # >>> vectorFib2(7) # [0, 1, 1, 2, 3, 5, 8, 13] def vectorFib2(n: int) -> list[int]: v = [0] * (n + 1) v[0] = 0 v[1] = 1 for i in range(2, n + 1): v[i] = v[i - 1] + v[i - 2] return v # 2ª definición (con programación dinámica y array) # ================================================= def fib3(n: int) -> int: return vectorFib3(n)[n] # (vectorFib3 n) es el vector con índices de 0 a n tal que el valor # de la posición i es el i-ésimo número de Finonacci. Por ejemplo, # >>> vectorFib3(7) # array([ 0, 1, 1, 2, 3, 5, 8, 13]) def vectorFib3(n: int) -> npt.NDArray[np.complex64]: v = np.zeros(n + 1, dtype=int) v[0] = 0 v[1] = 1 for i in range(2, n + 1): v[i] = v[i - 1] + v[i - 2] return v # 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('fib1(34)') # 2.10 segundos # >>> tiempo('fib2(34)') # 0.00 segundos # >>> tiempo('fib3(34)') # 0.00 segundos # # >>> tiempo('fib2(100000)') # 0.37 segundos # >>> tiempo('fib3(100000)') # 0.08 segundos # Verificación # ============ def test_fib() -> None: assert fib1(6) == 8 assert fib2(6) == 8 assert fib3(6) == 8 print("Verificado") # La verificación es # >>> test_fib() # Verificado |