Ciąg (liczby) Fibonacciego
Ciąg Fibonacciego to szczególny rodzaj ciągu liczb naturalnych. Liczby tego ciągu nazywane są liczbami Fibonacciego. Spotykane są w wielu dziedzinach i sytuacjach np. w matematyce, w przyrodzie, na rynkach giełdowych oraz na maturze z informatyki! Ciąg Fibonacciego można określić rekurencyjnie – dlatego jest często wykorzystywany we wszelkich zadaniach informatycznych.
Spis treści
Definicja liczb Fibonacciego
Rekurencyjne opisanie ciągu Fibonacciego:
Ciąg Fibonacciego to ciąg liczb, w którym pierwszy wyraz jest równy 0, drugi jest równy 1 a każdy następny jest sumą dwóch poprzednich.
\[\begin{cases} {F}_{0} = 0\\ {F}_{1} = 1\\ {F}_{n} = ({F}_{n-1}) + ({F}_{n-2}) \end{cases}\]Istnieje pewna nieścisłość zależnie od przyjętych wytycznych. W jednym z zadań na egzaminie maturalnych z informatyki, ciąg rozpoczynał się od cyfry 1. Różni autorzy mają różne zadanie na ten temat. Dostając wzór do zadania, zwróć uwagę na jego parametry.
Obliczając n-ty wyraz ciągu, musisz posługiwać się wartościami poprzednimi czyli n-1, n-2 itd. aż dojdziesz do wartości które znasz. Są nimi wartości dla F0 i F1.
Obliczymy wartość 4 wyrazu ciągu Fibonacciego, wynosi ona:
\[{F}_{4}={F}_{4-1}+{F}_{4-2}={F}_{3}+{F}_{2}\]Jest to nasza wartość dla 4 wyrazu ciągu. Zapisujemy ją lub zapamiętujemy. Wzór rekurencyjny nie dostarcza nam informacji o elemencie F3 i F2 więc musimy ponownie rozpisać te wyrazy posługując się wzorem na n:
\[{F}_{3}={F}_{3-1}+{F}_{3-2}={F}_{2}+{F}_{1}\\ {F}_{2}={F}_{2-1}+{F}_{2-2}={F}_{1}+{F}_{0}=1+0=1\]Zgodnie z obliczeniami wartość dla F2 wynosi 1. Dzięki temu możemy obliczyć wartość dla F3 i F4:
\[{F}_{3}={F}_{2}+{F}_{1}=1+1=2\\ {F}_{4}={F}_{3}+{F}_{2}=2+1=3\]Ostatecznie 4 wyraz ciągu liczb Fibonacciego wynosi 3.
Obliczanie n-tego wyrazu ciągu Fibonacciego C++ (rekurencyjnie)
Za pomocą poniższego kodu możemy wyznaczyć dowolny n-ty wyraz ciągu Fibonacciego. Jest to sposób rekurencyjny, ponieważ zawiera rekurencyjne wywołanie funkcji fib().
#include <iostream>
#include <cstdlib>
using namespace std;
unsigned int fib(int n)
{
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n-1)+fib(n-2);
}
int main()
{
int n;
cout << "Podaj numer wyrazu ciagu fibonacciego do obliczenia:" << endl;
cin >> n;
cout << fib(n) << endl;
system("PAUSE");
return(0);
}
Obliczanie n-tego wyrazu ciągu Fibonacciego C++ (iteracyjnie)
Obliczanie n-tego wyrazu ciągu fibonacciego iteracyjne jest trudniejsze, i mniej optymalne w porównaniu do metody rekurencyjnej.
#include <iostream>
#include <cstdlib>
using namespace std;
unsigned int fib(int n)
{
int a, b;
if(n == 0) return 0;
a = 0; b = 1;
for(int i=0; i < (n-1); i++)
{
swap(a, b);
b += a;
}
return b;
}
int main()
{
int n;
cout << "Podaj wyraz ciagu fibonacciego do obliczenia:" << endl;
cin >> n;
cout << fib(n) << endl;
system("PAUSE");
return(0);
}
Wypisywanie n wyrazów ciągu Fibonacciego
Korzystając ponownie ze wzoru rekurencyjnego możemy w łatwy sposób wypisać na ekran dowolną ilość liczb ciągu fibonacciego. Wystarczy wywołać funkcję w pętli odpowiednią ilość razy i wyświetlać na ekran wartości zwracane:
#include <iostream>
#include <cstdlib>
using namespace std;
unsigned int fib(int n)
{
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n-1)+fib(n-2);
}
int main()
{
int ilosc;
cout << "Podaj ile wyrazow wypisac:" << endl;
cin >> ilosc;
for (int i = 0; i<=ilosc; i++)
cout << fib(i) << ", ";
system("PAUSE >nul");
return(0);
}
Uwaga! Należy zwrócić uwagę na treść zadania. Pierwszym wyrazem ciągu Fibonacciego może być 0 lub 1. Jeżeli masz wypisać 10 wyrazów wypisujesz wyrazy od F1 do F10. Natomiast jeżeli w zadaniu ciąg zaczyna się od cyfry 0, wtedy traktujemy 0 jako pierwszy wyraz. Wypisując 10 wyrazów wypisujemy od wyrazy od F0 do F9. Tak jak pisałem wcześniej jest to kwestia umowna.
