Zadanie 1: Rekurencja
Funkcja A(m, n) zdefiniowana rekurencyjnie: liczba wywołań, wartości dla dużych argumentów i wzory ogólne (1.1 do 1.3).
Rozwiązujesz bez konta, a odpowiedzi sprawdza ten sam silnik co na platformie. Postęp i powtórki zapisują się dopiero po darmowej rejestracji.
Zadanie 1 / 3TrudneUzupełnij tabelę
1:1 z matury · Matura maj 2026, zadanie 1.1
Policz wywołania rekurencyjne funkcji A
Obliczenie A(3, 9) wprost z definicji wymaga trzech wywołań rekurencyjnych: A(3, 4), A(6, 2), 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 = 27. Uzupełnij tabelę: podaj liczbę wywołań rekurencyjnych oraz same wywołania wraz z argumentami. W ostatnim wierszu podaj tylko liczbę wywołań.
pseudokod
| 1 | A(m, n): |
| 2 | jeżeli n = 1 |
| 3 | wynikiem jest m |
| 4 | w przeciwnym razie jeżeli n mod 2 = 0 |
| 5 | wynikiem jest A(2 · m, n / 2) |
| 6 | w przeciwnym razie |
| 7 | wynikiem jest 2 · A(m, (n - 1) / 2) + m |
Wywołania wypisz w kolejności powstawania, oddzielone przecinkami, w formacie `A(m, n)`. Potęgi zapisuj jako `2^k`.
| m | n | liczba wywołań rekurencyjnych | wywołania rekurencyjne funkcji A |
|---|---|---|---|
| 3 | 9 | 3 | A(3, 4), A(6, 2), A(12, 1) |
| 2^5 | 2^5 | ||
| 10 | 15 | ||
| 1 | 2^100 + 1 | (tu podaj tylko liczbę wywołań) |
Do uzupełnienia: 5