Kolejnymi zagadnieniami są funkcje rekurencyjne. Omówię m.in. silnie, wieże Hanoi oraz inne zadania.
Skonstruujmy rekurencyjny algorytm wyznaczający silnię liczby naturalnej.
Jako parametr przyjmujemy dowolną liczbę naturalną.
Z definicji silni wynika, że `0!` jest równe 1. Jest to istotny warunek, gdyż bez niego rekurencja by się nie zakończyła.
Funkcja zwraca samą siebię z parametrem mniejszym o 1, co odpowiada takiemu zapisowi `5*4*3*2*1*1`
Skonstruuj algorytm wyznaczający n-ty wyraz ciągu Fibonacciego.
Ciąg ten jest specjalnym rodzajem ciągu, w którym następny element równy jest sumie poprzednich.
`a_n = a_(n-1) + a_(n-2)`
Warto pamiętać, że dla dużych n funkcja rekurencyjna może wykonywać się bardzo długo albo całkowicie zapełnić pamięć.
`\Phi = (1 + \sqrt{5}) / 2`
Z tego wzoru na złoty podział można wyprowadzić formułę na n-ty element.
`a(n) = ( ((\sqrt{5} + 1) / 2)^n - (-(\sqrt{5} + 1) / 2)^-n ) / \sqrt{5}`
Jest to jeden z lepszych sposobów jako, że złożoność jest liniowa. Przez co obliczenie wyrazu ciągu np. dla 100 nie jest problemem.
Dobrym przykładem jest zagadka wież Hanoi. Mamy trzy paliki i za ich pomocą musimy przenieść krążki z palika A na palik B z zachowaniem kolejności (większy krążek zawsze pod mniejszym). Palik C wykorzystujemy jako bufor.
N pełni tutaj liczbę krążków. Kolejne wywoływania rekurencyjne to po prostu manewrowanie krążkami.
Wizualizację oraz więcej informacji o tym problemie można znaleźć tutaj.
`(n/k)`
Symbol newtona wykorzystuje sie m.in. w kombinatoryce. Mowi on ile k-elementowych kombinacji bez powtórzeń będzie można wykonać na zbiorze n elementów.
Symbol Newtona można równoważnie wyrazić wzorem rekurencyjnym:
\begin{cases}1&{\mbox{dla }}k=0{\mbox{ lub }}k=n\\{n-1 \choose k-1}+{n-1 \choose k}&{\mbox{dla }}0 < k < n\end{cases}
A w programie wygląda to tak:
Dziękuję Ci za przeczytanie tego artykułu :). Zachęcam do sprawdzenia innych moich postów na blogu.
Zachęcam cię do odwiedzenia mojej strony na Google Play store i sprawdzenia wszystkich moich aplikacji.