Nunta
Fie FN numarul de moduri de a aseza la masa N perechi. Se observa imediat ca F1 = 1 si F2 = 2. Pentru a calcula FN este necesar sa stim valorile elementelor FN-1 si FN-2. Astfel, pentru o asezare oarecare a primelor N-2 cupluri, putem aseza cea de-a N-a si a (N-1)-a pereche ca in imagine:
In acest caz, avem FN-2 variante de asezare.
Perechea a N-a poate fi asezata si in modul urmator:
In acest caz, avem FN-1 variante de asezare. Numarand astfel putem sti ca nu vom numara aceeasi asezare de mai multe ori. Obtinem relatia de recurenta: FN = FN-1 + FN-2. Rezolvarea problemei se bazeaza deci pe afisarea celui de-al (N+1)-lea numar din sirul lui Fibonacci. Deoarece rezultatul nu se incadreaza in nici un tip de date conventional, trebuie implementata adunarea pe numere mari. De exemplu, al 1000-lea numar Fibonacci are 209 cifre. Operatiile cu numere mari sunt tratate in acest articol. Din considerente de memorie se vor retine la fiecare pas doar ultimele doua numere Fibonacci.
