aplikacja Matura google play app store

zadania z informatyki - Analiza algorytmów

Zadanie: 1 2 3 4 5 6 7 8 9 10
Zadanie 8.
Wiązka zadań Dwa ciągi
Niech A[1..n] i B[1..n] będą uporządkowanymi rosnąco tablicami liczb całkowitych i niech x będzie liczbą całkowitą. Rozważmy następujący algorytm:

i←1
jn
dopóki (in oraz j > 0) wykonuj

dopóki (in oraz j > 0) wykonuj
(*) jeżeli A[i] + B[j] = x
podaj wynik PRAWDA i zakończ algorytm
w przeciwnym razie
jeżeli A[i] + B[j] < x
ii + 1
w przeciwnym razie
jj – 1
podaj wynik FAŁSZ
Zadanie 8.1.
Uzupełnij poniższą tabelę. Podaj wynik działania algorytmu oraz liczbę porównań wykonanych w wierszu oznaczonym (*).

Tablica A

Tablica B

x

Wynik działania algorytmu

Liczba porównań w kroku (*)

3, 5, 12, 17

8, 10, 13, 14

21

 

 

4, 6, 8, 10

5, 7, 9, 11

13

 

 


Zadanie 8.2.
Przeanalizuj działanie zaprezentowanego algorytmu i uzupełnij poniższą specyfikację.

Dane:
n — dodatnia liczba całkowita
A[1..n], B[1..n] — n-elementowe tablice liczb całkowitych, posortowane rosnąco
x — liczba całkowita
Wynik:
PRAWDA, gdy .........................
FAŁSZ, gdy .........................
Zadanie 8.3.
Podaj przykład pięcioelementowych tablic A i B, dla których przy x = 20 algorytm wykona sześć porównań w wierszu (*), a wynikiem będzie PRAWDA.
Poprzednia strona Następna strona

źródło: CKE
Polityka Prywatności