Darmowe konto pozwoli wrócić do niego później.
Polecenie
Zadanie 1. Rekurencja
Dana jest zdefiniowana rekurencyjnie funkcja A(m, n), gdzie m i n są dodatnimi liczbami całkowitymi.
A(m, n) = {
m gdy n = 1
A(2 ∙ m, n/2) gdy n > 1 oraz n jest podzielne przez 2
2 ∙ A(m, (n–1)/2) + m gdy n > 1 oraz n nie jest podzielne przez 2
}
Zadanie 1.1.
Darmowe konto pozwoli wrócić do niego później.
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 | 2^100 + 1 | |
3 pkt
Liczba wywołań rekurencyjnych:
25 | 25: 5
10 | 15: 3
1 | 2^100 + 1: 100
Wywołania rekurencyjne:
25 | 25: A(2^6, 24), A(2^7, 23), A(2^8, 22), A(2^9, 21), A(2^10, 20)
10 | 15: A(10, 7), A(10, 3), A(10, 1)
1 | 2^100 + 1: (tylko liczba)
odpowiedź poprawna w 5 polach tabeli.
odpowiedź poprawna w 4 polach tabeli.
odpowiedź poprawna dla co najmniej dwóch pól tabeli.
Należy śledzić sekwencję rekurencyjnych wywołań funkcji; liczba wywołań zależy od liczby czasu potrzebnego do zmniejszenia n do 1.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.