Ciąg Fibonacciego

Ciąg Fibbonaciego – ciąg liczb naturalnych, w którym każda liczba - z wyjątkiem pierwszej i drugiej równych jeden – jest sumą dwóch poprzednich.

n – numer liczby ciągu, n ∈N

Pierwsze 15 wyrazów ciągu Fibonacciego:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610

Liczby ciągu Fibonacciego można obliczać 2 metodami:

metoda rekurencyjna - niewydajna, algorytm odwołuje się wielokrotnie do wartości poprzednich wyrazów ciągu.
metoda iteracyjna – znacznie wydajniejsza od rekurencyjnej, oparta na tzw. programowaniu dynamicznym, w którym algorytm wykorzystuje wyniki otrzymane w poprzednich krokach - oblicza nową liczbę na podstawie dwóch poprzednich, a następnie zapamiętuje dwie ostatnie liczby – przez co nie musi liczyć wszystkich składników od początku. Operacje wykonywane są w pętli aż do wyznaczenia liczby Fibonacciego o wskazanym numerze.

Zadania

Report abuse