Funkcja A(m, n) podwaja pierwszy argument i połowi drugi. To jest mnożenie rosyjskich chłopów, czyli A(m, n) = m · n. Kto to rozpozna, ma podpunkt 1.2 za darmo.
Arkusz CKE — maj 2026, rozszerzony
Zasada — rozpisz w dół, złóż w górę
Schodzisz po drugim argumencie aż do n = 1, notując każde wywołanie. Potem składasz wynik od dołu.
def A(m, n):
if n == 1:
return m
if n % 2 == 0:
return A(2*m, n // 2)
else:
return 2 * A(m, (n-1) // 2) + m
Drugi argument zawsze maleje, więc rekurencja musi dojść do 1. Wywołań jest mniej więcej log₂ n.
Zadanie 1.1 — liczba i lista wywołań
m | n | wywołań | wywołania rekurencyjne |
|---|---|---|---|
| 3 | 9 | 3 | A(3, 4), A(6, 2), A(12, 1) |
| 2⁵ | 2⁵ | 5 | A(64, 16), A(128, 8), A(256, 4), A(512, 2), A(1024, 1) |
| 10 | 15 | 3 | A(10, 7), A(10, 3), A(10, 1) |
| 1 | 2¹⁰⁰+1 | 100 | — |
Dla (2⁵, 2⁵) — n jest cały czas parzyste, od 32 do 1 to pięć połowień.
Dla (10, 15) — n cały czas nieparzyste (15 → 7 → 3 → 1), więc m stoi w miejscu.
Dla (1, 2¹⁰⁰+1) — pierwszy krok nieparzysty schodzi do 2⁹⁹, potem 99 połowień. Razem 100.
Zadanie 1.2 — wartości
Skoro A(m, n) = m · n:
m | n | A(m, n) |
|---|---|---|
| 1 | 777 | 777 |
| 2·10⁶ | 256·10⁶ | 512·10¹² |
Zapis potęgowy jest dozwolony, nie musisz rozpisywać piętnastocyfrowej liczby.
Dlaczego to jest iloczyn: dla parzystego n zachodzi m·n = (2m)·(n/2), więc iloczyn się nie zmienia. Dla nieparzystego m·n = 2·m·(n−1)/2 + m, czyli wyciągasz jedno m i liczysz dalej. Podstawa A(m, 1) = m.
Zadanie 1.3 — wzór na drugi argument
Pierwszy argument jest tu nieistotny.
n | wywołań | drugi argument w i-tym wywołaniu |
|---|---|---|
| 8 | 3 | 2³⁻ⁱ |
| 2ᵏ | k | 2ᵏ⁻ⁱ |
| 2ᵏ − 1 | k − 1 | 2ᵏ⁻ⁱ − 1 |
Dla 2ᵏ to same połowienia. Dla 2ᵏ − 1 liczba jest nieparzysta, a (n−1)/2 = 2ᵏ⁻¹ − 1 — wzór odtwarza się sam i ciąg kończy się na 2¹ − 1 = 1.
Najszybsze sprawdzenie jest binarne: 2ᵏ to jedynka i k zer, połowienie ucina jedno zero. 2ᵏ − 1 to k jedynek, (n−1)/2 ucina jedną jedynkę.
Gdzie tracisz punkty
- Off-by-one przy zliczaniu. Wywołanie z
n = 1liczy się — to ono zwraca podstawę. Nie liczysz tylko startowegoA(m, n), bo pytanie dotyczy wywołań rekurencyjnych. - Rozwiązanie 1.2 bez śladu. Nawet jak wiesz, że to iloczyn, w 1.1 egzaminator chce widzieć rozpisane wywołania. Sam wynik to nie wszystko.
- Zgubione środkowe zero przy dużych potęgach w 1.3.
Ten sam wzorzec w innych arkuszach
Śledzenie rekurencji — rozpisz w dół, złóż w górę — to jeden z najpewniejszych wzorców na tej maturze:
- maj 2025, zad. 1 — funkcja
przestaw— ten sam schemat, tylko liczba idzie parami cyfr - grudzień 2024, zad. 1 — pozycje jedynek — rozkład na bity tą samą metodą
Z tego samego arkusza: zad. 2 (przeniesienia), zad. 3 (pary słów), zad. 5 (systemy liczbowe).
Takich wzorców jest kilkanaście i wracają co roku. Wszystkie rozpisane i przypisane do zadań z siedmiu arkuszy — Variant.
