Zadanie 1
Matura z informatyki, maj 2023, poziom rozszerzony
Wymaganie: I.2) do realizacji rozwiązania problemu dobiera odpowiednią metodę lub technikę algorytmiczną i struktury danych. P.I.3) […] stosuje podejście zachłanne i rekurencję. P.I.5) sprawdza poprawność działania algorytmów dla przykładowych danych.
Treść zadania
Zadanie 1. Biblioteczka Adama
Adam przechowuje swoje książki w biblioteczce zbudowanej z półek ponumerowanych kolejno 0, 1, 2, … (zaczynając od półki położonej najwyżej). Półka o numerze i ma 2^i przegródek, ponumerowanych od lewej do prawej liczbami 1, 2, …, 2^i. W jednej przegródce można umieścić tylko jedną książkę. Jako B[i, j] oznaczamy j-tą przegródkę na i-tej półce. Każda książka ma swój numer identyfikacyjny.
Adam ustawia książki, zawsze zaczynając od przegródki B[0, 1], według rekurencyjnej reguły: sprawdza, czy przegródka B[i, j] jest pusta. Jeśli tak, umieszcza w niej książkę. W przeciwnym przypadku porównuje numer wstawianej książki z numerem książki w przegródce: jeśli numer wstawianej książki jest mniejszy, próbuje umieścić ją w przegródce B[i + 1, 2j − 1], a jeśli większy – w przegródce B[i + 1, 2j].
Przykład z arkusza: po wstawieniu do pustej biblioteczki kolejno książek 10, 2, 15, 13, 1, 5, 25 w B[0,1] stoi 10, w B[1,1] i B[1,2] – 2 i 15, w B[2,1], B[2,2] i B[2,3] – 1, 5 i 13, a w B[2,4] – 25.
Zadanie 1.1. (0–2) Podaj zawartość biblioteczki po wstawieniu do niej kolejno książek o numerach: 14, 18, 12, 9, 20, 15, 17. Numery książek wpisz we właściwe miejsca na schemacie.
Zadanie 1.2. (0–3) Uzupełnij tabelkę – wpisz, ile minimalnie, a ile maksymalnie musi być półek w biblioteczce, żeby można było umieścić w niej n książek i żeby na ostatniej półce znalazła się co najmniej jedna książka. W arkuszu podano wiersze dla n = 1 (1 i 1), n = 3 (2 i 3), n = 4 (3 i 4); do uzupełnienia są wiersze dla n = 7, 16 (minimum 5 podano), 31, 32 oraz n = 2^k − 1 (k > 0).
Zadanie 1.3. (0–2) Kolega Adama stwierdził, że wszystkie numery książek można wypisać rekurencyjnym algorytmem A, zaczynając od półki 0 i przegródki 1 (w biblioteczce jest co najmniej jedna książka):
A(i, j)
wypisz numer książki z przegródki B[i, j]
jeżeli przegródka B[i + 1, 2j – 1] nie jest pusta, to
wykonaj A(i + 1, 2j – 1)
jeżeli przegródka B[i + 1, 2j] nie jest pusta, to
wykonaj A(i + 1, 2j)
Dla biblioteczki z przykładu algorytm A wypisze: 10, 2, 1, 5, 15, 13, 25. Podaj ciągi liczb wypisane przez algorytm A dla podanych zawartości biblioteczki:
a) B[0,1] = 9; B[1,1] = 2, B[1,2] = 12; B[2,3] = 10, B[2,4] = 14; B[3,7] = 13, B[3,8] = 15;
b) B[0,1] = 10; B[1,1] = 8, B[1,2] = 15; B[2,1] = 4, B[2,3] = 12; B[3,2] = 6, B[3,6] = 13.
Źródło: arkusz CKE MINP-R0-100-2305. Otwórz oryginalny PDF
Rozwiązanie
Reguła wstawiania to wstawianie do drzewa BST (mniejsze w lewo, większe w prawo): przegródka B[i+1, 2j−1] to lewe dziecko, a B[i+1, 2j] – prawe dziecko przegródki B[i, j].
1.1. Odpowiedź zgodna z zasadami oceniania CKE:
- 14 → B[0,1]
- 18 > 14 → B[1,2]
- 12 < 14 → B[1,1]
- 9 < 14, 9 < 12 → B[2,1]
- 20 > 14, 20 > 18 → B[2,4]
- 15 > 14, 15 < 18 → B[2,3]
- 17 > 14, 17 < 18, 17 > 15 → B[3,6]
półka 0: 14
półka 1: 12 18
półka 2: 9 - 15 20
półka 3: (17 w B[3,6], prawe dziecko 15)
1.2. Odpowiedź z zasad oceniania CKE:
| n | min półek | max półek |
|---|---|---|
| 7 | 3 | 7 |
| 16 | 5 | 16 |
| 31 | 5 | 31 |
| 32 | 6 | 32 |
| 2^k − 1 | k | 2^k − 1 |
Minimum osiągamy, gdy półki wypełniają się od góry bez luk: na p półkach mieści się 2^p − 1 książek, więc potrzeba ⌈log₂(n+1)⌉ półek. Maksimum osiągamy, gdy każda kolejna książka trafia na nową półkę (np. numery wstawiane rosnąco), więc max = n.
1.3. Algorytm A wypisuje najpierw książkę z bieżącej przegródki, potem całe lewe, a następnie prawe poddrzewo (przejście pre-order). Odpowiedź z zasad oceniania CKE:
- a) 9, 2, 12, 10, 14, 13, 15
- b) 10, 8, 4, 6, 15, 12, 13
Uwaga: algorytm A to przejście pre-order (bieżąca przegródka, potem lewe, potem prawe poddrzewo), a nie wypisywanie półka po półce. W 1.1 każdą książkę porównujemy od B[0,1] w dół, aż trafi na pustą przegródkę — 17 trafia aż na półkę 3. W 1.2 „co najmniej jedna książka na ostatniej półce” nie oznacza pełnej ostatniej półki: maksimum to tyle półek, ile książek (każda na osobnej półce).
Strona arkusza CKE z treścią zadania
Rozwiązanie
1.1. Wstawianie 14, 18, 12, 9, 20, 15, 17
Reguła “rodzic B[i,j] → dzieci B[i+1, 2j−1] i B[i+1, 2j]” oznacza pełne drzewo binarne wypełniane poziomami od lewej do prawej.
poziom 0: 14
poziom 1: 18 12
poziom 2: 9 20 15 171.2. Tabelka min/max półek
Minimum: trzeba ⌈log₂(n+1)⌉ poziomów, więc tyle samo półek (poziom 0 to półka 1).
Maksimum: jedna książka na półce — n półek.
| n | min | max |
|---|---|---|
| 7 | 3 | 7 |
| 16 | 5 | 16 |
| 31 | 5 | 31 |
| 32 | 6 | 32 |
| 2^k − 1 | k | 2^k − 1 |
1.3. Algorytm A = pre-order (NLR)
Definicja A(i,j): wypisz B[i,j], potem rekurencyjnie lewe dziecko, potem prawe.
def A(B, i, j):
print(B[i][j])
if (i+1, 2*j-1) in B:
A(B, i+1, 2*j-1)
if (i+1, 2*j) in B:
A(B, i+1, 2*j)- a) 9, 2, 10, 13, 12, 14, 15
- b) 10, 8, 4, 6, 13, 15, 12
Rozumiesz, jak to rozwiązać?
Przećwicz podobne typy zadań w aplikacji
matury-online.pl ma tysiące zadań pogrupowanych po dziedzinach. Sprawdź, czy temat „drzewo binarne, algorytm rekurencyjny, struktury danych, półki z książkami” zrobisz samodzielnie.
Otwórz matury-online.pl