1.2 Najmniej i najwięcej półek

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

Zadanie 1.2 (3 pkt): ile najmniej, a ile najwięcej półek zajmie \( n \) książek. **Najwięcej**: książki wstawiane rosnąco idą zawsze w prawo, każda o półkę niżej, więc \( n \) książek zajmuje \( n \) półek. **Najmniej**: półki zapełnione do pełna, a na półkach \( 0, 1, \ldots, k - 1 \) mieści się \( 1 + 2 + \ldots + 2^{k-1} = 2^k - 1 \) książek. Program wstawia 7 książek rosnąco i w kolejności "najpierw środek".

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


for order in [[1, 2, 3, 4, 5, 6, 7], [4, 2, 6, 1, 3, 5, 7]]:
    shelf = {}
    for book in order:
        insert(shelf, book)
    print(order, "półek:", max(s for s, j in shelf) + 1)
    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.