Fibonacci-Rechner-Algorithmus: Schritt für Schritt Erklärung

Der Fibonacci-Rechner ist ein ziemlich erstaunliches Gerät, das Fibonacci–Zahlen berechnen kann - eine Folge von Zahlen, bei der jede Zahl die Summe der beiden vorherigen ist. Dieser Algorithmus wurde im 13. Jahrhundert entwickelt und wird immer noch in verschiedenen Bereichen eingesetzt, von der Mathematik bis zur Programmierung.

Die Grundidee des Fibonacci–Rechner-Algorithmus besteht darin, Rekursion zu verwenden - einen Prozess, bei dem die Funktion sich selbst aufruft. Der Algorithmus beginnt mit zwei Startwerten, normalerweise 0 und 1, und berechnet dann die verbleibenden Zahlen der Sequenz nacheinander mit rekursiven Aufrufen.

Der Prozess der Berechnung von Fibonacci–Zahlen beginnt mit der Definition des zugrunde liegenden Falles - einer Situation, in der der Algorithmus aufhört, sich selbst aufzurufen und den Endwert zurückgibt. Der Algorithmus verarbeitet dann einen allgemeineren Fall, in dem er sich selbst aufruft, um die beiden vorherigen Zahlen zu berechnen und sie zu summieren, um die nächste Zahl in der Sequenz zu erhalten.

Der Fibonacci-Rechner-Algorithmus ist ein Beispiel für die effektive Verwendung von Rekursion, um ein komplexes mathematisches Problem zu lösen. Das Verständnis dieses Algorithmus kann helfen, nicht nur die Genialität von Leonardo von Pisa zu bewundern, sondern auch zu lernen, Rekursion in ihren eigenen Programmierprojekten zu verwenden und komplexe Probleme mit Leichtigkeit zu lösen.

Was ist der Fibonacci-Rechner-Algorithmus

Der Fibonacci-Rechner-Algorithmus kann auf verschiedene Arten implementiert werden, aber die Grundidee besteht darin, eine Rekursion oder Schleife zu verwenden, um Fibonacci-Zahlen zu berechnen.

Mithilfe der Rekursion können Sie einen Algorithmus wie folgt implementieren:

1. Wenn die Zahl n 0 oder 1 ist, geben wir n zurück.
2. Andernfalls geben wir das Ergebnis der Addition von zwei Funktionsaufrufen mit den Argumenten n-1 und n-2 zurück.

Daher ruft die rekursive Funktion sich selbst mit einem abnehmenden Argument auf, bis sie den zugrunde liegenden Fall (die Zahl 0 oder 1) erreicht, und gibt dann die Summe der beiden vorherigen Zahlen zurück. Dieser Prozess wird fortgesetzt, bis die erforderliche Fibonacci-Zahl erreicht ist.

Der Fibonacci-Rechner-Algorithmus kann auch mit einer Schleife implementiert werden:

1. Wir initialisieren zwei Variablen, prevNum und currNum, mit den Werten 0 bzw. 1.
2. Mit Hilfe einer Schleife durchlaufen wir die Zahlen von 0 bis einschließlich n, wobei n die zu berechnende Fibonacci-Zahl ist.
3. Aktualisieren Sie innerhalb der Schleife die Werte prevNum und currNum, indem Sie currNum auf prevNum + currNum und prevNum auf currNum setzen.
4. Nach Abschluss der Schleife wird das Ergebnis ein currNum-Wert sein, der der Fibonacci-Zahl entspricht.

Die Verwendung einer Schleife vermeidet rekursive Aufrufe und beschleunigt die Berechnung von Fibonacci-Zahlen, insbesondere bei großen Werten.

Wie funktioniert der Fibonacci-Rechner-Algorithmus

Der Algorithmus basiert auf Rekursion, dh der Verwendung einer Funktion, die sich selbst aufruft. Der folgende Ansatz wird verwendet, um Fibonacci-Zahlen mit der Rekursion zu berechnen:

1. Wenn die Eingabezahl 0 oder 1 ist, geben wir diese Zahl zurück, da sie ein Basisfall ist und keine weiteren Berechnungen erfordert.
2. Andernfalls rufen wir die Fibonacci-Rechner-Funktion für die beiden vorherigen Zahlen auf, addieren sie und geben das Ergebnis als Ergebnis der aktuellen Fibonacci-Zahl zurück.

Zum besseren Verständnis kann man sich vorstellen, dass jede Fibonacci-Zahl einen Eckpunkt eines verzweigten Baumes darstellt, wobei jeder Eckpunkt zwei Nachkommen hat. Wenn Sie also eine Zahl berechnen, müssen Sie für beide Teilbäume Berechnungen durchführen.

Obwohl der Algorithmus korrekt funktioniert, kann seine Leistung bei der Berechnung großer Fibonacci-Zahlen aufgrund wiederholter Berechnungen der gleichen Zahlen stark beeinträchtigt sein. Um die Leistung zu verbessern, können Sie eine dynamische Programmiermethode verwenden, die berechnete Werte speichert und sie für nachfolgende Berechnungen verwendet.

Erster Schritt des Algorithmus: Initialisieren von Variablen

Der Fibonacci-Rechner-Algorithmus beginnt mit der Initialisierung von zwei Variablen: die vorherige Zahl und die aktuelle Zahl. Die erste Fibonacci-Zahl ist 0, daher wird die vorherige Zahl mit Null initialisiert. Die zweite Fibonacci-Zahl ist 1, daher wird die aktuelle Zahl als eins initialisiert.

Die Initialisierung der Variablen erfolgt vor der Ausführung der Hauptschleife des Algorithmus. Dies ermöglicht es dem Algorithmus, korrekt mit Fibonacci-Zahlen zu arbeiten, beginnend mit der dritten Zahl.

Sie können Variablen wie folgt initialisieren:

int prev_number = 0;

int current_number = 1;

Wo prev_number - eine Variable, um die vorherige Fibonacci-Zahl zu speichern, und current_number - variable zum Speichern der aktuellen Fibonacci-Zahl.

Der zweite Schritt des Algorithmus ist die Eingabe der Fibonacci-Zahl

In diesem Schritt muss der Benutzer eine ganze Zahl eingeben, die die Zahl der Fibonacci-Zahl in der Sequenz bestimmt. Um das Verständnis und die Implementierung des Algorithmus zu erleichtern, werden wir die Eingabe von Zahlen auf 1 bis 30 beschränken.

Der Benutzer wird aufgefordert, die gewünschte Zahl einzugeben, und nachdem die eingegebenen Daten bestätigt wurden, geht der Algorithmus zum nächsten Schritt über: Berechnung der entsprechenden Fibonacci-Zahl in der Sequenz.

Der dritte Schritt des Algorithmus: Berechnung der Fibonacci-Zahl

Dazu müssen wir die Variablen a und b erstellen, die die beiden vorherigen Zahlen der Sequenz darstellen. Zunächst ist a gleich 0 und b gleich 1.

Dann erstellen wir eine Schleife, die n - 2 Mal iteriert wird (da die ersten beiden Zahlen bereits angegeben sind). Bei jeder Iteration überschreiben wir die Variablen a und b wie folgt:

1. Erstellen Sie eine temporäre Variable temp und weisen Sie der Variablen a einen Wert zu.
2. Überschreiben Sie a mit der Variablen b.
3. Überschreiben Sie b, indem Sie die Werte der temporären Variablen temp und der Variablen b addieren.

Als Ergebnis der Ausführung der Schleife erhalten wir den Wert der n-ten Fibonacci-Zahl in der Variablen b.

Jetzt, da wir einen Fibonacci-Zahlenwert haben, können wir ihn auf dem Bildschirm anzeigen oder nach Belieben verwenden.

Eine Möglichkeit, das Ergebnis auf dem Bildschirm anzuzeigen, besteht darin, JavaScript und seine Funktionen zur Manipulation von HTML-Elementen einer Seite zu verwenden. Sie können beispielsweise ein Element mit einer bestimmten ID im HTML-Code erstellen, auf das Sie über JavaScript zugreifen und das Ergebnis der Berechnung in das Element einfügen können.

Dazu können Sie die innerHTML-Eigenschaft des Elements verwenden, dem Sie das Ergebnis hinzufügen möchten. Zum Beispiel:

let resultElement = document.getElementById('result');resultElement.innerHTML = fibonacciNumber;

Hier ist ein resultElement eine Variable, die einen Verweis auf ein Element mit der id 'result' enthält. Verwenden Sie dann die innerHTML-Eigenschaft, um den Wert der Variablen Fibonacci in dieses Element einzufügen.

Auf diese Weise wird nach Abschluss aller Berechnungen eine Zahl auf dem Bildschirm angezeigt, die das n-te Element der Fibonacci-Sequenz ist.

Beispiel für den Fibonacci-Rechner-Algorithmus

Um die Funktionsweise des Fibonacci-Rechner-Algorithmus zu verstehen, betrachten wir ein Beispiel:

• Der Benutzer gibt die Zahl 6 als Index der Fibonacci-Sequenz ein.
• Der Algorithmus prüft, ob die eingegebene Zahl kleiner oder gleich 1 ist.
• Da die Zahl 6 größer als 1 ist, führt der Algorithmus die folgenden Aktionen aus:
• 1. Initialisiert die Variablen a, b und c mit den Werten 0, 1 bzw. 0.
  2. Startet eine Schleife, die 4 Mal (2 bis 6) ausgeführt wird.
  3. Innerhalb einer Schleife weist der Algorithmus der Variablen c zuerst den Wert der Summe der Variablen a und b zu (0 + 1 = 1).
  4. Aktualisiert dann die Werte der Variablen a und b, indem Sie der Variablen a den Wert b und der Variablen b den Wert c zuweisen (a = 1, b = 1).
  5. Daher haben die Variablen a und b nach der ersten Iteration der Schleife die Werte 1 bzw. 1.
  6. Der Algorithmus führt die Schleife fort und wiederholt die oben beschriebenen Schritte.
  7. Nach vier Iterationen der Schleife haben die Variablen a und b jeweils die Werte 3 bzw. 5.

Der Fibonacci-Rechner-Algorithmus ermöglicht es Ihnen daher, den Wert einer Zahl in der Fibonacci-Sequenz anhand ihres Indexes zu finden. In diesem Beispiel können Sie die sechste Zahl in der Fibonacci-Sequenz finden, die 5 ist.