2. Funkcja rekurencyjna F(x, p)

Matura próbna grudzień 2024 - Matura z informatyki: arkusze krok po kroku (Python)

**Zadanie 2. Rekurencja.** \( F(x, p) \) bierze ostatnią cyfrę \( c \) liczby \( x \) w systemie o podstawie \( p \): nieparzystą dodaje, parzystą odejmuje, a resztę liczby oddaje wywołaniu rekurencyjnemu. Każde wywołanie zdejmuje jedną cyfrę, więc wywołań jest o jeden więcej niż cyfr (ostatnie dostaje \( x = 0 \)). Przykład liczy wiersz z arkusza: \( F(125, 2) = 6 \) i 8 wywołań (\( 125 = 1111101_2 \), siedem cyfr). Uruchom krokowo i obejrzyj stos wywołań.

calls = 0


def F(x, p):
    global calls
    calls = calls + 1  # licznik wywołań, także pierwszego
    if x == 0:
        return 0
    c = x % p  # ostatnia cyfra x w systemie o podstawie p
    if c % 2 == 1:
        return F(x // p, p) + c
    return F(x // p, p) - c


print(F(125, 2), calls)
print("125 dwójkowo:", bin(125)[2:])

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