1

我在 Scala 中编写了这个函数来计算给定特定索引 n 的斐波那契数：

 def fibonacci(n: Long): Long = {
 if(n <= 1) n
 else
   fibonacci(n - 1) + fibonacci(n - 2)     
}

但是，在使用大索引进行计算时效率不高。因此我需要使用元组实现一个函数，这个函数应该返回两个连续的值作为结果。

有人可以给我任何提示吗？我以前从未使用过 Scala。谢谢！

4

4 回答 4

2

这个问题也许应该去数学。

斐波那契数列有一个明确的公式。如果您需要计算 n 的斐波那契数而不需要前面的数，这要快得多。你可以在这里找到它（比内公式）：http ://en.wikipedia.org/wiki/Fibonacci_number

于 2013-11-05T21:28:45.607 回答
1

这是一个简单的尾递归解决方案：

def fibonacci(n: Long): Long = {
  def fib(i: Long, x: Long, y: Long): Long = {
    if (i > 0) fib(i-1, x+y, x)
    else x
  }
  fib(n, 0, 1)
}

您发布的解决方案需要指数级的时间，因为它在每一步创建两个递归调用树 (fibonacci(n - 1)和)。fibonacci(n - 2)通过简单地跟踪最后两个数字，您可以递归地计算答案而无需任何重复计算。

你能解释一下中间部分，为什么(i-1, x+y, x)等等。对不起，如果我问得太多，但我讨厌在不知道它是如何工作的情况下复制和粘贴代码。

这很简单——但我对变量名的错误选择可能会让人感到困惑。

  • i只是一个计数器，说明我们还剩下多少步。如果我们正在计算第M 个 （我正在使用M，因为我已经n在我的代码中使用过）斐波那契数，然后告诉我们在达到第M 个i项之前还有多少项需要计算。
  • x是斐波那契数列中的第 m项，或F m（其中m = M - i）。
  • y是m-1th斐波那契数列中的项，或F m-1。

所以，在第一次调用fib(n, 0, 1)时，我们有i=M, x=0, y=1. 如果您查看双向斐波那契数列，您会看到 F 0 = 0 和 F -1 = 1，这就是为什么x=0和y=1这里。

在下一次递归调用中，我们作为下一个值fib(i-1, x+y, x)传递。这直接来自定义：x+yx

F n = F n-1 + F n-2

我们x作为下y一项通过，因为我们当前的 F n-1与下一项的 F n-2相同。

每一步我们都会递减i，因为我们离最终答案更近了一步。

于 2013-11-05T21:34:03.427 回答
0

更新

这是另一个解决方案，再次使用Streams如下（免费获取Memoization），但更直观（又名：在 fibs Stream 上不使用 zip/tail 调用）：

val fibs = Stream.iterate( (0,1) ) { case (a,b)=>(b,a+b)  }.map(_._1)

产生与以下相同的输出：

fibs take 5 foreach println

Scala 通过Streams支持记忆化，Streams是惰性列表的一种实现。这非常适合 Fibonacci 实现，它实际上在Scala Api for Streams中作为示例提供。在这里引用：

import scala.math.BigInt
object Main extends App {

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

  fibs take 5 foreach println
}

// prints
//
// 0
// 1
// 1
// 2
// 3
于 2013-11-06T08:08:54.663 回答
0

我假设您没有从以前的计算中保存值。如果是这样，使用黄金比例而不是递归定义的直接公式会更快。该公式可以在Wikipedia 页面中找到斐波那契数：

floor(pow(phi, n)/root_of_5 + 0.5)

哪里phi = (1 + sqrt(5)/2)。

我对 Scala 编程一无所知。我希望 SO 上的某个人将我的伪代码升级为实际的 Scala 代码。

于 2013-11-05T21:38:16.253 回答