Temat zadania:

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

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

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

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

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) 

Odpowiedź: 9, 2, 12, 10, 14, 13, 15

b) 

Odpowiedź: 10, 8, 4, 6, 15, 12, 13