JavaScript-Algorithmen: Fibonacci-Folge lösen (LeetCode)

Nov 24 2022

Beschreibung

Die Fibonacci-Zahlen, die allgemein mit F(n) bezeichnet werden, bilden eine Folge, die als Fibonacci-Folge bezeichnet wird, sodass jede Zahl die Summe der beiden vorhergehenden ist, beginnend mit 0 und 1. Die Zahlen in der folgenden ganzzahligen Folge sind 0, 1, 1 , 2, 3, 5, 8, 13, 21, 34, 55, 89, …….

Foto von Ludde Lorentz auf Unsplash

Die allgemein bezeichneten Fibonacci-ZahlenF(n) bilden eine Folge, die als Fibonacci-Folge bezeichnet wird, so dass jede Zahl die Summe der beiden vorhergehenden ist, beginnend mit 0und 1. Die Zahlen in der folgenden ganzzahligen Folge 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

Das ist

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Beispiel 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

0 <= n <= 30

Zur Lösung dieses Problems gibt es mehrere Möglichkeiten: Rekursionsansatz.

Rekursionsansatz

Eine einfache Methode, die eine direkte rekursive Implementierung einer mathematischen Wiederholungsrelation ist. Der langsamste Weg, dieses Problem zu lösen, da es eine exponentielle Zeitkomplexität : O(2^N) und Raumkomplexität : O(N) erfordert .

	function fibonacci(n) {
	if (n <= 1) {
	return n;
	}

	return fibonacci(n - 1) + fibonacci(n - 2);
	}

view raw fibonacci_1.js hosted with ❤ by GitHub

Dynamische Programmierung mit Memoisierung (Top-Down-Ansatz)

Wir können die wiederholte rekursive Arbeit vermeiden, indem wir die bisher berechneten Fibonacci-Zahlen speichern. Wir müssen nur alle Werte in einer Karte speichern. Zeitkomplexität : O(N) und Raumkomplexität : O(N) .

	/* Add the previous 2 numbers in the series and store it */
	const dpMemo = new Map([[0, 0], [1, 1]])

	function fibonacci(n) {
	/* Check if exist calculate value */
	if (dpMemo.has(n)) {
	return dpMemo.get(n);
	}

	/* Calculate and set value */
	dpMemo.set(n, fibonacci(n - 1) + fibonacci(n - 2));

	return dpMemo.get(n);
	}

view raw fibonacci_4.js hosted with ❤ by GitHub

Iterationsansatz _

Iteration mit Lösung aller Teilprobleme und Rückgabe der Antwort für N Elemente unter Verwendung bereits berechneter Fibonacci-Werte. Zeitkomplexität : O(N) und Raumkomplexität : O(N) .

	function fibonacci(n){
	/* Create an array and store Fibonacci numbers. */
	const fibonacciArr = [0, 1];

	for (let i = 2; i <= n; i++){
	/* Add the previous 2 numbers in the series and store it */
	fibonacciArr.push(fibonacciArr[i-1] + fibonacciArr[i-2]);
	}

	return fibonacciArr[n];
	}

view raw fibonacci_2.js hosted with ❤ by GitHub

Iterationsansatz ( platzoptimiert)

Wir können den Iterationsansatz optimieren, indem wir nur die beiden vorherigen Zahlen speichern, weil das alles ist, was wir brauchen, um die nächste Fibonacci-Zahl in Reihe zu bekommen. Zeitkomplexität : O(N) und Raumkomplexität : O(1) .

	function fibonacci(n){
	if (n <= 1) {
	return n;
	}

	let current;
	let prev1 = 1;
	let prev2 = 0;

	for (let i = 2; i <= n; i++){
	current = prev1 + prev2;
	prev2 = prev1;
	prev1 = current;
	}

	return current;
	}

view raw fibonacci_3.js hosted with ❤ by GitHub

Matrix-Potenzierungs-Ansatz

Verwenden Sie die Matrixexponentiation, um die Fibonacci-Zahl aus dem Element bei (0, 0) in der resultierenden Matrix zu erhalten. Um dies zu tun, können wir uns auf die Matrixgleichung für die Fibonacci-Folge stützen, um die N-te Fibonacci-Zahl zu finden:

Wie diese Formel funktioniert, können Sie im Wiki nachsehen

Diese Lösung hat: Zeitkomplexität : O(logN) und Raumkomplexität : O(logN) .

	function fibonacci(n){
	if (n <= 1) {
	return n;
	}

	/* Create an array of arrays(matrix) */
	const matrixA = [ [ 1, 1 ], [ 1, 0 ] ];

	matrixPower(matrixA, n - 1);

	return matrixA[0][0];
	}

	function matrixPower(matrixA, n) {
	if (n <= 1) {
	return;
	}

	matrixPower(matrixA, Math.floor(n / 2));
	multiply(matrixA, matrixA);

	const matrixB = [ [ 1, 1 ], [ 1, 0 ] ];

	if (n % 2 != 0) {
	multiply(matrixA, matrixB);
	}
	}

	/* Function that multiplies 2 matrices A and B of size 22, and puts the multiplication result back to A[][] /
	function multiply(A, B){
	const x = A[0][0] * B[0][0] + A[0][1] * B[1][0];
	const y = A[0][0] * B[0][1] + A[0][1] * B[1][1];
	const z = A[1][0] * B[0][0] + A[1][1] * B[1][0];
	const w = A[1][0] * B[0][1] + A[1][1] * B[1][1];

	A[0][0] = x;
	A[0][1] = y;
	A[1][0] = z;
	A[1][1] = w;
	}

view raw fibonacci_8.js hosted with ❤ by GitHub

Mathematischer Ansatz

Wir können Folgendes verwenden golden ratio forumula:

Hier ist ein Link , um mehr darüber zu erfahren, wie die Fibonacci-Folge und der Goldene Schnitt funktionieren.

Diese Lösung hat: Zeitkomplexität : O(logN) und Raumkomplexität : O(1) .

	function fibonacci(n) {
	const goldenRatio = (1 + Math.sqrt(5)) / 2;

	return Math.round(Math.pow(goldenRatio, n) / Math.sqrt(5));
	}

view raw fibonacci_5.js hosted with ❤ by GitHub

Manchmal ist es auch erforderlich, keinen Wert für ein bestimmtes N zurückzugeben, sondern ein Array von Fibonacci-Elementen bis zu einem bestimmten N zurückzugeben.

Beispiel:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

	function fibonacci(n){
	/* Create an array and store Fibonacci numbers. */
	const fibonacciArr = [0, 1];

	for (let i = 2; i <= n; i++){
	/* Add the previous 2 numbers in the series and store it */
	fibonacciArr.push(fibonacciArr[i-1] + fibonacciArr[i-2]);
	}

	/* Return array of Fibonacci */
	return fibonacciArr;
	}

view raw fibonacci_6.js hosted with ❤ by GitHub

und Dynamische Programmierung mit Memoisierung mit kleinen Änderungen:

	function getFibonacciArr(n) {
	/* Add the previous 2 numbers in the series and store it */
	const dpMemo = new Map([[0, 0], [1, 1]])

	/* Function to calculate Fibonacci values ans storre it */
	function fibonacci(n) {
	if (dpMemo.has(n)) {
	return dpMemo.get(n);
	}

	dpMemo.set(n, fibonacci(n - 1) + fibonacci(n - 2));

	return dpMemo.get(n);
	}

	/* Call function to calculate Fibonacci values ans storre it */
	fibonacci(n);

	/* return array of Map values */
	return Array.from(dpMemo.values());
	}

view raw fibonacci_7.js hosted with ❤ by GitHub

Wir haben verschiedene Möglichkeiten zur Lösung des Fibonacci-Problems in Betracht gezogen, die am schwierigsten zu verstehende ist die Matrixexponentiation, aber normalerweise reicht die Kenntnis der 4 vorherigen Methoden für ein Interview aus.

Hoffe, es war nützlich für Sie!

Danke fürs Lesen! Seh dich später.

Weitere Inhalte auf PlainEnglish.io . Melden Sie sich für unseren kostenlosen wöchentlichen Newsletter an . Folgen Sie uns auf Twitter , LinkedIn , YouTube und Discord . Interessiert an Growth Hacking? Schauen Sie sich die Schaltung an .