Zadanie 1. Liczby Fibonacciego

Liczby Fibonacciego są definiowane w następujący sposób:

FIndeks dolny 11 = 1, FIndeks dolny 22 = 1,

FIndeks dolny nn = FIndeks dolny n - 1 Indeks dolny koniecn - 1 + FIndeks dolny n - 2 Indeks dolny koniecn - 2 dla $n$ = 3, 4, …

Rekurencyjny algorytm, który służy do obliczania wartości $F_n$ dla dowolnego n >= 1, można zapisać następująco:

funkcja F(n)
	jeśli n = 1 lub n = 2:
		wynikiem jest 1
	w przeciwnym razie:
		wynikiem jest F(n - 1) + F(n - 2)

Zadanie 1.1

Zapisz w wybranej przez siebie notacji (w języku programowania lub w pseudokodzie) algorytm iteracyjny, który służy do obliczania wartości liczby $F_n$ dla dowolnego $n$ ≥ 1. Algorytm nie może używać tablic.

Przykładowe rozwiązanie:

Mamy przedstawić algorytm, który będzie obliczać wartość elementu ciągu Fibonacciego o podanym indeksie. Posłużymy się techniką iteracyjną (czyli wykonamy określoną liczbę powtórzeń pewnych czynności).

1. Definiujemy zmienną indeks, która będzie przechowywać indeks wyliczanego elementu ciągu:

indeks ← n

2. Piszemy instrukcję warunkową umożliwiającą obliczenie wartości pierwszego lub drugiego elementu ciągu Fibonacciego. W obu przypadkach podajemy wówczas wartość 1:

indeks ← n

jeżeli indeks = 1 lub indeks = 2:
	wypisz(1)
w przeciwnym razie:

3. Aby obliczyć wartość elementu o indeksie numer 3 lub wyższym, stosujemy iteracjęiteracjaiterację. Tworzymy najpierw trzy zmienne:

   • aktualna – przechowuje wartość wyliczoną dla obecnego indeksu,

   • poprzednia – przechowuje wartość elementu o indeksie niższym o 1,

   • bPoprzednia – przechowuje wartość elementu o indeksie niższym o 2.

indeks ← n

jeżeli indeks = 1 lub indeks = 2:
	wypisz(1)
w przeciwnym razie:
	aktualna ← 0
	poprzednia ← 1
	bPoprzednia ← 1

4. Tworzymy pętlę dla, w której będą obliczane wartości kolejnych elementów ciągu Fibonacciego (licznik pętli inicjujemy wartością 3, ponieważ dwa pierwsze elementy ciągu już znamy):

indeks ← n

jeżeli indeks = 1 LUB indeks = 2:
	wypisz(1)
w przeciwnym razie:
	aktualna ← 0
	poprzednia ← 1
	bPoprzednia ← 1
    
	dla i = 3, 4, ..., indeks wykonuj:

5. Wewnątrz pętli wykonane zostaną trzy działania:

   1. obliczenie wartości elementu ciągu o aktualnym indeksie (suma dwóch poprzednich elementów);

   2. wartość o indeksie niższym o 1 na potrzeby następnego cyklu pętli stanie się wartością o indeksie niższym o 2;

   3. wartość aktualna na potrzeby następnego cyklu pętli stanie się wartością o indeksie niższym o 1.

indeks ← n

jeżeli indeks = 1 LUB indeks = 2:
	wypisz(1)
w przeciwnym razie:
	aktualna ← 0
	poprzednia ← 1
	bPoprzednia ← 1
    
	dla i = 3, 4, ..., indeks wykonuj:
		aktualna ← poprzednia + bPoprzednia
		bPoprzednia ← poprzednia
		poprzednia ← aktualna
        
	wypisz(aktualna)

Schemat oceniania:

• 2 p. – za poprawny algorytm (w tym za prawidłowe zapisanie warunków początkowych i iteracji 1 p.).

• 1 p. – za zapamiętanie tylko dwóch poprzednich wyrazów ciągu.

• 0 p. – za podanie odpowiedzi błędnej albo brak odpowiedzi.

Za przedstawione rozwiązanie zadania otrzymalibyśmy 2 punkty, ponieważ prawidłowo zapisane zostały warunki początkowe (dla indeksów 1 i 2) oraz pętla iteracyjna.

Zadanie 1.2

Aby obliczyć $F_{45}$, wywołano najpierw funkcję iteracyjną, a potem – rekurencyjną. Okazało się, że czas trwania obliczeń realizowanych przez funkcję rekurencyjną był długi, podczas gdy funkcja iteracyjna prawie natychmiast podała wynik. Uzasadnij długi czas działania funkcji rekurencyjnej.

Przykładowe rozwiązanie:

Jedną z lepszych wizualizacji rekurencji jest zapisanie jej w postaci drzewa, w którym poszczególne wywołania funkcji uruchamiają kolejne jej wywołania (aż do napotkania przypadku podstawowego). Wielokrotne wywoływanie powoduje wielokrotne obliczanie tych samych wartości. Poszczególne elementy ciągu Fibonacciego wyliczane są zatem bez brania pod uwagę wyrazów już znanych. Za każdym razem funkcja rekurencyjna dochodzi do przypadku podstawowego. Ponadto im dalszy wyraz ciągu Fibonacciego ma zostać obliczony, tym więcej powtórzeń jest wykonywanych. Z tego powodu taka technika okazuje się wolniejsza od metody iteracyjnej i daje złożoność wykładniczą od n.

Schemat oceniania:

• 1 p. – za poprawną odpowiedź.

• 0 p. – za podanie odpowiedzi błędnej albo brak odpowiedzi.

Nasza odpowiedź jest trochę obszerniejsza niż ta przedstawiona w arkuszu sporządzonym przez CKE, ale wyjaśnia powód wolniejszego działania algorytmu rekurencyjnego. W rezultacie na egzaminie otrzymalibyśmy 1 punkt.

Słownik