Zadanie 1.3, matura maj 2023, informatyka rozszerzona

2 pktotwarteśrednie 63%Maj 2023

Darmowe konto pozwoli wrócić do niego później.

Zadanie

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 2i przegródek, w których umieszczane są książki. W jednej przegródce można umieścić tylko jedną książkę. Przegródki na i-tej półce są ponumerowane od lewej do prawej kolejnymi liczbami 1, 2, 3, …, 2i.

Jako B[i, j] oznaczamy j-tą przegródkę na i-tej półce.

Przykład 1.

Szara komórka to przegródka B[3, 4]

Materiał graficzny do zadaniaPowiększ
Materiał graficzny do zadania

Każda książka ma swój numer identyfikacyjny. Adam ustawia książki na półkach, zawsze zaczynając od przegródki B[0,1]. Stosuje przy tym następującą, rekurencyjną regułę:

Adam sprawdza, czy przegródka B[i, j] (i ≥ 0 oraz 1 ≤ j ≤ 2i) jest pusta. Jeśli tak, umieszcza książkę w tej przegródce. W przeciwnym przypadku porównuje numer wstawianej książki z numerem książki w przegródce. Jeśli numer wstawianej książki jest mniejszy od numeru książki stojącej w przegródce, próbuje umieścić książkę na kolejnej półce w przegródce B[i + 1, 2j – 1]. Jeśli numer wstawianej książki jest większy od numeru książki w przegródce, to próbuje umieścić książkę w przegródce B[i + 1, 2j].

Przykład 2.

Poniżej przedstawiono zawartość biblioteczki po wstawieniu do niej książek kolejno o numerach: 10, 2, 15, 13, 1, 5, 25 (zakładamy, że przedtem biblioteczka była pusta).

Materiał graficzny do zadaniaPowiększ
Materiał graficzny do zadania

Przykład 3.

Poniżej przedstawiono zawartość biblioteczki po wstawieniu do niej książek kolejno o numerach: 1, 5, 10, 15, 2, 25, 13 (zakładamy, że przedtem biblioteczka była pusta).

Materiał graficzny do zadaniaPowiększ
Materiał graficzny do zadania

Polecenie

2 punkty

Kolega Adama, oglądający biblioteczkę, stwierdził, że aby wypisać wszystkie numery książek umieszczonych na półkach, można posłużyć się podanym poniżej rekurencyjnym algorytmem A, którego działanie rozpoczynamy od półki o numerze 0 i od przegródki o numerze 1. Zakładamy przy tym, że w biblioteczce jest co najmniej jedna książka.

```text

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 siedmioma książkami z przykładu 2. algorytm A wypisze: 10, 2, 1, 5, 15, 13, 25.

Podaj ciągi liczb wypisane przez algorytm A dla podanych zawartości biblioteczki.

a)

Materiał graficzny do zadaniaPowiększ
Materiał graficzny do zadania

Odpowiedź:

b)

Materiał graficzny do zadaniaPowiększ
Materiał graficzny do zadania

Odpowiedź:

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

a) 9, 2, 12, 10, 14, 13, 15

b) 10, 8, 4, 6, 15, 12, 13

Schemat punktowania

2 pkt

odpowiedź poprawna.

1 pkt

odpowiedź poprawna dla jednego podpunktu.

0 pkt

odpowiedź niepoprawna albo brak odpowiedzi.

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.