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. static 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 nwd() przyjmuje dwa argumenty a i b. (2.) Dopóki oba argumenty są różne to (3. - 7.) należy odjąć mniejszą liczbę od większej. Na koniec (9.) wystarczy zwrócić a lub b. Jest to szukana wartość NWD(a, b). Warto zauważyć, że funkcja napotyka problem kiedy jedna z wartości wynosi 0. Wtedy program będzie działał w nieskończoność, ponieważ 0 nie będzie zmieniać wartości drugiej zmiennej, która będzie dodatnia, ponieważ wiadomo, że a i b należą do liczb naturalnych.

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. static int fib(int n) {
2.   if (n <= 1) {
3.     return n;
4.   } else {
5.     return fib(n - 2) + fib(n - 1);
6.   }
7. }

(2.) Zmienna c pozwoli zapamiętać wynik a % b. (3.) Dopóki b jest różne od 0 to: (4.) zapisujemy w c wynik resztę z dzielenia a przez b. Jak wiadomo wynik tej operacji da liczbę, która będzie zarówno mniejsza od a jak i od b, dlatego wystarczy (5.) wartość b przypisać do a, a następnie (6.) bwartość c. W ten sposobób b < a, a co za tym idzie jeśli a = b to reszta z dzielenia a przez b to 0, a wtedy pętla zostaje przerwana, a a zawiera NWD(a, b).

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. static 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. static void Main(string[] args) {
2.   int k;
3.   Console.Write("Ktory wyraz wypisac? ");
4.   k = Convert.ToInt32(Console.ReadLine());
5.   Console.WriteLine(fib(k));
6.   Console.ReadKey();
7. }

• 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