Darmowe konto pozwoli wrócić do niego później.
Polecenie
Zadanie 1. Wyszukiwanie liczb
Funkcja F(T, x) przyjmuje jako argumenty tablicę T, w której znajdują się liczby całkowite uporządkowane niemalejąco, oraz liczbę całkowitą x, którą ma wyszukać w tablicy.
Dane:
n – liczba elementów tablicy, n > 0
T[1...n] – n-elementowa tablica zawierająca liczby całkowite uporządkowane niemalejąco
x – liczba całkowita poszukiwana w tablicy T
Darmowe konto pozwoli wrócić do niego później.
prawda – jeśli liczba x występuje w tablicy T, fałsz – w przeciwnym razie
funkcja F(T,x)
p ← 1
k ← n
dopóki p <= k powtarzaj:
s ← (p+k) div 2
jeśli T[s] = x to
wynikiem jest prawda
zakończ działanie funkcji
w przeciwnym razie
jeśli T[s] < x to p ← s+1
w przeciwnym razie k ← s-1
wynikiem jest fałsz
Uwaga: zapis div oznacza dzielenie całkowite
Zadanie 1.1.
Rozważmy tablicę T = [3; 5; 7; 8; 9; 13; 33; 37; 40; 43].
A. Podaj wynik funkcji F(T, x) dla liczby x=7.
B. Podaj, ile razy nastąpi modyfikacja wartości zmiennej p, a ile razy zmiennej k podczas wykonywania pętli dopóki dla x = 7 oraz dla x = 43.
C. Podaj kolejne wartości zmiennej s, jakie będzie ona przyjmowała dla x = 7.
1.1.A. prawda
1.1.B.
Zmienna | x=7 | x=43
p | 1 | 3
k | 1 | 0
1.1.C. 5, 2, 3
za podanie poprawnych odpowiedzi, w tym:
za poprawną odpowiedź w zadaniu 1.1.A
za poprawną odpowiedź w zadaniu 1.1.B (w tym po 1 pkt za każdą kolumnę tabeli)
za poprawną odpowiedź w zadaniu 1.1.C
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.