Ciąg Fibonacciego | Korepetycje do matury z informatyki - Maurycy Gast

Ciąg Fibonacciego

Jednym z zagadnień, które można określić jako podstawowe w zgłębianiu tajników algorytmiki, jest ciąg Fibonacciego. Pierwotnie został on opracowany przez włoskiego matematyka Leonarda z Pizy, który opisał przy jego pomocy proces rozmnażania się populacji królików. Warto jest ten ciąg poznać i zrozumieć, gdyż pozwala on na polepszenie zrozumienia różnic pomiędzy rekurencyjną a iteracyjną metodą konstruowania algorytmów. Oprócz tego jest całkiem duża szansa, że natkniecie się na niego na maturze z informatyki oraz na studiach.

Z ciągiem Fibonacciego zetkniemy się również w dziedzinach pozainformatycznych. W biologii przy pomocy liczb Fibonacciego opiszemy naturalne linie spiralne spotykane w roślinach. Wynika to z tego, że kąt wyrastania nowych organów (np. łodyg czy liści) jest równy proporcji, którą opisuje iloraz dwóch kolejnych liczb z ciągu Fibonacciego (a im większe liczby z ciągu weźmiemy na warsztat, tym dokładniejszą proporcję uzyskamy). Zależność tę nazywamy: „złotym kątem”.

Innym przykładem jest sztuka: kompozytorzy czasem tworzą swoje utwory w oparciu o zależności wyprowadzone z relacji pomiędzy kolejnymi liczbami Fibonacciego, zaś malarze potrafią planować rozłożenie elementów na obrazie w oparciu o estetykę odnoszącą się do tzw. „złotego podziału”. Fibonacciego znajdziemy nawet na giełdzie, gdzie inwestorzy czasem wykorzystują zniesienia Fibonacciego przy szacowaniu korekt cen instrumentów finansowych.

Podstawowa zasada jest następująca: każda kolejna liczba ciągu jest sumą dwóch poprzednich wyrazów ciągu. Dlatego pierwsze dwie liczby musimy zdefiniować sami, zaś kolejne będą wynikać z poprzednich. Zakładamy, że są one równe 1. W takim razie:

F1 = 1

F2 = 1

Fn = Fn-1 + Fn-2

Z powyższego wzoru wynika, że początek ciągu będzie wyglądał następująco:

F = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987…}

Z punktu widzenia matury najważniejsza jest kwestia skonstruowania odpowiedniego algorytmu, który będzie wyliczał dla nas wartości konkretnych elementów ciągu. Musimy ten algorytm rozumieć na tyle, aby móc również rozwiązać zagadki oparte na ciągach zbliżonych do Fibonacciego. CKE często traktuje bazowy ciąg Fibonacciego jako inspirację pod algorytmy proponowane w zadaniach, np. musimy być też gotowi na zrobienie podobnego ciągu, lecz opartego na sumowaniu trzech poprzednich elementów (taki ciąg nazywamy ciągiem „Tribonacciego”). Omówmy wpierw wersję rekurencyjną algorytmu, a więc wprost wynikającą z definicji.

ciąg fibonacciego c++
W ciągu Fibonacciego, w którym każdy kolejny wyraz jest sumą dwóch poprzednich.

Algorytm rekurencyjny

Wariant rekurencyjny jest wersją prostszą w zapamiętaniu. Właściwie sprowadza się do przepisania definicji na język, w którym programujemy, oraz osadzenie jej w funkcji. Zwróć uwagę że definicje matematyczne bardzo często są łatwe w implementacji rekurencyjnej.

W algorytmie zakładamy, że argument n na wejściu jest numerem wyrazu ciągu, który chcemy otrzymać w wyniku.

C++

int Fib(int n) {
	if (n == 1 or n == 2){
		return 1;
	}
	else {
		return Fib(n - 1) + Fib(n - 2);
	}
}

Python

def Fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return Fib(n - 1) + Fib(n - 2)

Algorytm iteracyjny

Cechą charakterystyczną tej wersji algorytmu jest to, że musimy wykorzystać w nim dodatkowe zmienne pomocnicze. Jest to konieczne, aby w trakcie wykonywania kolejnych operacji nie zgubić żadnej z wartości. Algorytm jest o tyle niewygodny, że wymaga takiego swoistego „wachlowania” wartościami zmiennych.

W przykładzie posłużymy się następującymi zmiennymi: a i b będą służyły do przechowywania poprzedniego oraz bieżącego wyrazu ciągu przy założeniu, że b przechowuje właściwy wynik dla każdej iteracji (a więc co do zasady będzie „tą większą liczbą”). Żeby operacja była możliwa, musimy również przy każdym powtórzeniu przechować jej wartość tak, aby na skutek wyliczania kolejnej sumy, nie utracić jej wartości, bowiem przy kolejnej iteracji to „ta większa” będzie musiała stać się „tą mniejszą”. Wykorzystamy do tego zmienną temp (skrót od temporary czyli tymczasowa).

Tak samo jak w wersji rekurencyjnej, zakładamy, że argument n na wejściu jest numerem wyrazu ciągu, który chcemy otrzymać w wyniku.

C++

int Fib(int n) {
	int temp;
	int a = 1;
	int b = 1;
	for (int i = 2; i < n; i++) {
		temp = b;
		b = a + b;
		a = temp;
	}
	return b;
}

Python

def Fib(n):
    a = 1
    b = 1
    for i in range(2, n):
        temp = b
        b = a + b
        a = temp
    return b

Jeżeli opracujesz i w pełni zrozumiesz obie wersje algorytmu, bez problemu poradzisz sobie również z ciągami podobnymi do ciągu Fibonacciego. Zadania tego typu możesz napotkać zarówno w części teoretycznej jak i praktycznej egzaminu, więc nigdy nie ucz się algorytmów na pamięć – najważniejsze jest ich zrozumienie. Bądź też gotowy do wykorzystania zarówno wersji rekurencyjnej jak i iteracyjnej. Może być bowiem tak, że w części teoretycznej natrafisz na polecenie, które już na wstępie precyzuje, w jakiej wersji algorytm musisz skonstruować. Dlatego nigdy nie pomijaj zagadnień niewygodnych, lecz wykorzystaj je, aby poszerzyć swoje umiejętności.

Wpisy, które mogą Cię zainteresować:



Dodaj komentarz

kurs maturalny informatyka