1
Polecenie 1

Dany jest ciąg zdefiniowany rekurencyjnie:

F n = { 0 dla  n = 0 1 dla  n = 1 F n 1 + F n 2 dla  n > 1

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

Linia 1. funkcja fib otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 2. jeżeli n otwórz nawias ostrokątny 2 dwukropek. Linia 3. zwróć n. Linia 4. zwróć fib otwórz nawias okrągły n minus 1 zamknij nawias okrągły plus fib otwórz nawias okrągły n minus 2 zamknij nawias okrągły.
Przeczytaj wyjaśnienie działania symulacji wywołania funkcji.
Przeczytaj wyjaśnienie działania symulacji wywołania funkcji.
Ważne!

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)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.

RulZIWQ1WZZnA
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

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.

Polecenie 2

Dany jest następujący wzór zdefiniowany rekurencyjnie:

Rozpisz drzewo wywołań rekurencyjnych ciągu dla .