Go 中的斐波那契闭合

Question

我正在关注他们官方网站上的 gotour，并被要求编写一个斐波那契生成器。在这里：

 package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    first := 0
    second := 0
    return func() int{
        if(first == 0) {
         first = 1
         second = 1
         return 0
        }else {
            current := first   
            firstc := second
            second = first + second
            first = firstc
            return current
        }



    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

它有效。然而我认为它非常丑陋，我确信必须有更好的解决方案。我一直在考虑将其发布在代码审查中，但是因为我要求更好的方法，所以我认为这是发布它的正确位置。

有更好的方法来编写这段代码吗？

这是任务：

实现一个斐波那契函数，该函数返回一个返回连续斐波那契数的函数（闭包）。

Answer 1

我最喜欢的实现斐波那契数列迭代的干净方法是使用

first

作为 f_{i - 1}，使用

second

作为 f_i。斐波那契方程指出：

f_{i + 1} = f_i + f_{i - 1}

除非我们在代码中编写此内容，否则在下一轮中我们将递增

。所以我们正在有效地做：

f_{下一个 i} = f_{当前 i} + f_{当前 i - 1}

和

f_{下一个 i - 1} = f_{当前 i}

我喜欢在代码中实现这一点的方式是：

first, second = second, first + second

first = second

部分对应更新f_{next i - 1} = f_{current i}，

second = first + second

部分对应更新f_{next i} = f_{current i} + f_{current i - 1}.

然后我们剩下要做的就是返回first的旧值，所以我们在更新之前将其存储在一个临时变量中。总共，我们得到：

// fibonacci returns a function that returns
// successive fibonacci numbers from each
// successive call
func fibonacci() func() int {
    first, second := 0, 1
    return func() int {
        ret := first
        first, second = second, first+second
        return ret
    }
}

在 Go Playground 上查看它的实际应用。

Answer 2

一个小技巧

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    a := 0
    b := 1
    return func() int {
        a, b = b, a+b
        return b-a
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

Answer 3

另一种方法

func fibonacci() func() int {
    n1, n := -1, 1
    return func() int {
        n1, n = n, n1+n
        return n
    }
}

围棋游乐场

Answer 4

我会利用多重赋值，减少标识符的长度，并删除 if 语句：

func fibonacci() func() int {
    var a, b int
    b = 1
    return func() int {
        ret := a
        a, b = b, a+b
        return ret
    }
}

Answer 5

我就是这样做的。

func fibonacci() func() int {
     var s = []int{0,1}

     return func() int{
                ret := s[0]
                s[0],s[1] = s[1],s[0]+s[1]
                return ret
            }
}

Answer 6

这也是我的建议，将每个数字存储在地图中。

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an 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
func fibonacci() func() int {
    numbers := make(map[int]int)
    n := 0
    return func() int {
        if n == 0 {
            numbers[n] = 0
            n++
            return 0
        }
        if n == 1 {
            numbers[n] = 1
            n++
            return 1
        }
        number := numbers[n-1] + numbers[n-2]
        numbers[n] = number
        n++
        return number
    }}

func main() {
    f := fibonacci()
    for i := 0; i < 30; i++ {
        fmt.Println(f())
    }
}

Answer 7

除了已经提供的答案之外，您还可以使用延迟函数：

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    secondLast := 0
    last := 1
    return func() int {
        defer func() {
            secondLast, last = last, secondLast+last
        }()
        return secondLast
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

去游乐场

但我猜 jwoodalls 的答案是最高效的。

编辑：但是，如果您想使用无符号整数（以展示您可以在架构上计算多少个斐波那契数；）），您将必须使用保存返回值的变量的方法或 defer 函数。

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an uint.
func fibonacci() func() uint {
    var secondLast uint
    var last uint = 1
    return func() uint {
        defer func() {
            secondLast, last = last, secondLast + last
        }()
        return secondLast
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

去游乐场

编辑编辑：或者更好：使用 float64！！！

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an float64.
func fibonacci() func() float64 {
    var secondLast float64
    var last float64 = 1
    return func() float64 {
        defer func() {
            secondLast, last = last, secondLast+last
        }()
        return secondLast
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

去游乐场

Answer 8

或者你可以使用这种方法......简单易懂，尽管与之前的答案没有太大不同。

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    f1 := 0
    f2 := 1
    return func() int {
        temp := f1+f2
        temp2 := f1
        f1 = f2
        f2 = temp
        return temp2
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

Answer 9

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    a, b, sum := 1, 1, 0
    return func() int {
        a,b = b,sum
        sum = a + b
        return b
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

Answer 10

我在这个练习中也遇到了一些麻烦，谢谢大家的回答。我想我也会分享，如果您继续游览并进入并发部分，还有另一种方法可以使用并发课程 4中的通道来实现此目的。

第 4 课的代码片段：

package main

import (
    "fmt"
)

func fibonacci(n int, c chan int) {
    x, y := 0, 1
    for i := 0; i < n; i++ {
        c <- x
        x, y = y, x+y
    }
    close(c)
}

func main() {
    c := make(chan int, 10)
    go fibonacci(cap(c), c)
    for i := range c {
        fmt.Println(i)
    }
}

Answer 11

如果您希望答案从零开始，请尝试此解决方案。

func fibonacci() func() int {
    a, b := 0, 1
    upd := func() { a, b = b, a+b }
    return func() int {
        defer upd()
        return a
    }
}

func main() {
    fib := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(fib())
    }
}

Answer 12

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    r := []int{0,0,1}
    return func() int{
        r = []int{r[1],r[2],r[1]+r[2]}
        return r[0]
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

Answer 13

我能够使用这篇文章中关于 go 中正确的递归语法的提示来实现递归闭包解决方案： https://stackoverflow.com/a/34194763/1592607

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func(int) int {
  var recur func(int) int
  recur = func(x int) int {
    switch x {
      case 0:
        return 0
      case 1:
        return 1
      default:
        return (recur(x - 1) + recur(x - 2))
    }
  }
  return recur
}

func main() {
  f := fibonacci()
  for i := 0; i < 10; i++ {
    fmt.Println(f(i))
  }
}

Answer 14

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
    first:=0
    second:=0
    return func() int{
        if second == 0 {
            second = 1
        } else if first == 0 {
            first = 1
        } else {
            first, second = second, first + second
        }
        return second
    }
}

func main() {
    f := fibonacci()
    for i := 0; i < 10; i++ {
        fmt.Println(f())
    }
}

Go 中的斐波那契闭合

问题描述投票：0回答：14

14个回答

最新问题

Go 中的斐波那契闭合

问题描述 投票：0回答：14

14个回答

最新问题

问题描述投票：0回答：14