Zadanie 1.2, matura maj 2023, informatyka rozszerzona
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]
PowiększKaż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).
PowiększPrzykł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).
PowiększPolecenie
3 punktyUzupeł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.
| n – liczba książek | Minimalna liczba półek | Maksymalna liczba półek |
|---|---|---|
| 1 | 1 | 1 |
| 3 | 2 | 3 |
| 4 | 3 | 4 |
| 7 | ||
| 16 | 5 | |
| 31 | ||
| 32 | ||
| 2k − 1, dla k > 0 |
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
| n – liczba książek | Minimalna liczba półek | Maksymalna liczba półek |
|---|---|---|
| 1 | 1 | 1 |
| 3 | 2 | 3 |
| 4 | 3 | 4 |
| 7 | 3 | 7 |
| 16 | 5 | 16 |
| 31 | 5 | 31 |
| 32 | 6 | 32 |
| 2k − 1 | k | 2k − 1 |
Schemat punktowania
odpowiedź w całości poprawna.
odpowiedź poprawna w przynajmniej 4 wierszach.
odpowiedź poprawna w jednej kolumnie albo w przynajmniej 3 wierszach.
odpowiedź niepoprawna albo brak odpowiedzi.