aplikacja Matura google play app store

zadania z informatyki - Praktyka w teorii

Zadanie: 1 2 3 4 5 6 7 8 9 10
Zadanie 9.
Wiązka zadań Podział tablicy

Rozważamy następujący algorytm.

Dane:
tablica liczb naturalnych T[1..n]

Algorytm:
x ← T[1]
i ← 0
j ← n+1
wykonuj
wykonuj
j ← j-1
(*) dopóki T[j] > x
wykonuj
i ← i+1
(**) dopóki T[i] < x
jeżeli i < j
(***) zamień(T[i] T[j])
w przeciwnym razie
zakończ

Uwaga: funkcja zamień(T[i], T[j]) zamienia miejscami wartości T[i] oraz T[j].
Zadanie 9.1.
Przeanalizuj działanie algorytmu i podaj łączną liczbę operacji porównania, jakie zostaną wykonane w wierszach oznaczonych (*) i (**) dla danych zapisanych w poniższej tabeli:

Tablica T

Liczba operacji porównania wykonanych w wierszu oznaczonym (*)

Liczba operacji porównania wykonanych w wierszu oznaczonym (**)

4, 2, 5, 8, 1, 9, 7, 6, 3

 

 

5, 4, 3, 2, 1, 6, 7, 8, 9, 10

 

 

1, 2, 3, ... , 100

 

 

100, 99, 98, ... , 1

 

 

Zadanie 9.2.
Przeanalizuj działanie algorytmu i podaj łączną liczbę operacji zamiany, jakie zostaną wykonane w wierszu oznaczonym (***) dla danych zapisanych w poniższej tabeli:

Tablica T

Liczba operacji zamiany wykonanych w wierszu oznaczonym (***)

4, 2, 5, 8, 1, 9, 7, 6, 3

 

5, 4, 3, 2, 1, 6, 7, 8, 9, 10

 

1, 2, 3, ... , 100

 

100, 99, 98, ... , 1

 

Poprzednia strona Następna strona

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