はじめに
直近Go言語を勉強していますが、なんか数学問題を解けてみまたいため、フィボナッチ数を計算できるロジックを作成しました。
環境
window 10
VSCode
Target
以下の結果を出力する
フィボナッチ数：(0,1,1,2,3,5...)
簡単に回帰関数を利用して、作りました。
package.go
package main
import "fmt"
func fibonacci() func(x int) int {
return func(x int) int {
if x < 2 {
return x
}
f := fibonacci()
return f(x-2) + f(x-1)
}
}
func main() {
f := fibonacci()
for i := 0; i < 10; i++ {
fmt.Println(f(i))
}
}
実行結果：
0
1
1
2
3
5
8
13
21
34
結果ができましたね。しかし、計算量が
O(2^n)
だった。
根本的になおしました。
package.go
package main
import "fmt"
func fibonacci() func(x int) int {
return func(x int) int {
a, b:= x%2, 1
for i := 0;i < x/2; i++{
a += b
b += a
}
return a
}
}
func main() {
f := fibonacci()
for i := 0; i < 10; i++ {
fmt.Println(f(i))
}
}
これで良さそうですね。
計算量が
O(n)
になりました。良さそうですね。