在Scala中生成一系列Fibonacci数

Question

  def fibSeq(n: Int): List[Int] = {
    var ret = scala.collection.mutable.ListBuffer[Int](1, 2)
    while (ret(ret.length - 1) < n) {
      val temp = ret(ret.length - 1) + ret(ret.length - 2)
      if (temp >= n) {
        return ret.toList
      }
      ret += temp
    }
    ret.toList
  }

所以上面是我使用Scala生成一个Fibonacci序列的代码n.我想知道Scala中是否有更优雅的方法可以做到这一点？

Answer 1

这有点优雅:

val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)

使用Streams,您可以"获取"许多值,然后您可以将其转换为List:

scala> fibs take 10 toList
res42: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)

更新:我写了一篇博文,详细介绍了这个解决方案的工作原理,以及为什么你最终得到斐波纳契数列!

Answer 2

定义Fibonacci序列有很多种方法,但我最喜欢的是这个:

val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }

这会创建一个流,当您需要特定的Fibonacci数时,该流将被懒惰地评估.

编辑:首先,正如Luigi Plinge指出的那样,开始时的"懒惰"是不必要的.第二,去看看他的答案,他几乎只做了同样的事情,更优雅.

Answer 3

不像Streams那样优雅,不是懒惰,而是拖尾并且处理BigInt(这也很容易用Luigis scanLeft做,但Tal的拉链不是这样 - 可能只是为了我).

@tailrec 
def fib (cnt: Int, low: BigInt=0, high: BigInt=1, sofar: List[BigInt]=Nil): List[BigInt] = {
  if (cnt == 0) (low :: sofar).reverse else fib (cnt - 1, high, low + high, low :: sofar) }

scala> fib(75)
res135:列表[BigInt] =列表(0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597 ,2584,4181,6765,10946,7711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102325155,165580141,267914296 ,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853 ,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2114885077978050)

Answer 4

我最喜欢的版本是：

def fibs(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fibs(b, a+b))

使用默认值，您可以调用fibs()并获取infinite Stream。

我也认为，尽管只有一个衬里，但它仍具有很高的可读性。

如果只想要第一个，n则可以使用takelike fibs() take n，如果需要它作为列表fibs() take n toList。