Fibonacci -Zahlen mit JavaScript
Bedeutung von Fibonacci -Zahlen
Fibonacci -Zahlen sind eine bestimmte Folge von positiven Ganzzahlen, die ab 0 beginnen. Ganze Zahlen sind positive Ganzzahlen. Eine Fibonacci -Zahl ist also eine bestimmte Abfolge von ganzen Zahlen oder natürlichen Zahlen, ab 0 ab 0. In dieser Sequenz sind die ersten beiden Zahlen in dieser Reihenfolge 0 und 1. Der Rest der Zahlen wird von dort aus entwickelt, indem die beiden vorherigen Zahlen hinzugefügt werden. Die ersten zwölf Fibonacci -Zahlen werden wie folgt erhalten:
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
Mit anderen Worten, die ersten zwölf Fibonacci -Zahlen sind:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Natürlich wäre die dreizehnte Zahl: 144 = 55 + 89. Fibonacci -Zahlen können sich in einem Array wie SO befinden:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
Ein Array hat Indizes. In der folgenden Tabelle zeigt die zweite Zeile die entsprechenden Null-basierten Indizes für die Fibonacci-Nummern in einem Array:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
Wenn es zwölf Elemente gibt, ist der letzte Index 11, wenn es zwölf Elemente gibt, 11 ist 11.
Fibonacci -Zahlen können in O (n) Zeit oder in o (1) Zeit erzeugt werden. In diesen zeitlichen Komplexitätsausdrücken bedeutet N n Hauptvorgänge und 1 Hauptbetrieb 1 Hauptbetrieb. Mit O (n) werden N -Fibonacci -Zahlen erzeugt, ab 0 ab 0. Mit O (1) wird eine Fibonacci -Zahl aus dem entsprechenden Index erzeugt. Deshalb nimmt O (1) nur einen Hauptvorgang anstelle von N -Hauptoperationen durch.
Ziel dieses Artikels ist es zu erklären, wie man Fibonacci -Zahlen produziert, in beiden Fällen mit JavaScript, das heute tatsächlich ecmascript ist.
Codierungsumgebung
Der Knoten.Die JS -Umgebung wird nicht verwendet, da der Leser möglicherweise erwartet hat. Stattdessen wird der Browser zur Interpretation des Codes und zur Anzeige der Ergebnisse verwendet. Das Skript (Code) sollte in einer Textedateidatei geschrieben werden, die mit der Erweiterung gespeichert werden sollte.html.Das Skript sollte als Mindestcode haben:
Dies ist ein ungefährer Mindestcode, den eine Webseite benötigt. Die gesamte Codierung für diesen Artikel geht zwischen den Tags, und .
Um den geschriebenen Code auszuführen (hinzugefügt) ausführen, doppelklicken Sie einfach auf das Symbol des Dateinamens, und der Browser des Computers öffnet ihn.
Definition einer Fibonacci -Nummer
Es gibt eine mathematische Definition für eine Fibonacci -Nummer. Es ist wie folgt definiert:
Wobei FN eine Fibonacci-Nummer ist, die einem Null-basierten Index entspricht, n.
Die ersten beiden Zahlen: 0 und 1 sind in dieser Reihenfolge vorgefertigt. Die letzte Zeile dieser Funktion zeigt, wie der Rest der Zahlen aus den ersten beiden Zahlen in ihrer Bestellung stammt.
Diese Definition ist auch eine der Formeln für die Fibonacci -Nummer.
Erzeugung von Fibonacci -Zahlen in o (n) Zeit
Wenn n 1 ist, werden nur 0 als Fibonacci -Nummer angezeigt. Wenn n 2 ist, werden 0 und 1 in dieser Reihenfolge als Fibonacci -Zahlen angezeigt. Wenn N 3 ist, dann würden 0, 1 und 1 in dieser Reihenfolge als Fibonacci -Zahlen angezeigt. Wenn N 4, dann 0, 1, 1 und 2 als Fibonacci -Zahlen angezeigt werden, in dieser Reihenfolge werden. Wenn n 5, dann 0, 1, 1, 2 und 3 ist, werden in dieser Reihenfolge als Fibonacci -Zahlen angezeigt. Wenn n 6, dann 0, 1, 1, 2, 3 und 5 ist.
Die ECMascript -Funktion zum Generieren der ersten N -Fibonacci -Ganzzahlen (Zahlen) lautet:
Dieser Code zeigt das Schließskript -Tag an. Der Code wird unter dem obigen Code getippt. Die auf der Webseite angezeigte Ausgabe lautet:
0 1 1 2 3 5 8 13 21 34 55 89
wie erwartet.
Erstellen einer Fibonacci -Zahl in o (1) Zeit
O (1) ist eine konstante Zeit. Es bezieht sich auf einen Hauptvorgang. Eine weitere mathematische Formel zur Erzeugung einer Fibonacci -Nummer ist:
Beachten Sie, dass auf der rechten Seite der Gleichung nicht die Quadratwurzel von 5 ist, die auf die Power N angehoben wird; Es ist der Ausdruck in Klammern, der an die Macht n angehoben wird. Es gibt zwei solche Ausdrücke.
Wenn N 0 ist, wäre Fibn 0. Wenn n 1 ist, wäre Fibn 1. Wenn n 2 ist, wäre Fibn 1. Wenn n 3 ist, wäre Fibn 2. Wenn n 4 ist, wäre Fibn 3 - und so weiter. Der Leser kann diese Formel mathematisch überprüfen, indem sie unterschiedliche Werte für n ersetzen und bewerten. n ist ein auf Null basierender Index in dieser Formel. Das Ergebnis ist die entsprechende Fibonacci -Nummer.
Der Codes für diese Formel ist der ECMascript -Code (JavaScript)
Der Code zeigt das Schließskript -Tag an. Die Ausgabe ist:
89.000000000003
Es ist möglich, die unnötigen Dezimalstellen aus der Antwort zu entfernen. Dies ist jedoch eine Diskussion für einige andere Zeit.
Wenn mehr als eine Fibonacci -Nummer erforderlich ist, muss der Code die Formel für jeden null basierenden entsprechenden N -Index einmal aufrufen.
Abschluss
Fibonacci -Zahlen sind eine bestimmte Folge von positiven Ganzzahlen, die ab 0 beginnen. Ganze Zahlen sind positive Ganzzahlen. Eine Fibonacci -Zahl ist also eine bestimmte Abfolge von ganzen Zahlen oder natürlichen Zahlen, ab 0 ab 0. In dieser Sequenz sind die ersten beiden Zahlen in dieser Reihenfolge 0 und 1. Diese ersten beiden Zahlen sind nur als solche definiert. Der Rest der Zahlen wird von dort aus entwickelt, indem die unmittelbaren vorherigen beiden Zahlen hinzugefügt werden.
Nachdem die ersten beiden Fibonacci-Nummern erstellt wurden, um den Rest der Fibonacci-Zahlen zu erzeugen, muss mit der Erklärung eine Gesamtnummern mit einer Gesamtnummern verwendet werden:
currno = a [i - 1] + a [i - 2];
Dies fügt die unmittelbaren letzten beiden Fibonacci -Zahlen hinzu, um die aktuelle Fibonacci -Nummer zu haben.
Verwenden Sie bei einem nullbasierten Index, um die entsprechende Fibonacci-Nummer zu haben, die Formel: