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>
