Matura 2026 — informatyka (termin główny) · zad. 1.1RozszerzonyŚrednie3 pkt

Rekurencja. Dana jest zdefiniowana rekurencyjnie funkcja A(m,n)A(m,n), gdzie mm i nn są dodatnimi liczbami całkowitymi:

A(m,n)={mn=1A(2m,n2)n>1 i n parzyste2⋅A(m,n−12)+mn>1 i n nieparzysteA(m,n)=\begin{cases} m & n=1\\ A\left(2m,\tfrac n2\right) & n>1\ \text{i}\ n\ \text{parzyste}\\ 2\cdot A\left(m,\tfrac{n-1}2\right)+m & n>1\ \text{i}\ n\ \text{nieparzyste}\end{cases}

Obliczenie A(3,9)A(3,9) wprost z definicji wymaga trzech wywołań rekurencyjnych: A(3,4)A(3,4), A(6,2)A(6,2), A(12,1)A(12,1), bo A(3,9)=2⋅A(3,4)+3=2⋅A(6,2)+3=2⋅A(12,1)+3=2⋅12+3=27A(3,9)=2\cdot A(3,4)+3=2\cdot A(6,2)+3=2\cdot A(12,1)+3=2\cdot12+3=27.

Podaj liczbę wywołań rekurencyjnych funkcji AA oraz wypisz wywołania rekurencyjne (w ostatnim wierszu podaj tylko liczbę wywołań) dla:

mmnn
3399 (przykład: 3 wywołania)
252^5252^5
10101515
112100+12^{100}+1
#rekurencja#matura 2026#informatyka