-
Notifications
You must be signed in to change notification settings - Fork 0
/
Fibonacci.hs
93 lines (80 loc) · 3.17 KB
/
Fibonacci.hs
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
-- Fibonacci.hs
-- Fibonacci como ejemplo de programación dinámica.
-- José A. Alonso Jiménez https://jaalonso.github.com
-- =====================================================================
module Tema_24.Fibonacci where
import Tema_24.Dinamica
-- ---------------------------------------------------------------------
-- Fibonacci como ejemplo de programación dinámica. --
-- ---------------------------------------------------------------------
-- (fib n) es el n-ésimo término de la sucesión de Fibonacci, calculado
-- mediante programación dinámica. Por ejemplo,
-- fib 8 == 21
fib :: Int -> Int
fib n = valor t n
where t = dinamica calculaFib (cotasFib n)
-- (calculaFib t i) es el valor de i-ésimo término de la sucesión de
-- Fibonacci calculado mediante la tabla t que contiene los
-- anteriores. Por ejemplo,
-- calculaFib (tabla []) 0 == 0
-- calculaFib (tabla [(0,0)]) 1 == 1
-- calculaFib (tabla [(0,0),(1,1)]) 2 == 1
-- calculaFib (tabla [(0,0),(1,1),(2,1)]) 3 == 2
-- calculaFib (tabla [(0,0),(1,1),(2,1),(3,2)]) 4 == 3
-- calculaFib (tabla [(0,0),(1,1),(2,1),(3,2),(4,3)]) 5 == 5
-- calculaFib (tabla [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5)]) 6 == 8
-- Además,
-- λ> dinamica calculaFib (0,8)
-- Tbl [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21)]
calculaFib :: Tabla Int Int -> Int -> Int
calculaFib t i
| i <= 1 = i
| otherwise = valor t (i-1) + valor t (i-2)
-- (cotasFib n) son las cotas del vector que se necesita para calcular
-- el n-ésimo término de la sucesión de Fibonacci mediante programación
-- dinámica.
cotasFib :: Int -> (Int,Int)
cotasFib n = (0,n)
-- ---------------------------------------------------------------------
-- Fibonacci mediante divide y vencerás --
-- ---------------------------------------------------------------------
-- (fibR n) es el n-ésimo término de la sucesión de Fibonacci calculado
-- mediante divide y vencerás. Por ejemplo,
-- fibR 8 == 21
fibR :: Int -> Int
fibR 0 = 0
fibR 1 = 1
fibR n = fibR (n-1) + fibR (n-2)
-- Comparación
-- λ> fib 20
-- 6765
-- (0.01 secs, 524824 bytes)
-- λ> fibR 20
-- 6765
-- (0.06 secs, 2165236 bytes)
-- λ> fib 30
-- 832040
-- (0.01 secs, 0 bytes)
-- λ> fibR 30
-- 832040
-- (6.46 secs, 222602404 bytes)
-- ---------------------------------------------------------------------
-- Fibonacci mediante programación dinámica con listas infinitas --
-- ---------------------------------------------------------------------
-- fibs es la lista de los términos de la sucesión de Fibonacci. Por
-- ejemplo,
-- take 10 fibs == [0,1,1,2,3,5,8,13,21,34]
fibs :: [Int]
fibs = 0:1:[x+y | (x,y) <- zip fibs (tail fibs)]
-- (fib' n) es el n-ésimo término de la sucesión de Fibonacci, calculado
-- a partir de fibs. Por ejemplo,
-- fib' 8 == 21
fib' :: Int -> Int
fib' n = fibs!!n
-- Comparaciones:
-- λ> fib 30
-- 832040
-- (0.02 secs, 524808 bytes)
-- λ> fib' 30
-- 832040
-- (0.01 secs, 542384 bytes)