Zadanie 1.1, matura czerwiec 2019, informatyka rozszerzona

2 pktobliczenioweśrednie (szac.)Czerwiec 2019

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 punkty

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

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.

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

Najmniejsza liczba wywołań: 4

Największa liczba wywołań: 5

Schemat punktowania

2 pkt

za poprawną odpowiedź, w tym:

1 pkt

za podanie największej liczby wywołań (5),

1 pkt

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 ⌈log⁡29⌉=4\lceil \log_2 9 \rceil = 4 czyli 5 wywołań łącznie z pierwszym.

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.