Zadanie 2.2, matura czerwiec 2018, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 2. Liczby Fibonacciego
Liczby Fibonacciego są definiowane w następujący sposób:
F1 = 1, F2 = 1,
Fn = Fn−1 + Fn−2 dla n = 3, 4, …
Rekurencyjny algorytm, który służy do obliczania wartości Fn 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)
```
Polecenie
1 punktAby obliczyć F45, 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.
Odpowiedź:
Korepetytor
Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.
5 rozmów · bez karty · Zaloguj się
Sprawdź się
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
Drzewo wywołań rekurencyjnych zawiera wielokrotne wywołanie tych samych wyrazów co powoduje wielokrotne ich obliczanie. Im dalszy wyraz Fibonacciego jest obliczany, tym jest więcej takich powtórzeń. Co daje złożoność wykładniczą od n.
Schemat punktowania
za poprawną odpowiedź
za podanie odpowiedzi błędnej albo brak odpowiedzi.
Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.