Darmowe konto pozwoli wrócić do niego później.
Polecenie
Dana jest dodatnia liczba całkowita n oraz uporządkowana rosnąco tablica różnych liczb całkowitych T[1..n]. Przeanalizuj następującą funkcję rekurencyjną, której parametrami są liczby całkowite x, p, k, przy czym
Darmowe konto pozwoli wrócić do niego później.
Rek(x, p, k)
jeżeli
s ← (p + k) div 2
jeżeli T[s] ≥ x
wynikiem jest Rek(x, p, s)
w przeciwnym razie
wynikiem jest Rek(x, s + 1, k)
w przeciwnym razie
jeżeli T[p] = x
wynikiem jest p
w przeciwnym razie
wynikiem jest −1
Uwaga: div jest operatorem oznaczającym część całkowitą z dzielenia.
Podaj największą i najmniejszą możliwą liczbę wywołań funkcji Rek w wyniku wywołania Rek(2019, 6, 14) dla n = 17 i pewnej, uporządkowanej rosnąco tablicy T[1..17] różnych liczb całkowitych.
Uwaga: Pierwsze wywołanie funkcji Rek(2019, 6, 14) włączamy do ogólnej liczby wywołań.
Najmniejsza liczba wywołań: 4
Największa liczba wywołań: 5
Wyjaśnienie: Algorytm realizuje wyszukiwanie binarne. Dla przedziału [6, 14] mamy 9 elementów. Najmniejsza liczba wywołań (4) występuje, gdy element znajduje się szybko. Największa liczba wywołań (5) występuje w przypadku pesymistycznym, gdy trzeba zawęzić przedział do jednego elementu.
za podanie największej liczby wywołań (5) – 1 punkt, za podanie najmniejszej liczby wywołań (4) – 1 punkt.
Algorytm to wyszukiwanie binarne. W każdym kroku przedział jest dzielony na pół, zatem liczba wywołań zależy od głębokości rekurencji. Dla przedziału 9 elementów maksymalna głębokość to czyli 5 wywołań łącznie z pierwszym.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.