इस समस्या में, हमें एक पूर्णांक मान N दिया जाता है। हमारा कार्य 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) को kवां तत्व मानेंगे और इसे Ef(k) के रूप में निरूपित करेंगे। यदि f(n) Ef(k) है, तो f(n-3) पिछली सम संख्या है, जिसे Ef(k-1) द्वारा दर्शाया गया है और इस प्रकार f(n-6), Ef(k-1) का पिछला है। एफई (के-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