Przejdź do treści

Centrum Kształcenia Zawodowego i Ustawicznego w Mrągowie

JS: Ciąg Fibonacciego

czwartek,

JS: Ciąg Fibonacciego

Dzisiejsza data zapisana w systemie amerykańskim (1123) to cyfry stanowiące początek ciągu Fibonacciego, tego dnia obchodzony jest Dzień Fibonacciego. Osiągnięcia włoskiego matematyka Leonarda Fibonacciego znalazły zastosowania w wielu dziedzinach, m.in. był on autorem specyficznego ciągu liczbowego zwanego ciągiem Fibonacciego.

Ciąg Fibonacciego to ciąg liczb naturalnych określony rekurencyjnie w następujący sposób:

  • wyraz jest równy 0 dla n = 0,
  • wyraz jest równy 1 dla n = 1,
  • dla n > 1 jest sumą dwóch poprzednich.

Istnieje wersja definicji, w której zero nie jest zaliczone do elementów ciągu Fibonacciego, takiego przypadku nie uwzględniono w przykładach, jednak łatwo je zmodyfikować do takiego wymagania. Powstało wiele sposobów na obliczenie n-tego wyrazu ciągu Fibonacciego, ograniczyliśmy się do zaprezentowania trzech spośród nich.

Testowanie

We wszystkich przykładach zadeklarowano funkcję Fibonacci(), a następnie jest ona wywoływana w pętli dla argumentów od 0 do 29. Wyniki wyświetlane są w konsoli JavaScript w przeglądarce, która jest dostępna we wszystkich nowoczesnych popularnych przeglądarkach.

Sposób uruchomienia konsoli zależy od przeglądarki i systemu, np. w Google Chrome w systemie Windows lub Linux należy wcisnąć skrót klawiszowy Ctrl+Shift+j, w przypadku Chrome i systemu macOS właściwy skrót klawiszowy to ⌘+⌥+j (command+option+j). Konsolę można uruchomić także z poziomu menu programu, szukaj opcji „Narzędzia dla programistów” lub podobnej.

<script>

	function Fibonacci(n) {
			
	}

	for(i = 0; i < 30; i++) console.log(Fibonacci(i));
			

</script>

Iteracyjnie

Wyznaczanie wyrazu ciągu Fibonacciego metodą iteracyjną polega na obliczeniu kolejnych wartości od 0 do n. W pierwszym przykładzie posłużono się tablicą. Pierwsze dwa wyrazy ciągu wyznaczane w odmienny sposób niż kolejne zostały zainicjalizowane w deklaracji. Następne wyrazy obliczane są w pętli jako suma dwóch poprzednich i przy pomocy metody push() umieszczane na końcu tablicy.

<script>

		function Fibonacci(n) {
			let arr = [0, 1];
            for (let i = 2; i <= n; i++) {
              arr.push(arr[i - 2] + arr[i -1]);
            }
            return arr[n]
		}

	    for(i = 0; i < 30; i++) console.log(Fibonacci(i));

</script>

Drugi przykład również został oparty o iterację, jednak nie występuje w nim tablica. Obliczane wartości wyrazów ciągu zapisywane są w zmiennych i nadpisywane w kolejnych iteracjach pętli.

<script>

	function Fibonacci(n) {
		if(n < 2) return n;
		let a = 0, b = 1;
        for (let i = 2; i <= n; i++) {
            b += a;
            a = b-a;
        }
        return b;
	}

	for(i = 0; i < 30; i++) console.log(Fibonacci(i));

</script>

Rekurencyjnie

Algorytm rekurencyjny wynika wprost z definicji: dla zera wyraz jest równy 0, dla jeden jest równy 1, pozostałe powstają jako suma dwóch poprzednich. Rozwiązanie jest niewydajne, ponieważ wielokrotnie obliczane są te same liczby Fibonacciego.

<script>

		function Fibonacci(n) {
			if(n < 2) return n;
			return (Fibonacci(n - 1) + Fibonacci(n - 2));
		}

		for(i = 0; i < 30; i++) console.log(Fibonacci(i));

</script>

Ze wzoru Bineta

Funkcja napisana z zastosowaniem wzoru Bineta jest najwydajniejsza z prezentowanych przykładów. Więcej na temat obliczania n-tego wyrazu ciągu Fibonacciego metodą opracowaną przez francuskiego matematyka można przeczytać na naszej stronie w artykule „Ciąg Fibonacciego”, czytelnik niezbyt zainteresowany matematyką może ograniczyć się do przekształcenia podanego tam wzoru.

<script>

		function Fibonacci(n) {
			if(n < 2) return n;
			let f = (1 + Math.sqrt(5)) / 2;
			return Math.round((f**n - (f - 1)**n) * Math.sqrt(5) / 5);
		}

		for(i = 0; i < 30; i++) console.log(Fibonacci(i));

</script>
Artykuł: DRAM Speculative Leadoff

DRAM Speculative Leadoff

Artykuł: Burst Mode DMA

Burst Mode DMA

Artykuł: Tryby DMA

Tryby DMA

Artykuł: DMA w kontekście historycznym

DMA w kontekście historycznym

Artykuł: Bezpośredni dostęp do pamięci

Bezpośredni dostęp do pamięci

Nasze technikum

Technik informatyk

Szkoły dla dorosłych

Nasza szkoła

Pełna oferta edukacyjna

Oferta szkoły