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

समस्या विवरण

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

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

उदाहरण

इनपुट

N = 5

आउटपुट

10

व्याख्या: फाइबोनैचि संख्याएं: 0, 1, 1, 2, 3, 5, 8, 13... गैर-फाइबोनैचि: 4, 6, 7, 9, 10... 5वीं गैर-फाइबोनैचि = 10

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

समस्या का एक सरल समाधान फाइबोनैचि संख्याओं को खोजना और फिर पहली n संख्याओं को प्रिंट करना है जो फाइबोनैचि संख्याओं में मौजूद नहीं हैं।

एक अन्य समाधान फाइबोनैचि संख्या सूत्र का उपयोग करना है और फिर दो फाइबोनैचि संख्याओं के बीच के अंतर को लगातार जोड़ना है। अंत में, सभी अंतरों का योग वांछित आउटपुट में परिणत होगा।

एल्गोरिदम

1. वर्तमान तत्व, पिछला तत्व और उससे पिछला तत्व ट्रैक करने के लिए तीन चर बनाएं
2. जब तक गैर-फाइबोनैचि की गिनती गैर-ऋणात्मक है, फाइबोनैचि संख्या के सरल सूत्र का उपयोग करें - Fib(n) = Fib(n-1) + Fib(n-2)
3. गैर-फाइबोनैचि संख्याओं की गिनती प्राप्त करने के लिए सूत्र n = n + (curr - prev - 1) का उपयोग करें
4. Nवीं गैर-फाइबोनैचि संख्या प्राप्त करने के लिए पिछली संख्या को n से घटाएं

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

#include <iostream> 
using namespace std; 

int findNthNonFiboNumber(int n) {
    int prevPrev = 1, prev = 2, curr = 3;
    while (n > 0) {
        prevPrev = prev;
        prev = curr;
        curr = prevPrev + prev;
        n = n - (curr - prev - 1);
    }
    n = n + (curr - prev - 1);
    return (prev + n);
}

int main() {
    int n = 7;
    cout << "Nवीं गैर-फाइबोनैचि संख्या है " << findNthNonFiboNumber(n);
    return 0;
}

आउटपुट

Nवीं गैर-फाइबोनैचि संख्या है 12

कार्यविधि समझ

दो क्रमागत फाइबोनैचि संख्याओं F(k) और F(k+1) के बीच, (F(k+1) - F(k) - 1) गैर-फाइबोनैचि संख्याएं होती हैं।

• F(3)=2, F(4)=3 → 0 गैर-फाइबोनैचि
• F(4)=3, F(5)=5 → 1 गैर-फाइबोनैचि: 4
• F(5)=5, F(6)=8 → 2 गैर-फाइबोनैचि: 6, 7
• F(6)=8, F(7)=13 → 4 गैर-फाइबोनैचि: 9, 10, 11, 12

हम इन गिनतियों को N से घटाते रहते हैं जब तक N ≤ 0 न हो जाए, फिर उत्तर निकालते हैं।

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

• समय जटिलता: O(log N) - फाइबोनैचि संख्याएं घातीय रूप से बढ़ती हैं
• स्पेस जटिलता: O(1)