Zadanie 1.3, matura czerwiec 2019, informatyka rozszerzona

1 pktzamkniętełatwe (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

1 punkt

Zł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.

Wypróbuj za darmo

5 rozmów · bez karty · Zaloguj się

Sprawdź się

Odpowiedz bezpośrednio w aplikacji

To zadanie może sprawdzić się automatycznie według klucza.

odpowiedź
Zaznacz odpowiedź jedną z opcji.

Jak poszło?

Pokaż rozwiązanieUkryj rozwiązanie

Odpowiedź z klucza CKE

D

Schemat punktowania

1 pkt

za podkreślenie poprawnej odpowiedzi.

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.