1. Pewien ciąg liczb został zdefiniowany rekurencyjnie, tak jak poniżej.
Zdefiniuj w języku programowania funkcję rekurencyjną a(n) obliczania n-tego wyrazu tego ciągu.
Ile wynosi wartość a(8) ?
A. 19012
B. - 3096
C. -22084
D. 8492
2. Kolejne liczby ciągu Lucasa oblicza się w taki sam sposób jak liczby Fibonacciego, z tym że początkowe liczby są równe 2 i 1. Każda kolejna liczba Lucasa jest sumą dwóch poprzednich, a zatem początkowe wartości ciągu Lucasa to: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, …
Jaki będzie 16 wyraz ciągu Lucasa ?
A. 2311
B. 1364
C. 843
D. 1231
3. Wieże z Hanoi to ciekawe zadanie z algorytmiki. Rozwiązanie jest często spotykanym modelem myślenia rekurencyjnego, dlatego warto je poznać.
Załóżmy, że mamy 4 krążki o malejących średnicach. Każdy z nich posiada wydrążoną dziurkę i jest "nadziany" na pierwszy z trzech drążków jakie posiadamy. Pozostałe drążki są puste.
Zadanie polega na przeniesieniu wszystkich krążków z pierwszego drążka na drugi przy użyciu trzeciego. Trzeba to jednak zrobić przy dwóch założeniach:
wolno przenosić krążki tylko pojedynczo
ani przez moment krążek większy nie może leżeć na krążku mniejszym
Jaka jest minimalna ilość ruchów dla 4 krążków?
A. 13
B. 25
C. 17
D. 15