Bedeutung der Fibonacci-Zahlen
Fibonacci-Zahlen sind eine bestimmte Folge von positiven ganzen Zahlen, beginnend bei 0. Ganze Zahlen sind positive ganze Zahlen. Eine Fibonacci-Zahl ist also eine bestimmte Folge von ganzen Zahlen oder natürlichen Zahlen, beginnend bei 0. In dieser Folge sind die ersten beiden Zahlen 0 und 1, in dieser Reihenfolge. Die restlichen Zahlen werden daraus entwickelt, indem die beiden vorherigen Zahlen addiert werden. Die ersten zwölf Fibonacci-Zahlen erhält man wie folgt:
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 lauten:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Die dreizehnte Zahl wäre natürlich: 144 = 55 + 89. Fibonacci-Zahlen kann man sich wie folgt in einem Array vorstellen:
| 0 | 1 | 1 | zwei | 3 | 5 | 8 | 13 | einundzwanzig | 3. 4 | 55 | 89 |
Ein Array hat Indizes. In der folgenden Tabelle zeigt die zweite Zeile die entsprechenden nullbasierten Indizes für die Fibonacci-Zahlen in einem Array:
| 0 | 1 | 1 | zwei | 3 | 5 | 8 | 13 | einundzwanzig | 3. 4 | 55 | 89 |
| 0 | 1 | zwei | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | elf |
Bei nullbasierten Indizes ist der letzte Index bei zwölf Elementen 11.
Fibonacci-Zahlen können in O(n)-Zeit oder in O(1)-Zeit erzeugt werden. In diesen Zeitkomplexitätsausdrücken bedeutet n n Hauptoperationen und 1 bedeutet 1 Hauptoperation. Bei O(n) entstehen n Fibonacci-Zahlen, beginnend bei 0. Bei O(1) ergibt sich eine Fibonacci-Zahl aus dem entsprechenden Index. Deshalb braucht O(1) nur eine Hauptoperation statt n Hauptoperationen.
Das Ziel dieses Artikels ist es, zu erklären, wie man Fibonacci-Zahlen mit JavaScript erzeugt, das heute eigentlich ECMAScript ist.
Codierungsumgebung
Die node.js-Umgebung wird nicht verwendet, wie der Leser vielleicht erwartet hat. Stattdessen wird der Browser zur Interpretation des Codes und zur Anzeige der Ergebnisse verwendet. Das Skript (Code) sollte in eine Texteditordatei geschrieben werden, die mit der Erweiterung „.html“ gespeichert werden sollte. Das Skript sollte als Mindestcode haben:
DOCTYPE-HTML >< html >
< Kopf >
< Titel > Fibonacci-Zahlen mit JavaScript Titel >
Kopf >
< Karosserie >
< Skripttyp = 'text/ecmascript' >
Skript >
Karosserie >
html >
Dies ist ein ungefährer Mindestcode, den eine Webseite benötigt. Die gesamte Codierung für diesen Artikel befindet sich zwischen den Tags .
Um den geschriebenen (hinzugefügten) Code auszuführen, doppelklicken Sie einfach auf das Symbol des Dateinamens, und der Browser des Computers öffnet ihn.
Definition einer Fibonacci-Zahl
Es gibt eine mathematische Definition für eine Fibonacci-Zahl. Es ist wie folgt definiert:
Wobei Fn eine Fibonacci-Zahl ist, die einem nullbasierten Index entspricht, n.
Die ersten beiden Zahlen: 0 und 1, sind in dieser Reihenfolge vordeklariert. Die letzte Zeile dieser Funktion zeigt, wie die restlichen Zahlen aus den ersten beiden Zahlen in ihrer Reihenfolge entstehen.
Diese Definition ist auch eine der Formeln für die Fibonacci-Zahl.
Produzieren von Fibonacci-Zahlen in O(n)-Zeit
Wenn n 1 ist, dann würde nur 0 als Fibonacci-Zahl angezeigt. Wenn n 2 ist, werden 0 und 1 als Fibonacci-Zahlen in dieser Reihenfolge angezeigt. Wenn n 3 ist, werden 0, 1 und 1 als Fibonacci-Zahlen in dieser Reihenfolge angezeigt. Wenn n 4 ist, werden 0, 1, 1 und 2 in dieser Reihenfolge als Fibonacci-Zahlen angezeigt. Wenn n 5 ist, werden 0, 1, 1, 2 und 3 in dieser Reihenfolge als Fibonacci-Zahlen angezeigt. Wenn n 6 ist, dann würden 0, 1, 1, 2, 3 und 5 als Fibonacci-Zahlen in dieser Reihenfolge angezeigt – und so weiter.
Die ECMAscript-Funktion zum Generieren der ersten n Fibonacci-Ganzzahlen (Zahlen) lautet:
< Skripttyp = 'text/ecmascript' >Funktion fibonacci ( EIN ) {
n = A. Länge ;
wenn ( n > 0 )
EIN [ 0 ] = 0 ;
wenn ( n > 1 )
EIN [ 1 ] = 1 ;
zum ( ich = zwei ; ich < n ; ich ++ ) { //n=0 und n=2 wurden berücksichtigt
aktuelleNr = EIN [ ich - 1 ] + EIN [ ich - zwei ] ;
EIN [ ich ] = aktuelleNr ;
}
}
Das schließende Skript-Tag wurde nicht angezeigt. Die Funktion erhält ein Array. Die ersten beiden Fibonacci-Zahlen werden an ihrer Position zugewiesen. Die for-Schleife iteriert vom nullbasierten Index 2 bis knapp unter n. Die wichtigste Anweisung in der for-Schleife ist:
aktuelleNr = A[i – 1] + A[i – 2];
Dadurch werden die beiden unmittelbar vorhergehenden Zahlen im Array hinzugefügt, um die aktuelle Zahl zu erhalten. Wenn die Ausführung der Funktion fibonacci() beendet ist, sind alle Elemente des Arrays die ersten n Fibonacci-Zahlen. Ein geeigneter Code, um die Funktion fibonacci() aufzurufen und die Fibonacci-Zahlen anzuzeigen, ist:
N = 12 ;Arr = Neu Array ( N ) ;
fibonacci ( Arr ) ;
zum ( ich = 0 ; ich < N ; ich ++ )
dokumentieren. schreiben ( Arr [ ich ] + ' ' ) ;
dokumentieren. schreiben ( '
' ) ;
Skript >
Dieser Code zeigt das schließende Skript-Tag. Der Code wird unter dem obigen Code eingegeben. Die auf der Webseite angezeigte Ausgabe lautet:
0 1 1 2 3 5 8 13 21 34 55 89
wie erwartet.
Produzieren einer Fibonacci-Zahl in O(1)-Zeit
O(1) ist konstante Zeit. Es bezieht sich auf eine Hauptoperation. Eine andere mathematische Formel zur Erzeugung einer Fibonacci-Zahl lautet:
Beachten Sie, dass auf der rechten Seite der Gleichung nicht die Quadratwurzel von 5 mit n potenziert wird; es ist der Ausdruck in Klammern, der mit n potenziert wird. Es gibt zwei solcher 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 – usw. Der Leser kann diese Formel mathematisch verifizieren, indem er verschiedene Werte für n einsetzt und auswertet. n ist in dieser Formel ein nullbasierter Index. Das Ergebnis ist die entsprechende Fibonacci-Zahl.
Der ECMAScript (JavaScript)-Code für diese Formel lautet:
< Skripttyp = 'text/ecmascript' >Funktion fibNr ( n ) {
FibN = ( Mathematik . pow ( ( 1 + Mathematik . quadrat ( 5 ) ) / zwei , n ) - Mathematik . pow ( ( 1 - Mathematik . quadrat ( 5 ) ) / zwei , n ) ) / Mathematik . quadrat ( 5 ) ;
Rückkehr FibN ;
}
Das schließende Skript-Tag wurde nicht angezeigt. Beachten Sie, wie die vordefinierten Funktionen Potenz (pow) und Quadratwurzel (sqrt) verwendet wurden. In ECMAScript (JavaScript) muss das Math-Modul nicht importiert werden. Die Funktion fibNo() implementiert die Formel direkt. Ein geeigneter Aufruf und Anzeige für die Funktion fibNo() auf der Webseite sind:
N = elf ;Rechts = fibNr ( N ) ;
dokumentieren. schreiben ( Rechts ) ;
Skript >
Der Code zeigt das schließende script-Tag. Die Ausgabe ist:
89.00000000000003
Es ist möglich, die unnötigen Dezimalstellen aus der Antwort zu entfernen. Aber das ist eine Diskussion für ein andermal.
Wenn mehr als eine Fibonacci-Zahl erforderlich ist, muss der Code die Formel einmal für jeden nullbasierten entsprechenden n-Index aufrufen.
Fazit
Fibonacci-Zahlen sind eine bestimmte Folge von positiven ganzen Zahlen, beginnend bei 0. Ganze Zahlen sind positive ganze Zahlen. Eine Fibonacci-Zahl ist also eine bestimmte Folge von ganzen Zahlen oder natürlichen Zahlen, beginnend bei 0. In dieser Folge sind die ersten beiden Zahlen 0 und 1, in dieser Reihenfolge. Diese ersten beiden Zahlen sind nur als solche definiert. Der Rest der Zahlen wird von dort aus entwickelt, indem die unmittelbar vorhergehenden zwei Zahlen addiert werden.
Nach der Erzeugung der ersten beiden Fibonacci-Zahlen muss, um die restlichen Fibonacci-Zahlen zu erzeugen, um am Ende insgesamt n Zahlen zu erhalten, eine for-Schleife mit der Anweisung verwendet werden:
aktuelleNr = A[i – 1] + A[i – 2];
Dadurch werden die unmittelbar letzten beiden Fibonacci-Zahlen zur aktuellen Fibonacci-Zahl addiert.
Wenn Sie einen nullbasierten Index erhalten, verwenden Sie die folgende Formel, um die entsprechende Fibonacci-Zahl zu erhalten:
