फाइबोनैचि श्रृंखला में ऐसी संख्याएँ होती हैं जिनमें प्रत्येक पद पिछले दो पदों का योग होता है। यह निम्नलिखित पूर्णांक अनुक्रम बनाता है -
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377…….
फाइबोनैचि संख्याओं को परिभाषित करने वाला पुनरावर्तन संबंध इस प्रकार है -
F(n) = F(n-1) + F(n-2) F(0)=0 F(1)=1
फिबोनाची श्रृंखला प्रदर्शित करने के लिए कार्यक्रम
फाइबोनैचि श्रृंखला प्रदर्शित करने की दो विधियाँ हैं अर्थात गतिशील प्रोग्रामिंग और पुनरावर्ती प्रोग्रामिंग का उपयोग करना। इन्हें आगे इस प्रकार समझाया गया है -
डायनामिक प्रोग्रामिंग
उदाहरण
#include<iostream>
using namespace std;
void fib(int n) {
int f[n];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i < n; i++) {
f[i] = f[i-1] + f[i-2];
}
for (i = 0; i < n; i++) {
cout<<f[i]<<" ";
}
}
int main () {
int n = 10;
fib(n);
getchar();
return 0;
} उपरोक्त कार्यक्रम का आउटपुट इस प्रकार है।
आउटपुट
0 1 1 2 3 5 8 13 21 34
कार्यक्रम में, मुख्य () ड्राइवर फ़ंक्शन है। फाइबोनैचि श्रृंखला के निर्माण के लिए वास्तविक कोड फ़ंक्शन fib() में संग्रहीत किया जाता है जिसे मुख्य से कहा जाता है।
एक सरणी f[n] बनाई गई है जो फाइबोनैचि श्रृंखला के पहले n पदों को संग्रहीत करेगी। इस सरणी के पहले और दूसरे तत्वों को क्रमशः 0 और 1 से प्रारंभ किया जाता है।
f[0] = 0; f[1] = 1;
फिर लूप के लिए सरणी में प्रत्येक तत्व को उसके पिछले दो तत्वों के योग के रूप में संग्रहीत करने के लिए उपयोग किया जाता है।
for (i = 2; i < n; i++) {
f[i] = f[i-1] + f[i-2];
} अंत में फाइबोनैचि श्रृंखला प्रदर्शित होती है।
for (i = 0; i < n; i++) {
cout<<f[i]<<" ";
} पुनरावर्ती प्रोग्रामिंग
आइए देखें कि रिकर्सन का उपयोग करके फाइबोनैचि श्रृंखला कैसे प्रदर्शित करें।
उदाहरण
#include<iostream>
using namespace std;
int fib(int n) {
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main () {
int n = 10, i;
for(i=0;i<n;i++)
cout<<fib(i)<<" ";
return 0;
} आउटपुट
0 1 1 2 3 5 8 13 21 34
उपरोक्त कार्यक्रम में, एक लूप के लिए सेट किया गया है जो रिकर्सन का उपयोग करके फाइबोनैकी श्रृंखला के प्रत्येक शब्द को बनाता है। यह श्रृंखला में प्रत्येक पद के लिए फ़ंक्शन fib() को कॉल करके किया जाता है।
for(i=0;i<n;i++) cout<<fib(i)<<" ";
फ़ंक्शन फ़ाइब () 0 या 1 देता है यदि n क्रमशः 0 या 1 है। यदि नहीं, तो यह स्वयं को पुनरावर्ती रूप से पिछले दो पदों के योग के रूप में तब तक कहता है जब तक कि सही मान वापस न आ जाए।
if (n <= 1) return n; return fib(n-1) + fib(n-2);