{"id":"informatyka-2026-maj-matura-rozszerzona/zad/1","paper_id":"informatyka-2026-maj-matura-rozszerzona","number":"1","points":7,"ptype":"open","subject":"informatyka","category":"matura","year":2026,"month":"maj","level":"rozszerzona","text":"Zadanie 1. Rekurencja\nDana jest zdefiniowana rekurencyjnie funkcja A(m, n), gdzie m i n są dodatnimi liczbami\ncałkowitymi.\nA(m, n) =\n{\nm gdy n = 1\nA (2 ∙ m,\nn\n2 ) gdy n > 1 oraz n jest podzielne przez 2\n2 ∙ A(m,\nn - 1\n2 ) + m gdy n > 1 oraz n nie jest podzielne przez 2","answer":null,"answer_text":"2\n7","solution":"Odpowiedź: **1.1.** | m | n | liczba wywołań | wywołania rekurencyjne | |---|---|---|---| | 3 | 9 | 3 | A(3,4), A(6,2), A(12,1) | | 2⁵ | 2⁵ | **5** | **A(2⁶,2⁴), A(2⁷,2³), A(2⁸,2²), A(2⁹,2¹), A(2¹⁰,2⁰)** | | 10 | 15 | **3** | **A(10,7), A(10,3), A(10,1)** | | 1 | 2¹⁰⁰+1 | **100** | — | **1.2.** - `A(1, 777)` = **777** - `A(2·10⁶, 256·10⁶)` = **512·10¹²** = 512 000 000 000 000 **1.3.** | n | liczba wywołań | drugi argument w i-tym wywołaniu | |---|---|---| | 8 | 3 | 8/2ⁱ (lub 2³⁻ⁱ) | | 2ᵏ | **k** | **2ᵏ⁻ⁱ** | | 2ᵏ − 1 | **k − 1** | **2ᵏ⁻ⁱ − 1** |\n\nTreść zadania (CKE)\n\nDlaczego A(m, n) = m · n\n\nDowód przez indukcję po n — wystarczy pokazać, że iloczyn m · n jest niezmiennikiem rekurencji:\n\nPrzypadek | Wywołanie | Iloczyn przed | Iloczyn po\nn = 1 | zwraca m | m · 1 = m | —\nn parzyste | A(2m, n/2) | m · n | (2m) · (n/2) = m · n\nn nieparzyste | 2·A(m, (n−1)/2) + m | m · n | 2·(m·(n−1)/2) + m = m·n − m + m = m · n\n\nIloczyn nie zmienia się przy żadnym przejściu, a na dnie rekurencji równa się m. Algorytm to więc mnożenie przez podwajanie — ta sama idea, co w mnożeniu chłopskim (rosyjskim).\n\nIle jest wywołań\n\nKażdy krok dzieli n przez 2 (dla nieparzystych po odjęciu jedynki), więc głębokość to ⌊log₂ n⌋:\n\n```\nn = 8 = 2³ → 8 → 4 → 2 → 1 : 3 wywołania\nn = 2ᵏ → 2ᵏ → 2ᵏ⁻¹ → … → 2⁰ : k wywołań\nn = 2ᵏ − 1 → same nieparzyste : k − 1 wywołań\nn = 2¹⁰⁰ + 1 → 1 + 99 : 100 wywołań\n```\n\nDrugi argument w i-tym wywołaniu:\n\n- dla n = 2ᵏ: 2ᵏ⁻ⁱ\n- dla n = 2ᵏ − 1: 2ᵏ⁻ⁱ − 1\n\nPunktacja CKE\n\n- 1.1. 3 pkt za 5 poprawnych pól tabeli, 2 pkt za 4, 1 pkt za co najmniej 2.\n- 1.2. 1 pkt — oba wiersze poprawne.\n- 1.3. 3 pkt za 4 poprawne pola, 2 pkt za 3, 1 pkt za 2.\n- Razem: 7 pkt.\n\nTypowy błąd: **Najważniejsza obserwacja, która skraca całe zadanie: `A(m, n) = m · n`.** Sprawdź na przykładzie z arkusza: A(3,9) = 27 = 3·9. Stąd 1.2 robi się w pamięci — A(1,777)=777, a A(2·10⁶, 256·10⁶) = 2·256·10¹² = 512·10¹². Bez tej obserwacji trzeba rozwijać rekurencję ręcznie i łatwo się pomylić przy dużych liczbach. Uzasadnienie własności jest krótkie: dla n parzystego m·n = (2m)·(n/2), a dla nieparzystego 2·(m·(n−1)/2) + m = m·(n−1) + m = m·n. Wartość się nie zmienia na żadnym kroku, a na końcu (n=1) wynosi m. **Druga pułapka — liczenie wywołań.** Rekurencja zmniejsza n mniej więcej o połowę, więc liczba wywołań jest rzędu log₂n: - `n = 2ᵏ` → dokładnie **k** wywołań (schodzimy 2ᵏ → 2ᵏ⁻¹ → … → 2⁰ = 1); - `n = 2ᵏ − 1` → **k − 1**, bo dla nieparzystych (n−1)/2 zjada jeden krok więcej na starcie; - `n = 2¹⁰⁰ + 1` → jedno wywołanie na zejście do 2⁹⁹, potem 99 halvingów, razem **100**. Częsty błąd to policzenie o jeden za dużo — wywołanie *początkowe* A(m,n) **nie jest** wywołaniem rekurencyjnym. W przykładzie z arkusza są trzy, nie cztery.","image":"img/informatyka-2026-maj-matura-rozszerzona/zad-1.webp","solution_image":null,"topics":"rekurencja, analiza algorytmu, zlozonosc logarytmiczna","page_from":4,"source":"ocr","answer_source":null,"answer_text_source":"ocr","solution_source":"maturaonline","text_source":"ocr","source_label":"Informatyka · Matura · maj 2026 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"<p>Zadanie 1. Rekurencja<br>Dana jest zdefiniowana rekurencyjnie funkcja A(m, n), gdzie m i n są dodatnimi liczbami<br>całkowitymi.<br>A(m, n) =<br>{<br>m gdy n = 1<br>A (2 ∙ m,<br>n<br>2 ) gdy n &gt; 1 oraz n jest podzielne przez 2<br>2 ∙ A(m,<br>n - 1<br>2 ) + m gdy n &gt; 1 oraz n nie jest podzielne przez 2</p>","answer_text_html":"<p>2<br>7</p>","solutions":[{"source":"maturaonline","label":"matura-online.pl","kind":"text","html":"<p>Odpowiedź: <strong>1.1.</strong> | m | n | liczba wywołań | wywołania rekurencyjne | |---|---|---|---| | 3 | 9 | 3 | A(3,4), A(6,2), A(12,1) | | 2⁵ | 2⁵ | <strong>5</strong> | <strong>A(2⁶,2⁴), A(2⁷,2³), A(2⁸,2²), A(2⁹,2¹), A(2¹⁰,2⁰)</strong> | | 10 | 15 | <strong>3</strong> | <strong>A(10,7), A(10,3), A(10,1)</strong> | | 1 | 2¹⁰⁰+1 | <strong>100</strong> | — | <strong>1.2.</strong> - <code>A(1, 777)</code> = <strong>777</strong> - <code>A(2·10⁶, 256·10⁶)</code> = <strong>512·10¹²</strong> = 512 000 000 000 000 <strong>1.3.</strong> | n | liczba wywołań | drugi argument w i-tym wywołaniu | |---|---|---| | 8 | 3 | 8/2ⁱ (lub 2³⁻ⁱ) | | 2ᵏ | <strong>k</strong> | <strong>2ᵏ⁻ⁱ</strong> | | 2ᵏ − 1 | <strong>k − 1</strong> | <strong>2ᵏ⁻ⁱ − 1</strong> |</p>\n<p>Treść zadania (CKE)</p>\n<p>Dlaczego A(m, n) = m · n</p>\n<p>Dowód przez indukcję po n — wystarczy pokazać, że iloczyn m · n jest niezmiennikiem rekurencji:</p>\n<p>Przypadek | Wywołanie | Iloczyn przed | Iloczyn po<br>n = 1 | zwraca m | m · 1 = m | —<br>n parzyste | A(2m, n/2) | m · n | (2m) · (n/2) = m · n<br>n nieparzyste | 2·A(m, (n−1)/2) + m | m · n | 2·(m·(n−1)/2) + m = m·n − m + m = m · n</p>\n<p>Iloczyn nie zmienia się przy żadnym przejściu, a na dnie rekurencji równa się m. Algorytm to więc mnożenie przez podwajanie — ta sama idea, co w mnożeniu chłopskim (rosyjskim).</p>\n<p>Ile jest wywołań</p>\n<p>Każdy krok dzieli n przez 2 (dla nieparzystych po odjęciu jedynki), więc głębokość to ⌊log₂ n⌋:</p>\n<p>```<br>n = 8 = 2³ → 8 → 4 → 2 → 1 : 3 wywołania<br>n = 2ᵏ → 2ᵏ → 2ᵏ⁻¹ → … → 2⁰ : k wywołań<br>n = 2ᵏ − 1 → same nieparzyste : k − 1 wywołań<br>n = 2¹⁰⁰ + 1 → 1 + 99 : 100 wywołań<br>```</p>\n<p>Drugi argument w i-tym wywołaniu:</p>\n<ul><li>dla n = 2ᵏ: 2ᵏ⁻ⁱ</li><li>dla n = 2ᵏ − 1: 2ᵏ⁻ⁱ − 1</li></ul>\n<p>Punktacja CKE</p>\n<ul><li>1.1. 3 pkt za 5 poprawnych pól tabeli, 2 pkt za 4, 1 pkt za co najmniej 2.</li><li>1.2. 1 pkt — oba wiersze poprawne.</li><li>1.3. 3 pkt za 4 poprawne pola, 2 pkt za 3, 1 pkt za 2.</li><li>Razem: 7 pkt.</li></ul>\n<p>Typowy błąd: <strong>Najważniejsza obserwacja, która skraca całe zadanie: <code>A(m, n) = m · n</code>.</strong> Sprawdź na przykładzie z arkusza: A(3,9) = 27 = 3·9. Stąd 1.2 robi się w pamięci — A(1,777)=777, a A(2·10⁶, 256·10⁶) = 2·256·10¹² = 512·10¹². Bez tej obserwacji trzeba rozwijać rekurencję ręcznie i łatwo się pomylić przy dużych liczbach. Uzasadnienie własności jest krótkie: dla n parzystego m·n = (2m)·(n/2), a dla nieparzystego 2·(m·(n−1)/2) + m = m·(n−1) + m = m·n. Wartość się nie zmienia na żadnym kroku, a na końcu (n=1) wynosi m. <strong>Druga pułapka — liczenie wywołań.</strong> Rekurencja zmniejsza n mniej więcej o połowę, więc liczba wywołań jest rzędu log₂n: - <code>n = 2ᵏ</code> → dokładnie <strong>k</strong> wywołań (schodzimy 2ᵏ → 2ᵏ⁻¹ → … → 2⁰ = 1); - <code>n = 2ᵏ − 1</code> → <strong>k − 1</strong>, bo dla nieparzystych (n−1)/2 zjada jeden krok więcej na starcie; - <code>n = 2¹⁰⁰ + 1</code> → jedno wywołanie na zejście do 2⁹⁹, potem 99 halvingów, razem <strong>100</strong>. Częsty błąd to policzenie o jeden za dużo — wywołanie <em>początkowe</em> A(m,n) <strong>nie jest</strong> wywołaniem rekurencyjnym. W przykładzie z arkusza są trzy, nie cztery.</p>"}]}