Liczby Fibonacciego zdefiniowane są w następujący sposób:
|
1 2 3 4 5 |
F(0) = 1 ; F(1) = 1 ; F(n) = F(n - 1) + F(n - 2) ; |
gdzie n należy do zbioru liczb naturalnych. Obliczanie liczb Fibonacciego dla kolejnych liczb naturalnych n jest prostą sprawą. Wstawiamy do pierwszego i drugiego elementu tablicy wartość 1, tak jak to wynika z definicji. Następnie, w pętli, poczynając od trzeciego elementu, obliczamy wartość dla każdego n, poprzez dodanie do siebie dwóch poprzednich wartości elementów tablicy:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
void oblicz(int *tab) { tab[0] = 1 ; tab[1] = 1 ; for (int i = 2 ; i < MAX_LICZB ; i++) tab = tab[i - 1] + tab[i - 2] ; } n = 2 F(2) = F(2 - 1) + F(2 - 2) (F(1) = 1; F(0) = 1) F(2) = 1 + 1 F(2) = 2 ... F(5) = F(4) + F(3) (F(4) = 5; F(3) = 3) ; F(5) = 8 ; |
itd.
Pełny kod przykładowego programu:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include const int MAX_LICZB = 46 ; void oblicz(int *tab) ; int main() { int liczba ; int tab[MAX_LICZB] ; oblicz(tab) ; // obliczamy na początku wartości dla n z zakresu 0..MAX_LICZB - 1 cout << "Podaj, dla jakiego n mam obliczyc liczbe Fibonacciego (zakres: 0.." << MAX_LICZB - 1 << ")\n" ; cin >> liczba ; if (liczba < 0 || liczba >= MAX_LICZB) cout << "Liczba " << liczba << " nie nalezy do podanego przedzialu.\n" ; else cout << tab[liczba] << endl ; // teraz od razu wypisujemy wartość dla podanego n return 0 ; } void oblicz(int *tab) { tab[0] = 1 ; tab[1] = 1 ; for (int i = 2 ; i < MAX_LICZB ; i++) tab = tab[i - 1] + tab[i - 2] ; } |
Autor: Iskar
