Fibonacci sequence (tsz. Fibonacci sequences)
A Fibonacci sorozat egy olyan számsorozat, amelyben minden szám az előző két szám összegéből adódik. A sorozat első két száma 0 és 1, és onnantól kezdve minden további szám az előző két szám összege:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
A Fibonacci sorozat kiszámításához többféle módszert is alkalmazhatunk. Az alábbiakban bemutatok két megoldást: az iteratív és a rekurzív megoldást.
Az iteratív megoldás során egy ciklus segítségével számoljuk ki a Fibonacci számokat. Ez a módszer hatékonyabb, mivel nem használ túl sok memóriát.
#include <iostream>
using namespace std;
int main() {
int n;
cout << "Add meg, hány Fibonacci számot szeretnél: ";
cin >> n;
long long a = 0, b = 1; // Az első két Fibonacci szám
cout << "Fibonacci sorozat: " << a << " " << b << " "; // Az első két szám kiírása
for (int i = 3; i <= n; i++) {
long long next = a + b; // Az új Fibonacci szám kiszámítása
cout << next << " "; // Az új szám kiírása
a = b; // Az előző számok frissítése
b = next;
}
cout << endl;
return 0;
}
Magyarázat: - A program a felhasználótól bekéri, hogy hány Fibonacci számot szeretne látni. - Az első két Fibonacci számot (0 és 1) előre beállítjuk, és ezeket kiírjuk. - Ezután egy ciklus segítségével kiszámítjuk a következő Fibonacci számot, és azt is kiírjuk, miközben folyamatosan frissítjük az előző két számot.
A rekurzív megoldásnál a Fibonacci számot egy rekurzív függvénnyel számoljuk ki. Bár egyszerű, a rekurzív megoldás nem olyan hatékony, mivel sok redundáns számítást végezhet el.
#include <iostream>
using namespace std;
// Rekurzív függvény a Fibonacci szám kiszámításához
long long fibonacci(int n) {
if (n <= 1) {
return n; // Az első két Fibonacci szám 0 és 1
}
return fibonacci(n - 1) + fibonacci(n - 2); // A Fibonacci szám rekurzív számítása
}
int main() {
int n;
cout << "Add meg, hány Fibonacci számot szeretnél: ";
cin >> n;
cout << "Fibonacci sorozat: ";
for (int i = 0; i < n; i++) {
cout << fibonacci(i) << " "; // Kiírjuk a Fibonacci számokat
}
cout << endl;
return 0;
}
Magyarázat: - A fibonacci függvény rekurzív módon számolja ki a Fibonacci számokat: ha n kisebb vagy egyenlő 1, akkor visszaadja n értékét (az alapértelmezett Fibonacci számokat). - A rekurzív hívások végzik el az összeadásokat és számolják ki a következő Fibonacci számot.
Ha a felhasználó 10 Fibonacci számot kér, akkor a program kimenete a következő lesz:
Add meg, hány Fibonacci számot szeretnél: 10 Fibonacci sorozat: 0 1 1 2 3 5 8 13 21 34
n értékre kell számolni, akkor az iteratív megoldás a jobb választás.memoization technika alkalmazásával a rekurziót optimalizálhatjuk, de az iteratív megoldás sokkal gyorsabb és memóriatakarékosabb.