5600235755

5 Rekurencja 12

5.3 Silnia

Rozważmy następujący ciąg rekurencyjny:

a₀ = 1,

a_n = n ■ a_n.

dla n > 1.

Wartość n-tego wyrazu tego ciągu nazywa się silnią liczby n i oznaczana jest przez n\. Zatem postać jawna tego ciągu wygląda następująco:

5.4 Ciąg Fibonacciego

Spośród ciągów rekurencyjnych najsłynniejszym jest chyba ciąg Fibonacciego:

a₀ = 0,

ai = 1,

a_n = 0"ti-1 + fln-2)    dla n > 2.

Każdy wyraz tego ciągu, poza dwoma pierwszymi, jest sumą poprzednich dwóch wyrazów. Postać jawna nie jest trywialna, a mianowicie:

5.5 Wieże Hanoi

Na jednej z trzech wież znajdują się 64 krążki takie, że krążki umieszczone wyżej mają mniejsze promienie. Zadanie polega na przełożeniu wszystkich tych kążków z pierwszej na trzecią wieżę, ale tak aby:

•    w jednym ruchu można przenieść tylko jeden krążek,

•    większy krążek nigdy nie może leżeć na mniejszym,

•    można posługiwać się trzema wieżami.

Ile czasu zajmmie przełożenie tych krążków jeśli przyjmiemy, że przełożenie jednego zajmuje sekundę?

Przez a_n oznaczmy liczbę ruchów potrzebnych do przeniesienia n krążków z jednej wieży na drugą. Łatwo sprawdzić, że

ao = 0,

ai = 1,

0-2 = 3, a₃ = 7.

Już przy n = 3 widać regułę rekurencyjną. Oznaczmy kolejne wieże przez A, B, C. Aby przenieść n krążków z A na C: