ফিবোনাচি সিরিজে এমন সংখ্যা রয়েছে যেখানে প্রতিটি পদ পূর্ববর্তী দুটি পদের সমষ্টি। এটি নিম্নলিখিত পূর্ণসংখ্যা ক্রম −
তৈরি করে0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377…….
পুনরাবৃত্ত সম্পর্ক যা ফিবোনাচি সংখ্যাকে সংজ্ঞায়িত করে তা হল নিম্নরূপ −
F(n) = F(n-1) + F(n-2) F(0)=0 F(1)=1
ফিবোনাচি সিরিজ প্রদর্শনের জন্য প্রোগ্রামগুলি
ফিবোনাচি সিরিজ প্রদর্শনের দুটি পদ্ধতি আছে যেমন ডায়নামিক প্রোগ্রামিং এবং রিকারসিভ প্রোগ্রামিং ব্যবহার করে। এগুলিকে নিম্নরূপ ব্যাখ্যা করা হয়েছে -
ডাইনামিক প্রোগ্রামিং
উদাহরণ
#include<iostream>
using namespace std;
void fib(int n) {
int f[n];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i < n; i++) {
f[i] = f[i-1] + f[i-2];
}
for (i = 0; i < n; i++) {
cout<<f[i]<<" ";
}
}
int main () {
int n = 10;
fib(n);
getchar();
return 0;
} উপরের প্রোগ্রামের আউটপুট নিম্নরূপ।
আউটপুট
0 1 1 2 3 5 8 13 21 34
প্রোগ্রামে, main() হল ড্রাইভার ফাংশন। ফিবোনাচি সিরিজ তৈরির আসল কোডটি fib() ফাংশনে সংরক্ষিত থাকে যা প্রধান থেকে বলা হয়।
একটি অ্যারে f[n] তৈরি করা হয়েছে যা ফিবোনাচি সিরিজের প্রথম n পদ সংরক্ষণ করবে। এই অ্যারের প্রথম এবং দ্বিতীয় উপাদানগুলি যথাক্রমে 0 এবং 1 তে শুরু করা হয়েছে৷
f[0] = 0; f[1] = 1;
তারপর ফর লুপ অ্যারের প্রতিটি উপাদানকে তার আগের দুটি উপাদানের যোগফল হিসাবে সংরক্ষণ করতে ব্যবহৃত হয়।
for (i = 2; i < n; i++) {
f[i] = f[i-1] + f[i-2];
} অবশেষে ফিবোনাচি সিরিজ প্রদর্শিত হয়।
for (i = 0; i < n; i++) {
cout<<f[i]<<" ";
} পুনরাবৃত্ত প্রোগ্রামিং
আসুন দেখি কিভাবে রিকারশন ব্যবহার করে ফিবোনাচি সিরিজ প্রদর্শন করা যায়।
উদাহরণ
#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, i;
for(i=0;i<n;i++)
cout<<fib(i)<<" ";
return 0;
} আউটপুট
0 1 1 2 3 5 8 13 21 34
উপরের প্রোগ্রামে, একটি ফর লুপ সেট করা হয়েছে যা রিকারশন ব্যবহার করে ফিবোনাচি সিরিজের প্রতিটি টার্ম তৈরি করে। সিরিজের প্রতিটি পদের জন্য ফাংশন fib() কল করে এটি করা হয়।
for(i=0;i<n;i++) cout<<fib(i)<<" ";
fib() ফাংশনটি 0 বা 1 প্রদান করে যদি n যথাক্রমে 0 বা 1 হয়। যদি তা না হয়, সঠিক মান ফেরত না আসা পর্যন্ত এটি আগের দুটি পদের যোগফল হিসাবে নিজেকে পুনরাবৃত্তিমূলকভাবে কল করে৷
if (n <= 1) return n; return fib(n-1) + fib(n-2);
