Zadanie 2.2, matura czerwiec 2018, informatyka rozszerzona

1 pktotwarteśrednie (szac.)Czerwiec 2018

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 punkt

Aby 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.

Wypróbuj za darmo

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

1 pkt

za poprawną odpowiedź

0 pkt

za podanie odpowiedzi błędnej albo brak odpowiedzi.

Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne i spełniające warunki zadania.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.