Рекурсивная memoization Фибоначчи

Мне нужна помощь с программой, которую я пишу для своего класса программирования II в университете. В вопросе спрашивается, что один рассчитывает последовательность Фибоначчи, используя рекурсию. Нужно хранить рассчитанные числа Фибоначчи в массиве, чтобы остановить ненужные повторные вычисления и сократить время вычисления.

Мне удалось заставить программу работать без массива и запоминания, теперь я пытаюсь реализовать это, и я застрял. Я не уверен, как его структурировать. Я googled и просматривал некоторые книги, но не нашел много, чтобы помочь мне решить, как реализовать решение.

import javax.swing.JOptionPane;
public class question2
{
static int count = 0;
static int [] dictionary;

public static void main(String[] args)
{

int answer;
int num = Integer.parseInt(javax.swing.JOptionPane.showInputDialog("Enter n:"));

javax.swing.JOptionPane.showMessageDialog(null, 
        "About to calculate fibonacci(" + num + ")");

//giving the array "n" elements
dictionary= new int [num];

if (dictionary.length>=0)
dictionary[0]= 0;

if (dictionary.length>=1)
dictionary[0]= 0;
dictionary[1]= 1;


//method call
answer = fibonacci(num);

//output
JOptionPane.showMessageDialog(null,"Fibonacci("+num+") is "+answer+" (took "+count+" calls)");
}



  static int fibonacci(int n)
  {
count++;

// Only defined for n >= 0
if (n < 0) {
  System.out.println("ERROR: fibonacci sequence not defined for negative numbers.");
  System.exit(1);
}

// Base cases: f(0) is 0, f(1) is 1
// Other cases: f(n) = f(n-1) + f(n-2)/
if (n == 0) 
{
  return dictionary[0];
}

else if (n == 1) 
{
  return dictionary[1];
}

else
return dictionary[n] = fibonacci(n-1) + fibonacci(n-2);



}

}

Вышеприведенное неверно, основной проблемой является мой метод fib. Я не знаю, как заставить его добавить числа рекурсивно к правильным частям массива.

Ответы

Ответ 1

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

if (n == 0) 
{
  // special case because fib(0) is 0
  return dictionary[0];
}
else 
{
  int f = dictionary[n];
  if (f == 0) {
    // number wasn't calculated yet.
    f = fibonacci(n-1) + fibonacci(n-2);
    dictionary[n] = f;
  }
  return f;
}

Ответ 2

public static int fib(int n, Map<Integer,Integer> map){

    if(n ==0){
        return 0;
    }

    if(n ==1){
        return 1;
    }

    if(map.containsKey(n)){
        return map.get(n);
    }

    Integer fibForN = fib(n-1,map) + fib(n-2,map);
    map.put(n, fibForN);

    return fibForN; 

}

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

Ответ 3

Запрограммировать первые n номера фибоначчи с помощью Memoization.

int[] dictionary; 
// Get Fibonacci with Memoization
public int getFibWithMem(int n) {
    if (dictionary == null) {
        dictionary = new int[n];
    }

    if (dictionary[n - 1] == 0) {
        if (n <= 2) {
            dictionary[n - 1] = n - 1;
        } else {
            dictionary[n - 1] = getFibWithMem(n - 1) + getFibWithMem(n - 2);
        }
    }

    return dictionary[n - 1];
}

public void printFibonacci()
{
    for (int curr : dictionary) {
        System.out.print("F[" + i++ + "]:" + curr + ", ");
    }
}

Ответ 4

Я считаю, что вы забываете на самом деле искать материал в своем словаре.

Изменить

else
    return dictionary[n] = fibonacci(n-1) + fibonacci(n-2);

к

else {
    if (dictionary[n] > 0)
        return dictionary[n];

    return dictionary[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

и он отлично работает (сам тестировал:)

Ответ 5

Вот моя реализация рекурсивной memoacci memoacci. Использование BigInteger и ArrayList позволяет рассчитать 100-й или даже более высокий срок. Я пробовал 1000-й срок, и результат возвращается в миллисекундах, вот код:

    private static List<BigInteger> dict = new ArrayList<BigInteger>();
    public static void printFebonachiRecursion (int num){
    if (num==1){
        printFebonachiRecursion(num-1);
        System.out.printf("Term %d: %d%n",num,1);
        dict.add(BigInteger.ONE);
    }
    else if (num==0){
        System.out.printf("Term %d: %d%n",num,0);
        dict.add(BigInteger.ZERO);
    }
    else {
    printFebonachiRecursion(num-1);
    dict.add(dict.get(num-2).add(dict.get(num-1)));
    System.out.printf("Term %d: %d%n",num,dict.get(num));
    }
}

Пример вывода

printFebonachiRecursion(100);

Term 0: 0
Term 1: 1
Term 2: 1
Term 3: 2
...
Term 98: 135301852344706746049
Term 99: 218922995834555169026
Term 100: 354224848179261915075

Ответ 6

int F(int Num){
int i =0;
int* A = NULL;
if(Num > 0)
{
 A = (int*) malloc(Num * sizeof(int));
}
else
 return Num;

for(;i<Num;i++)
 A[i] = -1;

return F_M(Num, &A);


}

int F_M(int Num, int** Ap){
int Num1 = 0;
int Num2 = 0;

if((*Ap)[Num - 1] < 0)
{
  Num1 = F_M(Num - 1, Ap);
  (*Ap)[Num -1] = Num1;
  printf("Num1:%d\n",Num1);
}
else
  Num1 = (*Ap)[Num - 1];

if((*Ap)[Num - 2] < 0)
{
  Num2 = F_M(Num - 2, Ap);
  (*Ap)[Num -2] = Num2;
  printf("Num2:%d\n",Num2);
}
else
  Num2 = (*Ap)[Num - 2];

if(0 == Num || 1 == Num)
{
 (*Ap)[Num] = Num;
 return Num;
}
else{
//  return ((*Ap)[Num - 2] > 0?(*Ap)[Num - 2] = F_M(Num -2, Ap): (*Ap)[Num - 2]  ) +     ((*Ap)[Num - 1] > 0?(*Ap)[Num - 1] = F_M(Num -1, Ap): (*Ap)[Num - 1]  );
  return (Num1 + Num2);
}

}

int main(int argc, char** argv){
int Num = 0;
if(argc>1){
sscanf(argv[1], "%d", &Num);
}

printf("F(%d) = %d", Num, F(Num));

return 0;

}

Ответ 7

Это еще один способ подхода к memoization для рекурсивного метода fibonacci() с использованием статического массива значений -

public static long fibArray[]=new long[50];\\Keep it as large as you need

public static long fibonacci(long n){
long fibValue=0;
if(n==0 ){
    return 0;
}else if(n==1){
    return 1;
}else if(fibArray[(int)n]!=0){
    return fibArray[(int)n];    
}
else{
    fibValue=fibonacci(n-1)+fibonacci(n-2);
    fibArray[(int) n]=fibValue;
    return fibValue;
}
}

Обратите внимание, что этот метод использует глобальный (класс) статический массив fibArray []. Чтобы посмотреть весь код с объяснением, вы также можете увидеть следующее: http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/

Ответ 8

Вот полноценный класс, который использует концепцию memoization:

import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

    public static Fibonacci getInstance() {
        return new Fibonacci();
    }

    public int fib(int n) {
        HashMap<Integer, Integer> memoizedMap = new HashMap<>();

        memoizedMap.put(0, 0);
        memoizedMap.put(1, 1);

        return fib(n, memoizedMap);
    }

    private int fib(int n, Map<Integer, Integer> map) {
        if (map.containsKey(n))
            return map.get(n);

        int fibFromN = fib(n - 1, map) + fib(n - 2, map);

        // MEMOIZE the computed value
        map.put(n, fibFromN);

        return fibFromN;
    }
}

Обратите внимание, что

memoizedMap.put(0, 0);
memoizedMap.put(1, 1);

используются для устранения необходимости следующей проверки

if (n == 0) return 0;
if (n == 1) return 1;

при каждом вызове рекурсивной функции.

Ответ 9

import java.util.HashMap;
import java.util.Map;

public class FibonacciSequence {

    public static int fibonacci(int n, Map<Integer, Integer> memo) {
        if (n < 2) {
            return n;
        }
        if (!memo.containsKey(n)) {
            memo.put(n, fibonacci(n - 1, memo) + fibonacci(n - 2, memo));
        }
        return memo.get(n);
    }

    public static int fibonacci(int n, int[] memo) {
        if (n < 2) {
            return n;
        }
        if (memo[n - 1] != 0) {
            return memo[n - 1];
        }
        return memo[n - 1] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    }

    public static void main(String[] s) {
        int n = 10;

        System.out.println("f(n) = " + fibonacci(n, new HashMap<Integer, Integer>()));
        System.out.println("f(n) = " + fibonacci(n, new int[n]));
    }
}

Ответ 10

#include <stdio.h>
long int A[100]={1,1};
long int fib(int n){
    if (A[n])
    {
        return A[n];
    }
    else
    {
         return A[n]=fib(n-1)+fib(n-2);
    }
}
int main(){
    printf("%ld",fib(30));
}

Ответ 11

Вот моя реализация.

private static int F(int N, int[] A) {
    if ((N == 0) || (N == 1)) return N;
    if (A[N] != 0) return A[N];

    if ((A[N - 1] != 0) && (A[N - 2] != 0)) {
        A[N] = A[N - 1] + A[N - 2];
        return A[N];
    }

    if (A[N-2] != 0) {
        A[N] = A[N - 2] + F(N - 1, A);
        return A[N];
    }
    if (A[N-1] != 0) {
        A[N] = A[N - 1] + F(N - 2, A);
        return A[N];
    }
    A[N] = F(N-1, A) + F(N-2, A);
    return A[N];
}

Ответ 12

Мемоизация, но O (log n) подход. Ссылка http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

private static HashMap<Integer, Integer> lookup = new HashMap<>();

private static int fib(int n){
    if(lookup.containsKey(n))
        return lookup.get(n);
    else{
        if(n <= 1)
            lookup.put(n, n);
        else{
            int k = (n & 1) == 1? (n+1)/2 : n/2;
            if((n&1) == 1)
                lookup.put(n, fib(k) * fib(k) + fib(k-1) * fib(k-1));
            else
                lookup.put(n, (2 * fib(k-1) + fib(k))*fib(k));
        }
        return lookup.get(n);
    }
}