algorithms/fibo.go at main · simon-epfl/algorithms · GitHub

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
package main

/*
➜  algo git:(main) ✗ go build -o algo && ./algo fibo
Fibonacci de 40 : 165580141
Exec: 468230 µs
➜  algo git:(main) ✗ go build -o algo && ./algo fibotop
Fibonacci de 40 : 165580141
Exec: 10 µs
➜  algo git:(main) ✗ go build -o algo && ./algo fibodown
Unknown algorithm
Exec: 6 µs
*/

func dumbFibo(n int) int {

	if n == 0 || n == 1 {
		return 1
	}

	return dumbFibo(n-1) + dumbFibo(n-2)
}

func fiboBottomUp(n int) int {

	cache := make([]int, n+1)

	cache[0] = 1
	cache[1] = 1

	if n < 2 {
		return cache[n]
	}

	for i := 2; i <= n; i++ {
		cache[i] = cache[i-1] + cache[i-2]
	}

	return cache[n]

}

func fiboTopDown(n int, cache []int) int {

	if cache[n] > -9999 {
		return cache[n]
	}

	if n < 2 {
		cache[0] = 1
		cache[1] = 1
		return 1
	}

	res := fiboTopDown(n-1, cache) + fiboTopDown(n-2, cache)

	cache[n] = res

	return res

}

func runFiboTopdown() {
	n := 40
	cache := make([]int, n+1)
	for i := range cache {
		cache[i] = -9999
	}

	result := fiboTopDown(n, cache)
	println("Fibonacci de", n, ":", result)
}

func runFiboBottomup() {
	n := 40

	result := fiboBottomUp(n)
	println("Fibonacci de", n, ":", result)
}

func runDumbfibo() {
	n := 40

	result := dumbFibo(n)
	println("Fibonacci de", n, ":", result)
}