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; 

}

Podobne do większości powyższych rozwiązań, ale zamiast tego za pomocą mapy.

Program do drukowania pierwszych n liczb Fibonacciego za pomocą Memoizacji.

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 + ", ");
    }
}

Wydaje mi się, że zapominasz szukać rzeczy w swoim słowniku.

Zmień

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

Do

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

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

I działa po prostu dobrze (przetestowałem to Sam :)

Oto moja implementacja rekurencyjnej memoizacji Fibonacciego. Korzystanie z BigInteger i ArrayList pozwala obliczyć 100th lub nawet większy termin. Próbowałem 1000-tych terminów, a wynik jest zwracany w ciągu milisekund, oto kod:

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

Przykład wyjścia

printFebonachiRecursion(100);

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

Oto w pełni rozwinięta Klasa , która wykorzystuje koncepcję memoizacji:

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

Zauważ, że

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

Są używane w celu wyeliminowania konieczności następującej kontroli

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

Przy każdym wywołaniu funkcji rekurencyjnej.

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;

}

Jest to kolejny sposób podejścia do memoizacji rekurencyjnej metody Fibonacciego () przy użyciu statycznej tablicy wartości -

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

Zauważ, że ta metoda wykorzystuje globalną (poziom klasy) tablicę statyczną fibArray []. Aby przyjrzeć się całemu kodowi z wyjaśnieniem, możesz również zobaczyć:http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/

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

Może być za stary, ale oto moje rozwiązanie dla swift

class Recursion {
    func fibonacci(_ input: Int) {
        var dictioner: [Int: Int] = [:]
        dictioner[0] = 0
        dictioner[1] = 1
       print(fibonacciCal(input, dictioner: &dictioner))
    }

    func fibonacciCal(_ input: Int, dictioner: inout [Int: Int]) -> Int {
        if let va = dictioner[input]{
            return va
        } else {
            let firstPart = fibonacciCal(input-1, dictioner: &dictioner)

            let secondPart = fibonacciCal(input-2, dictioner: &dictioner)

            if dictioner[input] == nil {
                dictioner[input] = firstPart+secondPart
            }

            return firstPart+secondPart
        }
    }
}

// 0,1,1,2,3,5,8
class TestRecursion {
    func testRecursion () {
        let t = Recursion()
        t.fibonacci(3)
    }
}

public class FiboSeries {

    // first two terms of Fibonacci
    int x1 = 0;
    int x2 = 1;
    long xn; // nth number in Fibo series
    long[] array; // an array for implementing memoization

    // print the Nth number of Fibonacci - logic is f(n) = f(n-1) + f(n-2)

    long fibo(int n) {

        // initialize the array having n elements if it does not exist already
        if (array == null) {

            array = new long[n + 1];

        }

        // Fetch the memoized value from the array instead of recursion
        // for instance, fibo(3) will be calculated just once and stored inside this
        // array for next call
        if (array[n] != 0)

        {
            xn = array[n];
            return xn;
        }

        // value of fibo(1)
        if (n == 1) {
            xn = x1;

        }

        // value of fibo(2)
        if (n == 2) {
            xn = x2;

        }

        // value of Fibo(n) using non linear recursion
        if (n > 2) {

            xn = fibo(n - 1) + fibo(n - 2);
        }

        // before returning the value - store it at nth position of an array
        // However, before saving the value into array, check if the position is already 
        //full or not

        if (array[n] == 0) {

            array[n] = xn;
        }

        return xn;

    }

    public static void main(String[] args) {

        FiboSeries f = new FiboSeries();

        int n = 50;
        long number = f.fibo(n);

        System.out.println(number);

    }


}

W Swift 5.3

Jest to bardzo szybka metoda memoizacji. Najpierw zainicjuję Mój słownik pamięci podręcznej.

var cache = [Int:Int]()

Następnie tworzę mój generator liczb Fibonacciego. Ponieważ jest funkcją rekurencyjną, każde wywołanie tej funkcji teoretycznie obliczyłoby cały ciąg Fibonacciego ponownie aż do żądanej liczby. Dlatego używamy pamięci podręcznej, aby przyspieszyć funkcję rekurencyjną:

func fibonacci(_ number: Int) -> Int {
    // if the value is in the dictionary I just return it
    if let value = cache[number] { return value }

    // Otherwise I calculate it recursively. 
    // Every recursion will check the cache again, 
    // this is why memoisation is faster!
    let newValue = number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
    cache[number] = newValue
    return newValue
}

Mogę zapisać swoją sekwencję w tablicy takiej jak:

var numbers = Array(0..<10).map(fibonacci) //[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Lub użyć funkcji w pętla.

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

Oto moja realizacja.

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];
}