再帰フィボナッチメモ

Question

私はプログラミングクラスIIのために私はユニヴァーサルで書いているプログラムで助けが必要です。質問は、再帰を使ってフィボナッチ数列を計算するかどうかを尋ねます。計算されたフィボナッチ数を配列に格納して、不要な繰り返し計算を停止し、計算時間を短縮する必要があります。

私は配列と暗記なしでプログラムを動かすことができましたが、今は実装しようとしています。私はそれをどのように構造化するか分からない。私はグーグルでいくつかの本を読んだが、ソリューションの実装方法を解決するのに役立つものはあまり見つかりませんでした。

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メソッドの終わりが主な問題です。私は配列の正しい部分に再帰的に数値を追加する方法を知りませんでした。

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

Answer 2

私は実際にあなたの辞書のものを調べることを忘れていると思います。

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

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

へ

変更

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

とそれだけで正常に動作しますが（それを自分でテストした:)

Answer 3

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; 

} 

Answer 4

メモ化を使用して第1 nフィボナッチ数を印刷するプログラム。

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

Answer 5

これは、値の静的配列を使用して再帰的フィボナッチ（）メソッドのためのメモ化にアプローチする別の方法である - この方法は、グローバル（クラスレベル）を使用すること

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/

Answer 6

ここで私は再帰フィボナッチメモを実装しています。 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 

Answer 7

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; 

} 

。ここで

Answer 8

はメモ化概念を活用本格的なクラスです：

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

は、次のチェック

の必要性を排除するために使用されていることを

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

お知らせ

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

それぞれの再帰関数呼び出しで