1.1. Wstawianie książek do biblioteczki

Wprowadzenie

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ⁱ 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, …, 2ⁱ. 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]

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 ≤ 2ⁱ) 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).

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

Polecenie

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 poniższym schemacie.