Обрезка последовательности Фибоначчи с использованием Java

Question

Вот моя реализация последовательности Фибоначчи с использованием Java

/**
 * Returns nth fibonacci number
 */
public class fib {

   public static void main(String[] args){
      System.out.println(fibonacci(12));
   }

   public static int fibonacci(int n) {
      if (n == 0){
         return 0;
      } else if (n == 1){
         return 1;
      } else {
         return fibonacci(n - 1) + fibonacci(n - 2);
      }
   }
}

Но визуализация этого метода с использованием рекурсии заставила меня думать, что это будет намного быстрее. Вот визуализация fib (5). https://imgur.com/a/2Rgxs Но это заставило меня задуматься. Обратите внимание, что когда мы поднимаемся вверх от нижней части рекурсивного пути, мы вычисляем fib(2), fib(3) и fib(4), но затем мы пересчитаем fib (3) в самой верхней правой ветви. Поэтому я подумал, когда мы снова всплываем, почему бы не сохранить fib (3), вычисленный по левой ветви, чтобы мы не делали никаких вычислений по правой ветви, как мой метод в настоящее время делает, как хеш-таблица при возврате. У меня вопрос, как мне реализовать эту идею?

Answer 1

Когда вы хотите добавить HashMap и оставайтесь со своим оригинальным подходом, попробуйте это:

static HashMap<Integer, Integer> values = new HashMap<Integer, Integer>();

public static void main(String[] args){
    values.put(0, 0);
    values.put(1, 1);
    System.out.println(fibonacci(12));
}

public static int fibonacci(int n) {
    if (values.containsKey(n)){
        return values.get(n);
    } else {
        int left = values.containsKey(n - 1) ? values.get(n - 1) : fibonacci(n - 1);
        values.put(n - 1, left);
        int right = values.containsKey(n - 2) ? values.get(n - 2) : fibonacci(n - 2);
        values.put(n - 2, right);
        return left + right;
    }
}

Этот подход может быть очень быстрым, если вы вызываете его чаще, потому что результаты Фибоначчи уже сохранены в values (наверняка это можно сделать и с другими подходами):

public static void main(String[] args){
    values.put(0, 0);
    values.put(1, 1);
    System.out.println(fibonacci(12));
    System.out.println(fibonacci(11));
    System.out.println(fibonacci(10));
}

Answer 2

Для быстрого расчета вам вообще не нужна рекурсия - достаточно сдвинуть промежуточные результаты

public static int fibonacci(int n) {
  if (n == 0) {
  return 0;
  } else {
    int npp = 0; // pre-previous number
    int np = 1; // previouse number
    int r = 1; // current number, eventually the result
    for (int i = 2; i <= n; i++) {
      r = np + npp;
      npp = np;
      np = r;
    }

    return r;
  }
}

Answer 3

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

public static int fibonacci(int n)
{    
    int f[] = new int[n+1];

    for (int i = 0; i <= n; i++) {
        if(i == 0 || i == 1) {
            f[i] = i;
        }
        else {
            f[i] = f[i-1] + f[i-2];
        }
    }

    return f[n];
}