分享
golang实现Fibonacii的几种算法
wyd_npu · · 1869 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
package fib
/**
Fibonacii的几种算法实现
*/
// 直接循环计算
func Fib(n int) int {
f := [3]int{0, 1, 1}
if n < 0 {
return -1
}
if n < 3 {
return f[n]
}
for i := 3; i <= n; i++ {
f[0], f[1] = f[1], f[2]
f[2] = f[0] + f[1]
}
return f[2]
}
// 略微修改,没有任何数据中间交换哦~~
func Fib2(n int) int {
f := [2]int{0, 1}
if n < 0 {
return -1
}
if n < 2 {
return f[n]
}
for i := 2; i <= n; i++ {
f[i&1] += f[(i+1)&1]
}
return f[n&1]
}
//递归算法,效率低
func FibRec(n int) int {
if n < 0 {
return -1
}
return fib_recursion(n)
}
func fib_recursion(n int) int {
if n < 3 {
return 1
}
return fib_recursion(n-1) + fib_recursion(n-2)
}
//尾递归算法
func FibTail(n int) int {
if n < 0 {
return -1
}
if n < 3 {
return 1
}
return fib_tail_recursion(n, 1, 1, 3)
}
func fib_tail_recursion(n int, a int, b int, begin int) int {
if n == begin {
return a + b
}
return fib_tail_recursion(n, b, a+b, begin+1)
}
单元测试测试代码:package fib
import (
//"fmt"
"testing"
)
func TestFib(t *testing.T) {
n := 10
f := Fib(n)
if f != 55 {
t.Error("Fib() failed. Got", f, "Expected 55 ")
}
}
func TestFib2(t *testing.T) {
n := 10
f := Fib2(n)
if f != 55 {
t.Error("Fib2() failed. Got", f, "Expected 55 ")
}
}
func TestFibRec(t *testing.T) {
n := 10
f := FibRec(n)
if f != 55 {
t.Error("FibRec() failed. Got", f, "Expected 55 ")
}
}
func TestFibTail(t *testing.T) {
n := 10
f := FibTail(n)
if f != 55 {
t.Error("FibTail() failed. Got", f, "Expected 55")
}
}
func BenchmarkFib(b *testing.B) {
for i := 0; i < b.N; i++ {
Fib(1000)
}
}
func BenchmarkFib2(b *testing.B) {
for i := 0; i < b.N; i++ {
Fib2(1000)
}
}
func BenchmarkFibTail(b *testing.B) {
for i := 0; i < b.N; i++ {
FibTail(1000)
}
}
直接递归实在太慢了,无法测试性能。
可以明显看出,直接计算,无交换的算法是最快的。
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1869 次点击
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
package fib
/**
Fibonacii的几种算法实现
*/
// 直接循环计算
func Fib(n int) int {
f := [3]int{0, 1, 1}
if n < 0 {
return -1
}
if n < 3 {
return f[n]
}
for i := 3; i <= n; i++ {
f[0], f[1] = f[1], f[2]
f[2] = f[0] + f[1]
}
return f[2]
}
// 略微修改,没有任何数据中间交换哦~~
func Fib2(n int) int {
f := [2]int{0, 1}
if n < 0 {
return -1
}
if n < 2 {
return f[n]
}
for i := 2; i <= n; i++ {
f[i&1] += f[(i+1)&1]
}
return f[n&1]
}
//递归算法,效率低
func FibRec(n int) int {
if n < 0 {
return -1
}
return fib_recursion(n)
}
func fib_recursion(n int) int {
if n < 3 {
return 1
}
return fib_recursion(n-1) + fib_recursion(n-2)
}
//尾递归算法
func FibTail(n int) int {
if n < 0 {
return -1
}
if n < 3 {
return 1
}
return fib_tail_recursion(n, 1, 1, 3)
}
func fib_tail_recursion(n int, a int, b int, begin int) int {
if n == begin {
return a + b
}
return fib_tail_recursion(n, b, a+b, begin+1)
}
单元测试测试代码:package fib
import (
//"fmt"
"testing"
)
func TestFib(t *testing.T) {
n := 10
f := Fib(n)
if f != 55 {
t.Error("Fib() failed. Got", f, "Expected 55 ")
}
}
func TestFib2(t *testing.T) {
n := 10
f := Fib2(n)
if f != 55 {
t.Error("Fib2() failed. Got", f, "Expected 55 ")
}
}
func TestFibRec(t *testing.T) {
n := 10
f := FibRec(n)
if f != 55 {
t.Error("FibRec() failed. Got", f, "Expected 55 ")
}
}
func TestFibTail(t *testing.T) {
n := 10
f := FibTail(n)
if f != 55 {
t.Error("FibTail() failed. Got", f, "Expected 55")
}
}
func BenchmarkFib(b *testing.B) {
for i := 0; i < b.N; i++ {
Fib(1000)
}
}
func BenchmarkFib2(b *testing.B) {
for i := 0; i < b.N; i++ {
Fib2(1000)
}
}
func BenchmarkFibTail(b *testing.B) {
for i := 0; i < b.N; i++ {
FibTail(1000)
}
}
直接递归实在太慢了,无法测试性能。
可以明显看出,直接计算,无交换的算法是最快的。