Zadanie 2.3, matura maj 2021, informatyka rozszerzona

2 pktobliczenioweśrednie 40%Maj 2021

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 punkty

Do 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.

kIle razy sprawdzany jest warunek pętli dopóki podczas wykonywania d(k)?
43 razy
16
1025

Miejsce na obliczenia:

Korepetytor

Nie wiesz, jak ruszyć? Korepetytor zna to zadanie i poprowadzi Cię krok po kroku, bez gotowca.

Wypróbuj za darmo

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

2 pkt

za pełną poprawną odpowiedź.

1 pkt

za poprawną odpowiedź w jednym wierszu.

0 pkt

za podanie odpowiedzi niepoprawnej lub brak odpowiedzi.

Uwaga: Akceptowane są wszystkie odpowiedzi merytorycznie poprawne, spełniające warunki zadania.

Umiejętności w zadaniu

Pliki cookies

Zapisujemy na Twoim urządzeniu to, bez czego serwis nie działa, np. zalogowanie. Plików analitycznych użyjemy tylko za Twoją zgodą. Szczegóły w polityce prywatności.