Algorytmy, C++, Matura z informatyki - nauka i materiały.

Ciąg Fibonacciego C++ – implementacja

Ciąg Fibonacciego C++

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ęzyku C++.

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 chą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… [edit]Wikipedia rozwiała moje wątpliwości.[/edit]

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 ado a10 prezentują się następująco:

Ciąg Fibonacciego C++

 

Ciąg Fibonacciego C++ – implementacja

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.

 

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ą. Zachęcam do przeczytania więcej na ten temat.

Dodaj komentarz