scala - 使用递归的快速斐波那契

Question

我在 Scala 中实现了一个斐波那契函数，它工作正常，但是当我输入 50 时，计算它需要很长时间，因为它每次都必须计算前 2 个整数。我找到了一个保留前两个数字的函数。但是，有人可以告诉我如何编写此函数以使其接受 2 个整数而不是 3，并返回最后 2 个数字以计算特定索引 x 处的斐波那契。谢谢！

    def fastFib(x: Long ): Long = {
      def fast(x:Long , a:Long, b:Long):Long = 
      if (x<=0) a+b 
      else fast(x-1,b,a+b)
      if (x<2) 1 
      else fast(x-2,0,1)
   }

Answer 1

您可以缓存中间结果，然后您永远不会重新计算相同的结果两次

这是代码

//this supposed to contains all the value when initialized
//initialized with 0 for all value
val cache = Array [Int] (101);//0 to 100
cache(1)==1;//initial value
cache(2)=1;//initial value

def fibonacciCache(n:Int) : Int = {
  if (n>100)
  {
      println("error");
      return -1;
  }

  if (cache(n)!=0)//means value has been calculated
     return cache(n);
  else
  {
    cache(n)=fibonacciCache(n-1)+fibonacciCache(n-2);
    return cache(n);    
  }
}

希望有帮助