Geben Sie die ersten n Fibonacci-Zahlen mit der direkten Formel aus

In diesem Artikel werden wir das Problem des Druckens der ersten n Fibonacci-Zahlen mithilfe einer direkten Formel lösen.

In der Mathematik werden Fibonacci-Zahlen oft durch Fn (für die n-te Fibonacci-Zahl) dargestellt und bilden eine Folge, in der jede Zahl gleich der Summe der beiden vorherigen Zahlen ist. Die n-te Fibonacci-Zahl kann wie folgt ausgedrückt werden:

$$mathrm{Fn:=:F_{n-1}:+:F_{n-2}}$$

Die Serie beginnt mit 0 und 1. Die ersten paar Werte in der Fibonacci-Folge beginnend bei 0 und 1 sind -

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

In diesem Problem erhalten wir also eine Zahl N und müssen die ersten N Fibonacci-Zahlen mit der direkten Formel ausgeben.

Beispiel

Geben Sie ein: 4

Ausgabe: 0 1 1 2

Geben Sie ein: 8

Ausgabe: 0 1 1 2 3 5 8 13

Für diese Frage müssen wir das Konzept der Binet-Formel verstehen, die eine direkte Formel zum Erhalten der n-ten Fibonacci-Zahl liefert, die im Abschnitt zum Algorithmus ausführlich besprochen wird.

Algorithmus

Gemäß der Formel $mathrm{Fn:=:F_{n-1}:+:F_{n-2}}$ benötigen wir das (n-1)te Element und das (n-2)te und addieren sie dazu Holen Sie sich das n-te Element. Denn in diesem Problem sollten wir die ersten n Fibonacci-Zahlen mithilfe der direkten Formel drucken, um die n-te Fibonacci-Zahl zu erhalten.

Um die n-te Fibonacci-Zahl in der Fibonacci-Folge zu erhalten, können Sie eine explizite Formel namens Binet-Formel anwenden. Es wurde vom Mathematiker Jacques Philippe Marie Binet erstellt.

Formel

Wenn $mathrm{Fn}$ die n-te Fibonacci-Zahl in der Fibonacci-Folge darstellt, kann sie als

ausgedrückt werden

$$mathrm{F_n:=:frac{1}{sqrt5}((frac{1+{sqrt5}}{2})^n:-:(frac{ 1-{sqrt5}}{2})^n )}$$

HINWEIS – Diese Formel ergibt die Fibonacci-Folge beginnend bei 1 und 1. Um die Fibonacci-Folge beginnend bei 0 und 1 zu erhalten, verwenden Sie n-1, um die n-te Fibonacci-Zahl zu erhalten.

Wir können diese Formel mithilfe des Konzepts quadratischer Gleichungen ableiten. Wir werden diese Formel verwenden, um jede Fibonacci-Zahl bis zur n-ten Fibonacci-Zahl zu drucken, um die ersten n Fibonacci-Zahlen zu drucken.

Methode

• Wir werden eine for-Schleife verwenden, um alle N Fibonacci-Zahlen von 0 bis n Iterationen auszugeben, da wir die Fibonacci-Folge betrachten, die bei 0 und 1 beginnt.

• Initialisieren Sie die Variable mit einer Fibonacci-Zahl und speichern Sie die i-te Fibonacci-Zahl unter Verwendung der obigen Formel bei jeder Iteration, bis i

• Fahren Sie fort, die Fibonacci-Zahlen bei jeder Iteration auszugeben, wodurch wir die ersten N Fibonacci-Zahlen erhalten.

Beispiel

Das Folgende ist die Implementierung der obigen Methode in C++ -

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void fibonacci(long long int N){ //function to print first N fibonacci numbers
   long long int fibonacci; //to store ith fibonacci number
   
   for(int i=0;i<N;i++) { //using for loop to print all N fibonacci numbers
      //using direct formula to print every fibonacci number until n
      fibonacci = 1/sqrt(5)*(pow((1+sqrt(5))/2,i) - (pow((1-sqrt(5))/2,i)));
      cout<<fibonacci<<" ";
   }
   cout<<endl;
}

//Driver Code
int main(){
   long long int N=10;
   fibonacci(N);
   N=6;
   fibonacci(N);
   return 0;
}

Ausgabe

0 1 1 2 3 5 8 13 21 34
0 1 1 2 3 5

Zeitliche Komplexität: O(n), weil die for-Schleife läuft, bis i kleiner als n ist.

Raumkomplexität: O(1), weil es keinen zusätzlichen Platz beansprucht.

Fazit

In diesem Artikel haben wir gelernt, die ersten N Fibonacci-Zahlen mithilfe einer direkten Formel anstelle der Rekursion auszugeben. Wir haben auch die Binet-Formel gelernt, mit der die n-te Fibonacci-Zahl in der Fibonacci-Folge direkt ermittelt werden kann.

Ich hoffe, dieser Artikel hat Ihnen geholfen, alle Konzepte zu diesem Thema zu klären.

Das obige ist der detaillierte Inhalt vonGeben Sie die ersten n Fibonacci-Zahlen mit der direkten Formel aus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!