Zadanie 1.2, 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, 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.
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
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.