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

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

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

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

N = 5

आउटपुट

10

समाधान दृष्टिकोण

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

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

एल्गोरिदम

• तीन चर बनाएं जो वर्तमान तत्व, पिछले तत्व और पिछले तत्व का ट्रैक रखेंगे।

• जबकि गैर फाइबोनैचि की संख्या ऋणात्मक नहीं है, फाइबोनैचि संख्या के सरल सूत्र का उपयोग करें - Fib(n)=Fib(n-1)+Fib(n-2)।

• सूत्र n=n+(curr-prev-1) का उपयोग करके गैर फाइबोनैचि संख्याओं की गणना प्राप्त करने के लिए।

• 
  

• अब nवीं गैर फाइबोनैचि संख्या प्राप्त करने के लिए पिछली संख्या को n से घटाएं।

उदाहरण

हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम

#include<iostream>
using namespace std;
int findNthNonFiboNumber(int n){
   int lastLastVal = 1, lastVal = 2, currVal = 3;
   while (n > 0){
      lastLastVal = lastVal;
      lastVal = currVal;
      currVal = lastLastVal + lastVal;
      n = n - (currVal - lastVal - 1);
   }
   n = n + (currVal - lastVal - 1);
   return (lastVal + n);
}
int main(){
   int n = 7;
   cout<<"Nth non fibonacci number is "<<findNthNonFiboNumber(n);
   return 0;
}

आउटपुट

Nth non fibonacci number is 12