首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Golang实现Fibonacii的几种算法

Golang实现Fibonacii的几种算法

作者头像
李海彬
发布2018-03-20 16:37:02
7770
发布2018-03-20 16:37:02
举报
文章被收录于专栏:Golang语言社区Golang语言社区
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)
    }
}

直接递归实在太慢了,无法测试性能。

可以明显看出,直接计算,无交换的算法是最快的。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2016-03-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Golang语言社区 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档