1. Biblioteczka: wstawianie książek

Matura maj 2023 - Matura z informatyki: arkusze krok po kroku (Python)

**Zadanie 1. Biblioteczka Adama.** Półka \( i \) ma \( 2^i \) przegródek. Książkę wstawia się od przegródki \( B[0, 1] \): pusta przegródka - książka zostaje, zajęta - przy mniejszym numerze idzie do \( B[i + 1, 2j - 1] \), przy większym do \( B[i + 1, 2j] \). To drzewo BST (drzewo poszukiwań binarnych) zapisane na półkach. Biblioteczkę zapisuje tu słownik: klucz to para (półka, przegródka), wartość to numer książki. Przykład wstawia książki z przykładu 2 arkusza: 10, 2, 15, 13, 1, 5, 25. Uruchom krokowo i zobacz, którą drogą idzie każda książka.

def insert(shelf, book):
    # shelf to słownik {(półka, przegródka): numer książki}; brak klucza = pusta przegródka
    i, j = 0, 1
    while (i, j) in shelf:
        if book < shelf[(i, j)]:
            j = 2 * j - 1  # mniejszy numer: lewa przegródka pod spodem
        else:
            j = 2 * j  # większy numer: prawa przegródka pod spodem
        i = i + 1
    shelf[(i, j)] = book


def show(shelf):
    for i in range(max(s for s, j in shelf) + 1):
        row = ["."] * 2 ** i  # półka i ma 2 do potęgi i przegródek
        for (s, j), book in shelf.items():
            if s == i:
                row[j - 1] = str(book)
        print(i, " ".join(row))


shelf = {}
for book in [10, 2, 15, 13, 1, 5, 25]:
    insert(shelf, book)
show(shelf)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.