Fotografia przedstawia artystyczną wizję rekurencji w przyrodzie. Tło w kolorze zielonym jest rozmyte, a na pierwszym planie widać spiralę (kwiat) w odcieniach żółto‑brązowych.
Fotografia przedstawia artystyczną wizję rekurencji w przyrodzie. Tło w kolorze zielonym jest rozmyte, a na pierwszym planie widać spiralę (kwiat) w odcieniach żółto‑brązowych.
I_R_W14_M21_C++ Rekurencja na maturze
Obraz wygenerowany przez canva.ai
Źródło: domena publiczna.
Rekurencji, czyli metody rozwiązywania problemów, polegającej na rozwiązywaniu podproblemów, możemy użyć m.in. w programach generujących ciągi liczb, wyszukujących wartości, sortujących zbiory czy generujących fraktale. W tym e‑materiale rozwiążemy zadania maturalne, w których należy wykorzystać rekurencję.
Ćwiczenia na rozgrzewkę:
Dana jest funkcja znajdź, opisana za pomocą niepełnej specyfikacji i pseudokodu.
Specyfikacja:
Dane:
n – liczba naturalna
tab[1..n] – tablica n liczb rzeczywistych
Wynik:
…
Pseudokod:
Linia 1. funkcja znajdź otwórz nawias okrągły n przecinek tablica zamknij nawias okrągły dwukropek.
Linia 2. jeżeli n znak równości 1.
Linia 3. zwróć tablica otwórz nawias kwadratowy 1 zamknij nawias kwadratowy.
Linia 5. wynik ← znajdź otwórz nawias okrągły n minus 1 przecinek tablica zamknij nawias okrągły.
Linia 6. jeżeli wynik zamknij nawias ostrokątny tablica otwórz nawias kwadratowy n zamknij nawias kwadratowy.
Linia 7. zwróć wynik.
Linia 8. zwróć tablica otwórz nawias kwadratowy n zamknij nawias kwadratowy.
funkcja znajdź(n, tablica):
jeżeli n = 1
zwróć tablica[1]
wynik ← znajdź(n - 1, tablica)
jeżeli wynik > tablica[n]
zwróć wynik
zwróć tablica[n]
Na podstawie podanych informacji wykonaj następujące ćwiczenia:
Ćwiczenie 1
RU7S4VJH4LDMF
Wynikiem funkcji znajdź(n, tab), gdzie tab to tablica n liczb rzeczywistych, będzie: Możliwe odpowiedzi: 1. największa spośród liczb tab[1..n], 2. najmniejsza spośród liczb tab[1..n], 3. średnia liczb zawartych w tab
Ćwiczenie 2
R16K9BHHVE6V8
Operacją dominującą danego algorytmu jest porównanie dwóch wartości występujących w linijce 6 algorytmu. Zaznacz poprawne zdania dotyczące liczby operacji dominujących funkcji znajdź Możliwe odpowiedzi: 1. dla znajdz(10, [1,2,3,4,5,6,7,8,9,0]) liczba dominujących operacji wynosi 9, 2. dla znajdz(10, [0,9,8,7,6,5,4,3,2,1]) liczba dominujących operacji wynosi 1, 3. dla znajdz(5, [99,0,0,0,0]) liczba dominujących operacji wynosi 1, 4. dla znajdz(5, [99,0,0,0,0]) liczba dominujących operacji wynosi 5, 5. dla znajdz(4, [143, 143, 143, 143]) liczba dominujących operacji wynosi 1, 6. dla znajdz(4, [143, 143, 143, 143]) liczba dominujących operacji wynosi 4, 7. dla znajdz(10, [1,2,3,4,5,6,7,8,9,0]) liczba dominujących operacji wynosi 10
Ćwiczenie 3
R16VNJBG1UKCJ
Złożoność obliczeniowa funkcji znajdź jest: Możliwe odpowiedzi: 1. liniowa, opisana wzorem O(n), gdzie n to rozmiar tablicy tab, 2. liniowa, opisana wzorem O(n+k), gdzie n to rozmiar tablicy tab, a k to różnica pomiędzy największym i najmniejszym elementem w tablicy, 3. stała, 4. kwadratowa, opisana wzorem O(k2), gdzie k oznacza pozycję mediany tablicy tab
Twoje cele
Prześledzisz sposób rozwiązywania zadań maturalnych wykorzystujących rekurencję.
Rozwiążesz samodzielnie kilka zadań maturalnych, używając rekurencji.
Przeanalizujesz, w jaki sposób uniknąć typowych błędów w tego typu zadaniach.