La función de Fibonacci por programación dinámica

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

   fib :: Integer -> Integer

   fib 6 == 8

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)

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