এই সমস্যাতে, আমাদের একটি ইন্টিজার N দেওয়া আছে। আমাদের কাজ হল Nth ইভেন ফিবোনাচি সংখ্যা বের করা।
ফিবোনাচি সিরিজ দুটি পূর্ববর্তী সংখ্যা যোগ করে পরবর্তী সংখ্যা তৈরি করে। ফিবোনাচি সিরিজ দুটি সংখ্যা F0 এবং F1 থেকে শুরু হয়। F0 এবং F1-এর প্রাথমিক মান ০, ১ বা ১, ১ নেওয়া যেতে পারে।
উদাহরণ দেখি:
ইনপুট : N = 4 আউটপুট : 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
