Zadanie 1.1, matura czerwiec 2019, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 1. Rekurencja
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 1 ≤ p ≤ k ≤ n.
```
Rek(x, p, k)
jeżeli p < k
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.
Polecenie
2 punktyPodaj 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ń.
Miejsce na obliczenia
Odpowiedź:
najmniejsza liczba wywołań
największa liczba wywołań
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
Najmniejsza liczba wywołań: 4
Największa liczba wywołań: 5
Schemat punktowania
za poprawną odpowiedź, w tym:
za podanie największej liczby wywołań (5),
za podanie najmniejszej liczby wywołań (4).
Komentarz. 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.