Sama postać i wzór rekurencyjny tego ciągu liczb naturalnych jakim jest ciąg Fibonacciego nie jest niczym nadzwyczajnym. Niesamowite natomiast jest przełożenie tego ciągu na otaczającą nas przyrodę. Jak bowiem nie dziwić się faktowi, że króliki rozmnażają się wedle założeń Włocha 😉 Zapraszam do zapoznania się z implementacją ciągu Fibonacciego w językach C++, Java i Python.
Ciąg Fibonacciego – występowanie w przyrodzie i wzór
Nie mam pojęcia jak włoski matematyk – Leonardo Fibonacci z Pizy, wpadł na pomysł zapisania zależności tego ciągu. Może zainspirował go świat przyrody? Może chcąc dorównać perfekcji ślimaczej muszli i doskonałości zwyczajnej szyszki, poświęcił kawał życia na obserwację przyrody i zanotowywanie porządku w jakim na świat przychodzą pszczoły? Kto wie…
Znany natomiast jest wzór rekurencyjny, za pomocą którego definiowany jest ciąg Fibonacciego. Ciąg z założenia zakłada, że jego pierwszy element ma wartość 0, kolejny 1, a każdy z następnych wyrazów ciągu jest sumą dwóch poprzednich. Stąd trzeci wyraz ciągu będzie sumą pierwszego i drugiego: 0+1=1. Czwarty wyraz za to będzie sumą dwóch jedynek, dlatego sam będzie równy 2. Wzór rekurencyjny ciągu przedstawia się następująco:
- a0=0
- a1=1
- an=an-1+an-2
Wyrazy ciągu Fibonacciego od a0 do a10 prezentują się następująco:
Ciąg Fibonacciego – implementacje
Program do wypisywania kolejnych wyrazów ciągu Fibonacciego postanowiłem zrobić z wykorzystaniem funkcji iteracyjnej zamiast rekurencyjnej mimo, że sam wzór ciąg jest rekurencyjny. Dlaczego tak? Dlatego, że funkcja rekurencyjna w przypadku ciągów jest gorszym wyborem, nieoptymalnym. Złożoność pamięciowa potrafi być szalenie wysoka. Dla kilku pierwszych wyrazów ciągu może to nie być tak odczuwalne, ale z czasem program może zacząć się, że tak powiem krztusić. Myślę, że temat złożoności algorytmów powinienem jeszcze poruszyć w kontekście matury z informatyki.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// program do wyznaczania wyrazów ciągu od a(0) do a(n) wyrazów ciągu Fibonacciego // Kosiński Łukasz #include <iostream> using namespace std; void fib(unsigned n) { long long i=0, j=1;//dwa pierwsze wyrazy ciągu for(int k=0; k<n; k++) //za k określamy aktualny numer ciągu w pętli { if(k==0) cout << i << " ";//wyraz o numerze 0, czyli pierwszy ciagu rowny jest 0 if(k==1) cout << j << " ";//natomiast drugi wyraz o numerze 1 wynosi 1 else { j+=i;//nowy wyraz to suma dwoch poprzednich, czyli suma wyrazow u numerach k-1 i k-2 i=j-i;//zmieniamy wartosc dotychczasowa zmiennej i na taką, jaką przed momentem miała zmienna j cout << j << " "; } } } int main() { unsigned x; cin>>x; fib(x); system("pause"); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.Scanner; public class Fibonacci { public static void main(String[] args) { System.out.println("Program wypisujący wyrazy ciągu Fibonacciego"); System.out.println("Podaj liczbę wyrazów do wypisania: "); Scanner scanner = new Scanner(System.in); // inicjalizacja skanera, który będzie pobierał wartości zmiennych int n = scanner.nextInt(); // pobieramy liczbe od uzytkownika int k = 1, l = 1; //dwa pierwsze wyrazy ciągu System.out.print("| 1 | 1 |"); //wypisujemy pierwsze dwa wyrazy for(int i=3; i<= n; i++) //zaczynamy iteracje od trzeciego wyrazu ciągu { int p = l; //zmienna pomocnicza do zamiany l = k + l; //dodajemy dwa ostatnie wyrazy k = p; // a nastepnie przesuwamy o jeden System.out.print(" " + l + " |"); // i wypisujemy do konsoli } scanner.close(); //zwalniamy zasoby } } |
Python
|
1 2 3 4 5 6 7 8 9 10 |
def fibonacci(x): wyraz1 = 1 wyraz2 = 1 for i in range(3, x+1): wyraz2, wyraz1 = wyraz1+wyraz2, wyraz2 print(wyraz2) print("Program liczacy wartosc wyrazu n ciagu Fibonacciego") print("Podaj liczbe n") n = int(input()) #pobieramy liczbe fibonacci(n) |
Ciekawostką dotyczącą ciągu Fibonacciego jest fakt, iż stosunek jego wyrazów tworzy tzw. „złotą proporcję”, która ponoć ma odzwierciedlenie praktycznie wszędzie. Nasz umysł działa tak, że rzeczy wykorzystujące złotą liczbę Φ bardziej nam się podobają.
