Быстрый Фибоначчи с использованием рекурсии

Я реализовал функцию Фибоначчи в Scala, и она работает нормально, однако, когда я ввожу 50, ее вычисление занимает много времени, потому что каждый раз приходится вычислять 2 предыдущих целых числа. Я нашел функцию, которая сохраняет 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)
   }

recursion scala fibonacci tail-recursion
person user2947615    schedule 02.11.2013    source источник
comment
Попробуйте сначала поискать. stackoverflow.com/questions/7388416/   -  person psisoyev    schedule 02.11.2013
comment
Ну что ж, как и в опубликованной ссылке, вы можете использовать явную формулу, которая не требует предыдущих результатов.   -  person Stefan Kunze    schedule 02.11.2013
comment
Я этого не понял..   -  person user2947615    schedule 02.11.2013
comment
Техника мемоизации может быть очень полезной. blog.tmorris.net/posts/memoisation-with-state-using -скала   -  person Shrey    schedule 03.11.2013
comment
Я не понимаю технику запоминания... может кто-нибудь объяснить, как моя функция получает a и b, пожалуйста? Мне нужно понять этот код, прежде чем использовать его. Спасибо   -  person user2947615    schedule 06.11.2013

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете кэшировать промежуточные результаты, тогда вы никогда не будете пересчитывать один и тот же результат дважды.

Вот код

//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);    
  }
}

надеюсь, это поможет

person Gabriel    schedule 22.11.2014