Algoritma JavaScript: Memecahkan Urutan Fibonacci (LeetCode)

Nov 24 2022

Keterangan

Angka-angka Fibonacci, biasanya dilambangkan dengan F(n) membentuk sebuah deret, yang disebut deret Fibonacci, sehingga setiap angka adalah jumlah dari dua angka sebelumnya, mulai dari 0 dan 1. Angka-angka dalam deret bilangan bulat berikut 0, 1, 1 , 2, 3, 5, 8, 13, 21, 34, 55, 89, …….

Foto oleh Ludde Lorentz di Unsplash

Angka- angka Fibonacci , umumnya dilambangkan F(n)membentuk urutan, yang disebut deret Fibonacci , sehingga setiap angka adalah jumlah dari dua angka sebelumnya, dimulai dari 0dan 1. Bilangan pada barisan bilangan bulat berikut 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

Itu adalah

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

Contoh 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

Ada beberapa opsi untuk memecahkan masalah ini: Pendekatan Rekursi.

Pendekatan Rekursi

Sebuah metode sederhana yang merupakan implementasi rekursif matematis relasi rekursif langsung. Cara paling lambat untuk menyelesaikan masalah ini karena membutuhkan kompleksitas waktu eksponensial : O(2^N) dan kompleksitas ruang : O(N) .

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

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

view raw fibonacci_1.js hosted with ❤ by GitHub

Pemrograman Dinamis menggunakan memoisasi (pendekatan Top down)

Kita dapat menghindari pekerjaan berulang yang dilakukan secara rekursif dengan menyimpan angka Fibonacci yang dihitung sejauh ini. Kami hanya perlu menyimpan semua nilai di peta. Kompleksitas waktu : O(N) dan kompleksitas ruang : 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

Pendekatan Iterasi

Iterasi, dengan menyelesaikan semua sub-masalah dan mengembalikan jawaban untuk elemen N, menggunakan nilai Fibonacci yang sudah dihitung. Kompleksitas waktu : O(N) dan kompleksitas ruang : 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

Pendekatan Iterasi ( Dioptimalkan Ruang)

Kita dapat mengoptimalkan pendekatan iterasi dengan menyimpan dua angka sebelumnya hanya karena hanya itu yang kita perlukan untuk mendapatkan angka Fibonacci berikutnya secara berurutan. Kompleksitas waktu : O(N) dan kompleksitas ruang : 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

Pendekatan Matriks Eksponensial

Gunakan Eksponensial Matriks untuk mendapatkan angka Fibonacci dari elemen di (0, 0) dalam matriks yang dihasilkan. Untuk melakukan ini, kita dapat mengandalkan persamaan matriks untuk deret Fibonacci, untuk menemukan bilangan Fibonacci ke-N :

Bagaimana cara kerja rumus ini Anda dapat melihat di Wiki

Solusi ini memiliki: kompleksitas waktu : O(logN) dan kompleksitas ruang : 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

Pendekatan Matematika

Kita dapat menggunakan golden ratio forumula:

Berikut tautan untuk mengetahui lebih lanjut tentang cara kerja deret Fibonacci dan rasio emas.

Solusi ini memiliki: kompleksitas waktu : O(logN) dan kompleksitas ruang : 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

Juga, terkadang diperlukan untuk mengembalikan bukan nilai untuk N yang diberikan, tetapi untuk mengembalikan array elemen Fibonacci hingga N yang diberikan.

Contoh:

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

dan Pemrograman Dinamis menggunakan memoisasi dengan sedikit perubahan:

	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

Kami telah mempertimbangkan opsi yang berbeda untuk memecahkan masalah Fibonacci, yang paling sulit dipahami adalah Eksponensial Matriks, tetapi biasanya pengetahuan tentang 4 metode sebelumnya sudah cukup untuk wawancara.

Semoga bermanfaat untuk Anda!

Terima kasih sudah membaca! Sampai jumpa lagi.

Lebih banyak konten di PlainEnglish.io . Mendaftar untuk buletin mingguan gratis kami . Ikuti kami di Twitter , LinkedIn , YouTube , dan Discord . Tertarik dengan Peretasan Pertumbuhan? Lihat Sirkuit .