Finden der Fibonacci-Nummer der großen Zahl

Question

Ich schrieb das folgende Programm für das Finden des Moduls der großen Fibonacci-Zahl. Dies kann große Zahlen lösen, aber in Fällen wie fibo_dynamic(509618737,4602,229176339), wo a = 509618737, b = 4602 und N = 229176339 nicht berechnet werden. Bitte hilf mir, das zu schaffen.

long long fibo_dynamic(long long x,long long y,long long n, long long a[]){ 
    if(a[n]!=-1){ 
     return a[n]; 
    }else{ 
     if(n==0){ 
      a[n]=x; 
      return x; 
     }else if(n==1){ 
      a[n]=y; 
      return y; 
     }else { 
      a[n]=fibo_dynamic(x,y,n-1,a)+fibo_dynamic(x,y,n-2,a); 
      return a[n]; 
     } 
    } 
} 

Answer 1

Die Werte werden überlaufen, weil Fibonacci-Zahlen sehr schnell zunehmen. Selbst für die ursprüngliche Fibonacci-Reihe (f(0) = 0 und f(1) = 1) ist der Wert f(90) mehr als 20 Stellen lang, die in keinem primitiven Datentyp in C++ gespeichert werden können. Sie sollten wahrscheinlich Modulus-Operator verwenden (da Sie es in Ihrer Frage erwähnt) Werte wie dies in Reichweite zu halten:

a[n] = (fibo_dynamic(x,y,n-1,a) + fibo_dynamic(x,y,n-2,a)) % MOD; 

Es ist sicher zu mod der Wert in jeder Phase, weil mod Betreiber hat die folgende Regel:

Sie haben auch die rekursive Version verwendet, um Fibonacci-Zahlen zu berechnen (obwohl Sie die Ergebnisse kleinerer Unterprobleme notiert haben). Dies bedeutet, dass es viele rekursive Aufrufe geben wird, die zusätzlichen Overhead verursachen. Besser, wenn möglich, eine iterative Version zu verwenden.

Als nächstes indexieren Sie das Array mit der Variablen n. Also gehe ich davon aus, dass die Größe des Arrays a zumindest n ist. Der Wert von n, der in der Frage erwähnt wird, ist sehr groß. Wahrscheinlich können Sie auf einer lokalen Maschine kein so großes Array deklarieren (bei einer Ganzzahl von 4 bytes entspricht die Größe des Arrays a etwa 874 MB).

Schließlich ist die Komplexität Ihres Programms O(n). Es gibt eine Technik, um n_th Fibonacci Nummer in O(log(n)) Zeit zu berechnen. Es ist "Lösen von Wiederholungsbeziehungen mithilfe von Matrixexponentiation". Fibonacci-Zahlen folgen der folgende lineare Rekursion:

f(n) = f(n-1) + f(n-2) for n >= 2 

this Lesen Sie die Technik zu verstehen.