1.3 Wywołania dla potęg dwójki

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

Zadanie 1.3 (3 pkt) pyta o liczbę wywołań i drugi argument w i-tym wywołaniu dla \( n = 2^k \) i \( n = 2^k - 1 \). Pierwszy argument nie wpływa na drugi, więc wystarczy `m = 1`. Program wypisuje dla kolejnych `k`: liczbę n, liczbę wywołań i listę drugich argumentów. Wzór widać po kilku wierszach: dla \( 2^k \) każde wywołanie dzieli n na pół.

calls = []


def A(m, n):
    # funkcja A z arkusza; każde wywołanie rekurencyjne trafia na listę calls
    if n == 1:
        return m
    if n % 2 == 0:
        calls.append((2 * m, n // 2))
        return A(2 * m, n // 2)
    calls.append((m, (n - 1) // 2))
    return 2 * A(m, (n - 1) // 2) + m


for k in range(3, 9):
    for n in [2 ** k, 2 ** k - 1]:
        calls.clear()
        A(1, n)
        print(n, len(calls), [arg for m, arg in calls])

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