1.3 Algorytm A

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

Zadanie 1.3 (2 pkt): rekurencyjny algorytm A wypisuje książkę z przegródki, potem całą "lewą" część pod nią, a na końcu "prawą". To przejście drzewa w kolejności **preorder** (korzeń, lewe poddrzewo, prawe poddrzewo). Dla przykładu 2 arkusz podaje wynik: 10, 2, 1, 5, 15, 13, 25. Uruchom krokowo i obserwuj stos wywołań.

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


def walk(shelf, i, j, out):
    # algorytm A: książka z przegródki, potem lewa i prawa przegródka na półce niżej
    out.append(shelf[(i, j)])
    if (i + 1, 2 * j - 1) in shelf:
        walk(shelf, i + 1, 2 * j - 1, out)
    if (i + 1, 2 * j) in shelf:
        walk(shelf, i + 1, 2 * j, out)
    return out


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

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