ফিবোনাচ্চি সিরিজে প্রতিটি পদ আগের দুটি পদের যোগফল। সিকোয়েন্স: ০, ১, ১, ২, ৩, ৫, ৮, ১৩, ২১, ৩৪, ...
পুনরাবৃত্তি সম্পর্ক: F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1
পদ্ধতি ১: ডাইনামিক প্রোগ্রামিং (Array ব্যবহার করে)
#include <iostream>
using namespace std;
void fib(int n) {
int f[n];
f[0] = 0;
f[1] = 1;
for(int i = 2; i < n; i++)
f[i] = f[i-1] + f[i-2];
for(int i = 0; i < n; i++)
cout << f[i] << " ";
}
int main() {
int n = 10;
fib(n);
return 0;
}
আউটপুট
0 1 1 2 3 5 8 13 21 34
অ্যারে f[n]-এ প্রতিটি পদ সংরক্ষণ করা হয়। সময় জটিলতা: O(n)।
পদ্ধতি ২: রিকার্সিভ
#include <iostream>
using namespace std;
int fib(int n) {
if(n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main() {
int n = 10;
for(int i = 0; i < n; i++)
cout << fib(i) << " ";
return 0;
}
আউটপুট
0 1 1 2 3 5 8 13 21 34
রিকার্সিভ পদ্ধতি সহজ কিন্তু অদক্ষ (O(2^n)), কারণ একই সাব-প্রব্লেম বারবার সমাধান করা হয়। বড় n-এর জন্য ডাইনামিক প্রোগ্রামিং বা মেমোয়াইজেশন ব্যবহার করা উচিত।
