Zadanie 1.1. (0-3)
Obliczenie wartości funkcji A(3, 9) wprost z definicji wymaga trzech wywołań rekurencyjnych:
A(3, 4), A(6, 2), A(12, 1), ponieważ:
A(3, 9) = 2 ∙ A(3, 4) + 3 = 2 ∙ A(6, 2) + 3 = 2 ∙ A(12, 1) + 3 = 2 ∙ 12 + 3 = 27
Uzupełnij poniższą tabelę. Podaj liczbę wywołań rekurencyjnych funkcji A oraz wypisz
wywołania rekurencyjne wraz z ich argumentami (w ostatnim wierszu podaj tylko liczbę
wywołań rekurencyjnych).
m
n
liczba wywołań
rekurencyjnych
funkcji A
wywołania rekurencyjne funkcji A
3
9
3
A(3, 4), A(6, 2), A(12, 1)
25
25
10
15
1
2100 + 1
Miejsce na obliczenia (brudnopis)
1.1.
0-1-
2-3
MINP-R0_100
Zadanie 1.1. (0-3)
Wymagania określone w podstawie programowej1
Wymaganie ogólne
Wymagania szczegółowe
I. Rozumienie, analizowanie
i rozwiązywanie problemów.
Zdający:
I.4) do realizacji rozwiązania problemu
dobiera odpowiednią metodę lub technikę
algorytmiczną i struktury danych.
I+II.3) objaśnia, a także porównuje
podstawowe metody i techniki
algorytmiczne oraz struktury danych,
wykorzystując przy tym przykłady
problemów i algorytmów, w szczególności:
b) rekurencję.
P.I.3) sprawdza poprawność działania
algorytmów dla przykładowych danych.
Zasady oceniania
3 pkt - odpowiedź poprawna w 5 polach tabeli.
2 pkt - odpowiedź poprawna w 4 polach tabeli.
1 pkt - odpowiedź poprawna dla co najmniej dwóch pól tabeli.
0 pkt - odpowiedź niepoprawna lub niepełna albo brak rozwiązania.
1 Rozporządzenie Ministra Edukacji z dnia 28 czerwca 2024 r. zmieniające rozporządzenie w sprawie podstawy
programowej kształcenia ogólnego dla liceum ogólnokształcącego, technikum oraz branżowej szkoły II stopnia
(Dz.U. z 2024 r. poz. 1019).
Zasady oceniania rozwiązań zadań
Poprawna odpowiedź
liczba wywołań
rekurencyjnych funkcji A
wywołania rekurencyjne funkcji A
3
A(3, 4), A(6, 2), A(12, 1)
5
A(26, 24), A(27, 23), A(28, 22), A(29, 21), A(210, 20)
3
A(10, 7), A(10, 3), A(10, 1)
100
| 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 | — |
"},{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"Stosujemy definicję funkcji: gdy $n$ jest parzyste i $n>1$ liczymy $A(2m,\\tfrac{n}{2})$, gdy $n$ nieparzyste i $n>1$ liczymy $A(m,\\tfrac{n-1}{2})$, a przy $n=1$ rekurencja się kończy.
\nA(3, 9): $9$ jest nieparzyste $\\Rightarrow A(3,4)$; $4$ parzyste $\\Rightarrow A(6,2)$; $2$ parzyste $\\Rightarrow A(12,1)$; $n=1$ koniec. Razem 3 wywołania: $A(3,4),\\ A(6,2),\\ A(12,1)$.
\nA(m, 2⁵) = A(m,32): kolejno dzielimy przez 2 (wszystkie parzyste aż do 1):
$A(2^6,2^4)\\to A(2^7,2^3)\\to A(2^8,2^2)\\to A(2^9,2^1)\\to A(2^{10},2^0=1)$ - koniec. Razem 5 wywołań (przy starcie $m=2^5$): $A(2^6,2^4),\\ A(2^7,2^3),\\ A(2^8,2^2),\\ A(2^9,2^1),\\ A(2^{10},2^0)$.
A(10, 15): $15$ nieparzyste $\\Rightarrow A(10,7)$; $7$ nieparzyste $\\Rightarrow A(10,3)$; $3$ nieparzyste $\\Rightarrow A(10,1)$; koniec. Razem 3 wywołania: $A(10,7),\\ A(10,3),\\ A(10,1)$.
\nOstatni wiersz - tylko liczba wywołań. Dla $A(m, 2^{100})$ argument $n$ jest cały czas parzysty, więc w każdym kroku $n$ dzieli się przez 2: $2^{100}\\to 2^{99}\\to\\dots\\to 2^0=1$. To daje 100 wywołań rekurencyjnych.
\n