এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যার মান দেওয়া হয়েছে। আমাদের কাজ হল Nth ইভেন ফিবোনাচি নম্বর খুঁজে পাওয়া .
ফিবোনাচি সিরিজ দুটি পূর্ববর্তী সংখ্যা যোগ করে পরবর্তী সংখ্যা তৈরি করে। ফিবোনাচি সিরিজ দুটি সংখ্যা থেকে শুরু হয় - F0 এবং F1। F0 এবং F1 এর প্রাথমিক মান যথাক্রমে 0, 1 বা 1, 1 নেওয়া যেতে পারে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : N = 4 Output : 144
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল এই সত্যটি ব্যবহার করা যে ফিবোনাচি অনুক্রমের প্রতিটি তৃতীয় সংখ্যা জোড় এবং জোড় সংখ্যার ক্রমও পুনরাবৃত্তিমূলক সূত্র অনুসরণ করে।
এমনকি ফিবোনাচি সিকোয়েন্সের পুনরাবৃত্তিমূলক সূত্র হল −
Ef(n)=4Ef(n-1) + Ef(n-2) যেখানে Ef(0)=0 এবং Ef(1)=2
আমরা জানি যে প্রতি তৃতীয় ফিবোনাচি সংখ্যা সমান, এইভাবে f(n-3) এবং f(n-6) উভয়ই জোড়। সুতরাং, আমরা f(n) কে kth উপাদান হিসাবে বিবেচনা করব এবং Ef(k) হিসাবে চিহ্নিত করব। যদি f(n) হয় Ef(k), তাহলে f(n-3) হল পূর্ববর্তী জোড় সংখ্যা Ef(k-1) দ্বারা চিহ্নিত এবং এইভাবে f(n-6) হল Ef(k-1) এর আগের হল Ef(k-2)।
এইভাবে f(n)=4f(n-3)+f(n-6)
অথবা, Ef(k)=4Ef(k-1) + Ef(k-2)।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include<iostream>
using namespace std;
int findNthEvenFiboNum(int n){
if (n < 1)
return n;
if (n == 1)
return 2;
return ((4 * findNthEvenFiboNum(n-1)) + findNthEvenFiboNum(n- 2));
}
int main (){
int n = 5;
cout<<n<<"th even fibonacci number is "<<findNthEvenFiboNum(n);
return 0;
} আউটপুট
5th even fibonacci number is 610
