Ciąg Fibonacciego

Wizualizacja pierwszych 7 wyrazów ciągu Fibonacciego

Definicja

Ciąg Fibonacciego jest ciągiem rekurencyjnym. Każdy wyraz, prócz dwóch pierwszych jest sumą dwóch poprzednich wyrazów. Dwa pierwsze wyrazy ciągu Fibonacciego to 1 i 1. Niektóre środowiska twierdzą, że pierwszym wyrazem jest 0. Matematycznie ciąg Fibonnacciego zapisuje się następująco:

Ciąg liczb

Kolejne wyrazy ciągu Fibonacciego to: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ...

Wyliczanie

Przyjmijmy, że Fn oznacza n-tą liczbę Fibonacciego wtedy otrzymujemy, że:

F₁ = F₂ = 1
F₃ = F₂ + F₁ = 1 + 1 = 2
F₄ = F₃ + F₂ = (F₂ + F₁) + F₂ = (1 + 1) + 1 = 3
F₅ = F₄ + F₃ = 3 + 2 = 5
F₆ = F₅ + F₄ = 5 + 3 = 8
F₇ = F₆ + F₅ = 8 + 5 = 13
...

Implementacja

Rozwiązanie iteracyjne

Istnieje możliwość obliczania kolejnych wyrazów ciągu Fibonacciego przy pomocy metody iteracyjnej lub metody rekurencyjnej. Pierwsza z nich reprezentuje kod poniżej. Dla większości osób ta metoda jest prostsza niż rekurencyjna. Tego typu rozwiązanie nadaje się do wypisywania kolejnych wyrazów ciągu, ponieważ rekurencyjna każdy wyraz musiałaby wyliczać od nowa.

1. int fib(int n) {
2.   int a = 0, b = 1, t = 1;
3.   for (int i = 0; i < n; i++) {
4.     t = a;
5.     a = a + b;
6.     b = t;
7.   }
8.   return a;
9. }

(1.) Funkcja fib() przyjmuje jeden argument n, który określa, który wyraz ciągu Fibonacciego program ma wyliczyć. Zwrócona zostanie wartość całkowita, której wartość będzie odpowiadała n-temu wyrazowi ciągu Fibonacciego. (2.) Zadeklarowanie zmiennych: a - początkowo pierwszy wyraz, b - początkowo drugi wyraz oraz t - zmienna pomocnicza. (3.) Wylicz n kolejnych wyrazów: (4.) Zapamiętaj wartość a, a następnie dodaj do a wartość b, a (6.) zapamiętaną wartość a przypisz do zmiennej b. W ten sposób zmienna a zawsze reprezentuje i-ty wyraz, a zmienna b poprzedni. (8.) Na koniec należy zwrócić wartość zmiennej a.

Rozwiązanie rekurencyjne

Rozwiązanie rekurencyjne cechuje się znacznie krótszym kodem, ale pod względem efektywności taki kod nie jest najlepszym rozwiązaniem, ponieważ zużywa bardzo dużo pamięci. Podczas każdego wywołania funkcji deklarowane są kolejne zmienne, które są zwalnianie dopiero jak funkcja zwróci wartość. W przedstawionym rozwiązaniu zostaje przyjęte, że pierwszy wyraz ma indeks 0 i wartość 0.

1. int fib(int n) {
2.   if (n <= 1) {
3.     return n;
4.   } else {
5.     return fib(n - 2) + fib(n - 1);
6.   }
7. }

(1.) Funkcja przyjmuje i zwraca tak samo jak w rozwiązaniu iteracyjnym. (2.) Uwzględniając fakt, że dwa pierwsze wyrazy to 0 i 1 to (2.) funkcja dla wartość n mniejszych od 1: (3.) zwróci wartość n. (4.) Jednak jeśli chodzi o któryś z kolejnych wyrazów to (5.) funkcja zwróci sumą dwóch poprzednich wyrazów.

Rozwiązanie w linijce

Jak wspomniałem wyżej rozwiązanie rekurencyjne pozwala na znaczne zmniejszenie długości kodu. O ile w poprzednim rozwiązaniu nie było tego widać to poniższy kod z pewnością już można za taki uznać:

1. int fib(int n) {
2.   return (n <= 2) ? 1 : fib(n - 1) + fib(n - 2);
3. }

Testowanie funkcji

W celu przetestowania napisanych funkcji można skorzystać z poniższego fragmentu kodu:

1. int main() {
2.   int k;
3.   cout << "Ktory wyraz wypisac? ";
4.   cin >> k;
5.   cout << fib(k) << endl;
6.   system("pause");
7.   return 0;
8. }

• Kod źródłowy Rozwiązanie iteracyjne
• Kod źródłowy Rozwiązanie rekurencyjne
• Kod źródłowy Rozwiązanie w linijce

Ćwiczenia

Zadanie 1

Napisz program, który dla wczytanej liczby naturalnej k wypisze k pierwszych wyrazów ciągu Fibonacciego. Zakładamy, że pierwsze dwa wyrazy to 1 i 1.

Przykładowo dla wartości k = 5 program wypisze na ekran:

1. 1 1 2 3 5

• Kod źródłowy Zadanie 1