Zadanie 1.3, 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
1 punktZłożoność czasowa algorytmu opisanego funkcją Rek dla parametrów x = 1, p = 1, k = n jest
- Asześcienna
- Bkwadratowa
- Cliniowa
- Dlogarytmiczna
Wybierz właściwą 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ę
Odpowiedz bezpośrednio w aplikacji
To zadanie może sprawdzić się automatycznie według klucza.
Jak poszło?
Pokaż rozwiązanieUkryj rozwiązanie
Odpowiedź z klucza CKE
D
Schemat punktowania
za podkreślenie poprawnej odpowiedzi.