C++ में Nवीं सम फाइबोनैचि संख्या खोजने का प्रोग्राम

समस्या विवरण

इस समस्या में, हमें एक पूर्णांक मान N दिया गया है। हमारा कार्य Nवीं सम फाइबोनैचि संख्या खोजना है।

फाइबोनैचि श्रृंखला पिछली दो संख्याओं को जोड़कर बाद की संख्या उत्पन्न करती है। फाइबोनैचि श्रृंखला दो संख्याओं से शुरू होती है - F0 और F1। F0 और F1 के प्रारंभिक मान 0, 1 या 1, 1 लिए जा सकते हैं।

उदाहरण

इनपुट: N = 4
आउटपुट: 144

हल का दृष्टिकोण

समस्या का एक सरल समाधान इस तथ्य का उपयोग करना है कि फाइबोनैचि अनुक्रम में हर तीसरी संख्या सम होती है और सम संख्याओं का अनुक्रम भी पुनरावर्ती सूत्र का पालन करता है।

सम फाइबोनैचि अनुक्रम के लिए पुनरावर्ती सूत्र है:

Ef(n) = 4×Ef(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) का पिछला है जो Ef(k-2) है।

इस प्रकार f(n) = 4f(n-3) + f(n-6)

या, Ef(k) = 4×Ef(k-1) + Ef(k-2)।

C++ कार्यान्वयन

#include <iostream> 
using namespace std; 

int findNthEvenFiboNum(int n) {
    if (n < 1)
        return 0;
    if (n == 1)
        return 2;
    return ((4 * findNthEvenFiboNum(n-1)) + findNthEvenFiboNum(n-2));
}

int main() {
    int n = 5;
    cout << n << "वीं सम फाइबोनैचि संख्या है " << findNthEvenFiboNum(n);
    return 0;
}

आउटपुट

5वीं सम फाइबोनैचि संख्या है 610

अनुकूलित पुनरावृत्तिमूलक संस्करण

int findNthEvenFiboNumIterative(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 2;
    
    long long a = 0, b = 2; // Ef(0), Ef(1)
    for (int i = 2; i <= n; i++) {
        long long c = 4 * b + a;
        a = b;
        b = c;
    }
    return b;
}

जटिलता विश्लेषण

सम फाइबोनैचि अनुक्रम

पहली कुछ सम फाइबोनैचि संख्याएं: 0, 2, 8, 34, 144, 610, 2584, 10946, ...

ये F(0), F(3), F(6), F(9), F(12), ... से मेल खाती हैं।