Aplet
Dany jest ciąg zdefiniowany rekurencyjnie:
Jest to ciąg Fibonacciego. W jaki sposób obliczyć jego wyraz o indeksie n?
Rozpisz drzewo wywołań rekurencyjnych dla podanego ciągu. Następnie porównaj je z tym zaprezentowanym w aplecie.
Specyfikacja problemu:
Dane
n– liczba naturalna; indeks wyrazu w ciągu Fibonacciego
Szukane
wyraz– liczba naturalna; obliczony wyraz ciągu Fibonacciego
Wykorzystanie mechanizmu rekurencji do rozwiązania tego problemu jest nieefektywne. Funkcja będzie wielokrotnie obliczać te same wartości, z każdym wywołaniem fib(n) licząc od nowa wartości fib(n - 1) i fib(n - 2). Zwróć uwagę, ile razy dla wywołania fib(5) zostanie policzona wartość fib(2). Funkcję zaprezentowano tylko w celu wyjaśnienia rekurencji. Nie należy jej stosować do wyznaczenia wyrazów ciągu Fibonacciego.
Zasób interaktywny dostępny pod adresem https://zpe.gov.pl/a/D1HpTu0N1
Symulacja przedstawia liczenie wybranego elementu z ciągu fibonacciego.
Na górze ustawiono pole, w którym wpisuje się numer wybranego elementu do wyliczenia.
Pod nim dwa przyciski: wstecz oraz dalej.
Po środku ekranu znajduje się napis fib (wybrana liczba).
Od tego napisu poprowadzone zostaną rozgałęzienia, z czego każde zakończone będzie podobnym napisem, pierwsze rozgałęzienie będzie miało napis fib (wybrana liczba - 1), zaś napis w drugiej gałęzi napis fib (wybrana liczba - 2).
To zachowanie będzie się powtarzało przy każdym kliknięciu przycisku dalej aż do momentu, w którym wybrana liczba po stosownym odejmowaniu osiągnie wartość 1 lub 0.
W przypadku osiągnięcia wartości 1 lub 0 wynik funkcji zostaje zwrócony jako 1 lub 0 odpowiednio, wtedy każdy wynik zostaje kolejno dodany i tym samym gałęzie zostają usunięte.
Po usunięciu gałęzi na jednym poziomie, schodzenie inną sąsiadującą gałęzią się powtarza.
Algorytm następnie polega na zsumowaniu wszystkich kolejnych wyników rozgałęzień i uzyskaniu wyniku dla początkowej wybranej liczby.
Dany jest następujący wzór zdefiniowany rekurencyjnie:
Rozpisz drzewo wywołań rekurencyjnych ciągu dla .
