Ciąg Fibonacciego – implementacje

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…



Jeżeli chcesz zwiększyć swojego programistycznego skilla, zachęcam do sprawdzenia tego tytułu

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:

  1. a0=0
  2. a1=1
  3. an=an-1+an-2

Wyrazy ciągu Fibonacciego od ado a10 prezentują się następująco:

Ciąg Fibonacciego C++

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++

Java

Python

grupa wsparcia matura z informatyki

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ą.

You Might Also Like
Dodaj komentarz

icon