头歌scala 函数之斐波那切数列

在Scala中，我们可以使用函数式编程的方式来实现斐波那契数列。斐波那契数列是一个经典的数列，每个数字是前两个数字的和，通常从0和1开始，例如：0, 1, 1, 2, 3, 5, 8, ...。

下面是一个简单的Scala函数，它使用递归的方式来计算第n项的斐波那契值：

def fibonacci(n: Int): Int = {
  if (n <= 1) n // base case: 第0项和第1项直接返回数值
  else fibonacci(n - 1) + fibonacci(n - 2) // 如果n大于1，则递归调用自身
}

然而，这个递归实现对于大的n可能会很慢，因为它会有很多重复的计算。为了优化性能，我们可以使用"记忆化"（ Memoization）技术，将已经计算过的结果存储起来，避免重复计算。这可以改写成如下的函数：

import scala.collection.mutable.Map

val memo = Map[Int, Int]()

def fibonacciOptimized(n: Int): Int = memo.getOrElseUpdate(n, {
  if (n <= 1) n
  else fibonacciOptimized(n - 1) + fibonacciOptimized(n - 2)
})

现在，`fibonacciOptimized`会在首次遇到给定n的值时计算，然后将结果存入map中供后续调用使用。

相关问题

用Scala计算出斐波那切数列前五项，去掉重复项并计算各项之和。F(n)=F(n-1)+F(n-2),n≥2,F(0)=0,F(1)=1

Scala是一种多范式编程语言，支持面向对象编程和函数式编程，非常适合实现数学问题的解决方案。下面是一个使用Scala编写的计算斐波那契数列前五项，去掉重复项并计算各项之和的示例代码：

object Fibonacci {
  def main(args: Array[String]): Unit = {
    val fibs = Stream.iterate((0, 1)) { case (a, b) => (b, a + b) }.map(_._1).take(5)
    val distinctFibs = fibs.distinct
    val sum = distinctFibs.sum
    println(s"Fibonacci series (first five): $fibs")
    println(s"Distinct Fibonacci numbers: $distinctFibs")
    println(s"Sum of distinct Fibonacci numbers: $sum")
  }
}

在这段代码中：
- 使用`Stream.iterate`函数创建了一个无限的斐波那契数列流，每次迭代生成一个新的数对，包含前两个斐波那契数。
- `map(_._1)`用于提取数对中的第一个元素，即当前的斐波那契数。
- `take(5)`用于获取前五个斐波那契数。
- `distinct`方法用于去除可能产生的重复项。
- `sum`方法用于计算所有元素的总和。

执行上述代码将输出斐波那契数列的前五项，去掉重复项后的结果以及这些数的总和。由于斐波那契数列定义特性，前五项实际上不会有重复项，因此结果中的distinctFibs与fibs相同。

scala尾递归实现斐波那契数列

在Scala中，可以使用尾递归来实现斐波那契数列。尾递归的实现方式是将递归调用的结果作为参数传递给下一次调用，从而避免了递归调用栈的溢出。下面是一个使用尾递归实现斐波那契数列的示例代码：

def fibonacci(n: Int): Int = {
  @annotation.tailrec
  def loop(n: Int, prev: Int, cur: Int): Int =
    if (n == 0) prev
    else loop(n - 1, cur, prev + cur)

  loop(n, 0, 1)
}

在这个实现中，我们使用了一个内部函数`loop`来进行尾递归。`loop`函数接受三个参数：当前的计数器`n`、前一个斐波那契数`prev`和当前的斐波那契数`cur`。在每次递归调用中，我们将`n`减1，将`cur`作为下一次调用的`prev`参数，将`prev + cur`作为下一次调用的`cur`参数。当`n`等于0时，我们返回`prev`作为结果。

需要注意的是，在这个实现中，我们使用了`@annotation.tailrec`注解来确保编译器对`loop`函数进行尾递归优化。如果`loop`函数不是尾递归，编译器会给出一个警告。