हमें प्रारंभ और अंत संख्याओं वाली रेंज दी गई है और कार्य दी गई रेंज के बीच उपलब्ध फाइबोनैचि संख्याओं की कुल संख्या की गणना करना है O(Log n) समय और O(1) स्पेस में।
फाइबोनैचि संख्याएं क्या हैं
फाइबोनैचि संख्याएं संख्याओं का एक क्रम है जिसे फाइबोनैचि अनुक्रम के रूप में जाना जाता है जहां प्रत्येक नई संख्या पिछली दो पूर्ववर्ती संख्याओं का योग होती है।
जहां, f(0) = 0 और f(1) = 1 यानी f(0) और f(1) का अनुक्रम में निश्चित स्थान है और गणना तीसरी संख्या से शुरू होगी।
अनुक्रम की गणना के लिए उपयोग किया गया सूत्र -
Fn = Fn-1 + Fn-2
जहां,
F0 = 0, F1 = 1
उदाहरण के लिए
इनपुट - प्रारंभ = 6 और अंत = 100 आउटपुट - श्रृंखला में फाइबोनैचि संख्याओं की संख्या 6 है
व्याख्या - 6 और 100 के बीच फाइबोनैचि संख्याएं 8, 13, 21, 34, 55, 89 हैं यानी कुल गिनती 6 है
इनपुट - प्रारंभ = 0 और अंत = 8 आउटपुट - श्रृंखला में फाइबोनैचि संख्याओं की संख्या 7 है
व्याख्या - 0 और 8 के बीच फाइबोनैचि संख्याएं 0, 1, 1, 2, 3, 5, 8 हैं यानी कुल गिनती 7 है
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
रेंज बनाने के लिए प्रारंभ और अंत संख्याएं इनपुट करें
fib1 को 0, fib2 को 1, fib3 को 1 घोषित और आरंभ करें
एक अस्थायी चर res घोषित करें और इसे 0 से आरंभ करें
एक लूप शुरू करें, जब तक fib1 अंत से कम या बराबर है
लूप के अंदर, जांचें कि क्या fib1 प्रारंभ से बड़ा या बराबर है तो res को 1 से बढ़ाएं
fib1 को fib2 पर सेट करें, fib2 को fib3 पर और fib3 को fib1 + fib2 पर सेट करें
res लौटाएं
परिणाम प्रिंट करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
// प्रारंभ से अंत तक की रेंज में फाइबोनैचि संख्याओं को गिनने के लिए फंक्शन
int count_fibonacci(int start, int last) {
// पहले तीन फाइबोनैचि नंबर
int fib1 = 0, fib2 = 1, fib3 = 1;
// फाइबोनैचि की संख्या गिनने के लिए res
int res = 0;
while (fib1 <= last) {
if (fib1 >= start) {
res++;
}
fib1 = fib2;
fib2 = fib3;
fib3 = fib1 + fib2;
}
return res;
}
// मुख्य फंक्शन
int main() {
int start = 6, last = 100;
cout << "Number of fibonacci Numbers in the series are "
<< count_fibonacci(start, last);
return 0;
}
आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा -
Number of fibonacci Numbers in the series are 6
