Strefa wyzwań

Już wiesz

  • Na czym polega rekurencja, a także podasz przykłady jej zastosowań.

  • Jak działa rekurencyjny algorytm obliczania silni oraz generowania ciągu Fibonacciego.

  • Jakie są ograniczenia związane z  wykorzystaniem rekurencji w programowaniu.

  • Jakie są różnice pomiędzy zastosowaniem rekurencji a iteracji do rozwiązania problemu.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce

Ćwiczenie 1
RHFAXJN5A7R5M
Który z poniższych ciągów jest ciągiem Fibonacciego? Możliwe odpowiedzi: 1. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144..., 2. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144..., 3. 1, 1, 2, 3, 5, 8, 11, 19, 30, 49, 79, 128..., 4. 1, 1, 2, 3, 5, 6, 8, 13, 21, 34, 55, 89, 144...
Ćwiczenie 2
RMEFHKMKV3ULM
Uzupełnij zdania. Ciąg Fibonacciego jest to ciąg liczb 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech z których pierwszy wyraz jest równy 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech, 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech także ma wartość 1, a każdy kolejny jest obliczany 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech, poprzez dodanie do siebie 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech poprzednich wyrazów ciągu.
Ćwiczenie 3
R145UEKPBCUC5
Która wersja algorytmu wyznaczania wyrazu ciągu Fibonacciego ma mniejszą złożoność czasową? Możliwe odpowiedzi: 1. wersja iteracyjna, 2. wersja rekurencyjna
Ćwiczenie 4
R28XN7D77CBM1
Pędy niektórych roślin rozwijają się zgodnie z ciągiem Fibonacciego. W kolejnych miesiącach przyrost jest taki, że w pierwszym miesiącu roślina ma jeden pęd, w drugim również jeden, w trzecim dwa itp. Ile pędów będzie miała roślina w ósmym miesiącu? Tu uzupełnij
Ćwiczenie 5
R1RLEX3V9DHC7
Jaka jest definicja ciągu Fibonacciego? Możliwe odpowiedzi: 1. nawias klamrowy, układ równań, pierwsze równanie, F indeks dolny, jeden, koniec indeksu dolnego, równa się, jeden, koniec równania, drugie równanie, F indeks dolny, dwa, koniec indeksu dolnego, równa się, jeden, koniec równania, trzecie równanie, F indeks dolny, n, koniec indeksu dolnego, równa się, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, plus, F indeks dolny, n, minus, dwa, koniec indeksu dolnego, koniec równania, koniec układu równań, 2. nawias klamrowy, układ równań, pierwsze równanie, F indeks dolny, jeden, koniec indeksu dolnego, równa się, zero, koniec równania, drugie równanie, F indeks dolny, dwa, koniec indeksu dolnego, równa się, zero, koniec równania, trzecie równanie, F indeks dolny, n, koniec indeksu dolnego, równa się, F indeks dolny, n, minus, dwa, koniec indeksu dolnego, plus, F indeks dolny, n, minus, trzy, koniec indeksu dolnego, koniec równania, koniec układu równań, 3. nawias klamrowy, układ równań, pierwsze równanie, F, równa się, zero, koniec równania, drugie równanie, F, równa się, jeden, koniec równania, trzecie równanie, F indeks dolny, n, koniec indeksu dolnego, równa się, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, plus, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, koniec równania, koniec układu równań, 4. nawias klamrowy, układ równań, pierwsze równanie, F indeks dolny, jeden, koniec indeksu dolnego, równa się, jeden, koniec równania, drugie równanie, F indeks dolny, dwa, koniec indeksu dolnego, równa się, jeden, koniec równania, trzecie równanie, F indeks dolny, n, koniec indeksu dolnego, równa się, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, plus, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, koniec równania, koniec układu równań
Ćwiczenie 6
R19R8LH355346
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ćwiczenie 7
RQL2JF4TLUHUE
Co reprezentują wartości zapisane w zmiennych a, b oraz i w pseudokodzie przedstawionym w poprzednim zadaniu? Możliwe odpowiedzi: 1. W zmiennej a oraz b przechowywane są wartości kolejnych wyrazów ciągu, a w zmiennej i numer aktualnie obliczanego wyrazu., 2. W zmiennej a, b oraz i przechowywane są wartości kolejnych wyrazów ciągu, 3. W zmiennej i przechowywane są wartości kolejnych wyrazów ciągu, a zmienne a, b to zmienne sterujące.
Ćwiczenie 8

Napisz iteracyjną wersję algorytmu uzupełniającego tablicę FIB = [0..n] dla n ≥ 0 kolejnymi wyrazami ciągu Fibonacciego w postaci pseudokodu. Zwróć uzupełnioną tablicę.

Specyfikacja problemu:

Dane:

  • FIB – tablica wypełniona kolejnymi wyrazami ciągu Fibonacciego

  • n – liczba naturalna; n ≥ 0

Wynik:

Program wypisuje uzupełnioną tablicę.

RVX5STB22391U
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Ćwiczenie 9

Zapoznaj się z pseudokodem i wykonaj ćwiczenie.

Linia 1. Rekurencyjnie otwórz nawias okrągły n zamknij nawias okrągły. Linia 2. jeżeli n znak równości 1. Linia 3. zwróć 1. Linia 4. w przeciwnym wypadku. Linia 5. zwróć Rekurencyjnie otwórz nawias okrągły n minus 1 zamknij nawias okrągły plus 1.
R8FADLPBKME9T
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ćwiczenie 10

Zapoznaj się z pseudokodem i wykonaj ćwiczenie.

Linia 1. Rekurencyjnie otwórz nawias okrągły n zamknij nawias okrągły. Linia 2. jeżeli n znak równości 1. Linia 3. zwróć 1. Linia 4. jeżeli n znak równości 2. Linia 5. zwróć 3. Linia 6. jeżeli n znak równości 3. Linia 7. zwróć 2. Linia 8. w przeciwnym wypadku. Linia 9. zwróć Rekurencyjnie otwórz nawias okrągły n minus 1 zamknij nawias okrągły plus Rekurencyjnie otwórz nawias okrągły n minus 3 zamknij nawias okrągły minus 1.
RF5B3P5UGKCXA
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ćwiczenie 11

Za pomocą pseudokodu zapisana została funkcja realizująca algorytm iteracyjnego wyznaczania wartości n-tego wyrazu ciągu. Rozwiąż przedstawiony problem, stosując technikę rekurencyjną.

Specyfikacja problemu:

Dane:

  • n – liczba naturalna; indeks elementu ciągu

Wynik:

Program wyświetla n-ty element danego ciągu.

Linia 1. Iteracyjnie otwórz nawias okrągły n zamknij nawias okrągły. Linia 2. a znak równości 5. Linia 3. dla i znak równości 2 przecinek 3 przecinek … przecinek n wykonuj. Linia 4. a znak równości minus a minus 4. Linia 5. zwróć a.
R1SSQF2VPZ6S4
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Rekurencja a iteracja. Co wybrać?