Zadanie 1.2, 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, jakie będą wartości parametrów przekazywanych do funkcji Rek w kolejnych jej wywołaniach dla n = 11, tablicy T = [1, 5, 8, 10, 12, 14, 19, 20, 23, 30, 38] oraz pierwszego wywołania Rek(37, 1, 11).

Miejsce na obliczenia

Kolejne wywołania:

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

```

Rek(37,7,11)

Rek(37,10,11)

Rek(37,11,11)

```

Schemat punktowania

2 pkt

za 3 kolejne poprawne wywołania; 1 pkt – za 2 kolejne poprawne wywołania.

Komentarz. Algorytm to wyszukiwanie binarne szukające liczby 37. Ponieważ 37 > T[10] = 30, zawsze poruszamy się w prawo.

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.