网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

Go语言斐波那契数列的解法

2020-06-10 04:01:39 admin 633

### 1\. 最常见的递归

func fib(N int) int {
        if N < 2 {
            return N
        }
        return fib(N-1) + fib(N-2)
    }

这么写效率很低，没有剪枝，存在大量的重复计算。

### 2.带缓存的递归

// solution 1
    func fib(N int) int {
        if N < 2 {
            return N
        }
        fibCache := make(map[int]int) 
        fibCache[0] = 0
        fibCache[1] = 1
        for i := 2; i <= N; i++ {
            fibCache[i] = fibCache[i-1] + fibCache[i-2]
        }
        return fibCache[N]
    }
    // solution 2
    // 减少递归次数
    func fib(N int) int {
        if N < 2 {
            return N
        }
        fibCache := make(map[int]int)
        if _, ok := fibCache[N]; !ok {
            fibCache[N] = fibCache[N-1] + fibCache[N-2]
        } else {
            return fibCache[N]
        }
        return fib(N-1) + fib(N-2)
    }

### 3\. 循环法

func fib(N int) int {
        cur, next := 0, 1
        for i := 0; i < N; i++ {
            cur, next = next, cur+next
        }
        return cur
    }

### 4.打表法

func fib(N int) int {
        fibs := []int{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040}
        return fibs[N]
    }

反正你测试用例是有限的，那我骗过你的测试用例就行了啊；)

转载文章，原文链接： Go语言斐波那契数列的解法

关键字词go 斐波

分享到：

上一篇：golang 基础（18）字符串

下一篇：软件技术-零基础-VSCode同步推送Github

如需留言，请登录，没有账号？请注册

0 条评论 0 人参与

网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

Go语言斐波那契数列的解法

zhou 2年前

zhou 2年前

zhou 2年前

zhou 2年前

武云 2年前

网站首页 返回列表 像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

Go语言 斐波那契数列的解法

zhou 2年前

zhou 2年前

zhou 2年前

zhou 2年前

武云 2年前

网站首页返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

Go语言斐波那契数列的解法