在 Scala 中生成斐波那契数列
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9864497/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Generate a sequence of Fibonacci number in Scala
提问by nobody
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
}
So the above is my code to generate a Fibonacci sequence using Scala to a value n. I am wondering if there is a more elegant way to do this in Scala?
所以上面是我使用 Scala 生成斐波那契数列的代码n。我想知道在 Scala 中是否有更优雅的方法来做到这一点？
回答by Luigi Plinge
This is a bit more elegant:
这更优雅一点：
val fibs: Stream[Int] = 0 #:: fibs.scanLeft(1)(_ + _)
With Streams you "take" a number of values, which you can then turn into a List:
使用 Streams，您可以“获取”多个值，然后您可以将这些值转换为列表：
scala> fibs take 10 toList
res42: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
Update: I've written a blog postwhich goes more detail regarding how this solution works, and why you end up with a Fibonacci sequence!
更新：我写了一篇博客文章，其中详细介绍了此解决方案的工作原理，以及为什么最终会得到斐波那契数列！
回答by Tal Pressman
There are many ways to define the Fibonacci sequence, but my favorite is this one:
定义斐波那契数列的方法有很多，但我最喜欢的是这个：
val fibs:Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ t => t._1 + t._2 }
This creates a stream that is evaluated lazily when you want a specific Fibonacci number.
这将创建一个流，当您需要特定的 Fibonacci 数时，该流会延迟计算。
EDIT: First, as Luigi Plinge pointed out, the "lazy" at the beginning was unnecessary. Second, go look at his answer, he pretty much did the same thing only more elegantly.
编辑：首先，正如 Luigi Plinge 所指出的，一开始的“懒惰”是不必要的。其次，去看看他的回答，他几乎做了同样的事情，只是更优雅。
回答by user unknown
Not as elegant as Streams, not lazy, but tailrecursive and handles BigInt (which is easy to do with Luigis scanLeft too, but not so with Tal's zip - maybe just for me).
不像 Streams 那样优雅，不懒惰，但采用尾递归并处理 BigInt（这对于 Luigis scanLeft 也很容易，但对于 Tal 的 zip 则不然——也许只适合我）。
@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: List[BigInt] = List(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, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 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, 2111485077978050)
scala> fib (75)
res135: List[BigInt] = List(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，1346269，2178309，3524578，5702887，9227465，14930352，24157817，39088169，63245986，102334155，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, 80651559339, 80651559339, 80651559339, 80651559339, 80651559339, 85959570
回答by dvdnglnd
My favorite version is:
我最喜欢的版本是：
def fibs(a: Int = 0, b: Int = 1): Stream[Int] = Stream.cons(a, fibs(b, a+b))
With the default values you can just call fibs()and get the infinite Stream.
使用默认值，您可以调用fibs()并获得无穷大Stream。
I also think it's highly readable despite being a one liner.
我也认为它是高度可读的，尽管它是单行的。
If you just want the first nthen you can use takelike fibs() take n, and if you need it as a list fibs() take n toList.
如果你只想要第一个，n那么你可以使用takelike fibs() take n，如果你需要它作为列表fibs() take n toList。
回答by dimitrisli
Here's yet another approach again using *Stream*s on an intermediary tuples:
这是在中间元组上再次使用 * Stream*s 的另一种方法：
scala> val fibs = Stream.iterate( (0,1) ) { case (a,b)=>(b,a+b) }.map(_._1)
fibs: scala.collection.immutable.Stream[Int] = Stream(0, ?)
scala> fibs take 10 toList
res68: List[Int] = List(0, 1, 1, 2, 3, 5, 8, 13, 21, 34)
回答by Cristian
I find this implementation to be more legible:
我发现这个实现更清晰：
def fibonacci: Stream[Int] = {
def loop(a: Int, b: Int): Stream[Int] = (a + b) #:: loop(b, b + a)
loop(0, 1)
}
回答by Saddam Abu Ghaida
def fib:Stream[Int] ={
def go(f0: Int, f1:Int): Stream[Int] = {
Stream.cons(f0,go(f1,f0+f1))
}
go(0,1)
}
