Zadanie 2.3, matura maj 2021, informatyka rozszerzona
Darmowe konto pozwoli wrócić do niego później.
Zadanie
Zadanie 2. Analiza algorytmu
Niech n będzie nieujemną liczbą całkowitą, a T[1..n] – tablicą zawierającą n liczb całkowitych. Dla n = 0 tablica T jest pusta (nie zawiera żadnego elementu).
Wykonaj analizę poniżej zapisanej funkcji d(x), która rozszerza tablicę T o liczbę całkowitą x, a następnie przeprowadza pewną reorganizację zawartości tej tablicy.
```
d(x):
n ← n + 1
T[n] ← x
s ← n
dopóki ((s div 2) ≥ 1) oraz (T[s] > T[s div 2]) wykonuj
pom ← T[s]
T[s] ← T[s div 2]
T[s div 2] ← pom
s ← s div 2
```
Uwaga: w tym zadaniu przyjmujemy, że:
• tablica T może być powiększana;
• jeśli wartość lewego argumentu operatora oraz jest równa fałsz, to wartość prawego argumentu nie jest wyliczana;
• div jest operatorem oznaczającym część całkowitą z dzielenia.
Polecenie
2 punktyDo początkowo pustej tablicy T wstawiono za pomocą funkcji d kolejno liczby całkowite od 1 do k – 1. Wstawiamy teraz do tablicy T kolejną liczbę k za pomocą d(k).
Zapisz, ile razy w trakcie wykonywania d(k) sprawdzany jest warunek pętli dopóki:
"((s div 2) ≥ 1) oraz (T[s] > T[s div 2])" dla podanych wartości k.
| k | Ile razy sprawdzany jest warunek pętli dopóki podczas wykonywania d(k)? |
|---|---|
| 4 | 3 razy |
| 16 | |
| 1025 |
Miejsce na obliczenia:
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
k = 16: 5 razy
k = 1025: 11 razy
Schemat punktowania
za pełną poprawną odpowiedź.
za poprawną odpowiedź w jednym wierszu.
za podanie odpowiedzi niepoprawnej lub brak odpowiedzi.
Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne, spełniające warunki zadania.