Kliknij i wspomóż mnie :)

Kolejnymi zagadnieniami są funkcje rekurencyjne. Omówię m.in. silnie, wieże Hanoi oraz inne zadania.

Silnia liczby n

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.

`5*4*3*2*1*1`

Ciąg Fibonacciego

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ęć.

Ciąg Fibonacciego... lepiej

`\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.

Wieże Hanoi

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:

Wieże Hanoi - Wikipedia

Symbol Newtona

`(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.

Dziękuję Ci za przeczytanie tego materiału 😀 Jeżeli spodobało Ci się to o czym piszę, możesz sprawdzić więcej materiałów na blogu lub udostępnić znajomym. Będzie mi bardzo miło 😊