जावास्क्रिप्ट में फाइबोनैचि अनुक्रम

फाइबोनैचि संख्याएँ ऐसी संख्याएँ हैं, जो पहले दो के बाद की श्रृंखला में प्रत्येक संख्या दो पूर्ववर्ती संख्याओं का योग होती हैं। श्रृंखला 1 से शुरू होती है। उदाहरण -

1, 1, 2, 3, 5, 8, 13, 21, 34, ….

हम निम्नानुसार nth उत्पन्न करने के लिए एक प्रोग्राम लिख सकते हैं -

functionfibNaive(n) {
   if (n<= 1) return n;
   returnfibNaive(n - 1) + fibNaive(n - 2);
}

आप -

console.log(fibNaive(7));
console.log(fibNaive(8));
console.log(fibNaive(9));
console.log(fibNaive(4));

यह आउटपुट देगा -

13
21
34
3

आइए देखें कि ये फ़ंक्शन कॉल वास्तव में कैसे हो रहे हैं -

/**
* f(5)
* / \
* f(4) f(3)
* / \ / \
* f(3) f(2) f(2) f(1)
* / \ ..........
* f(2) f(1)..........
*/

जब हम f(5) पर कॉल करते हैं, तो हम f(2) को लगभग 4 बार कॉल करेंगे और यह एक ही कोड को 4 से अधिक बार चलाएगा। यह एक अतिव्यापी उपसमस्या का मामला है। उस फ़ंक्शन को 500 के लिए चलाने का प्रयास करें। आप फंस जाएंगे क्योंकि इन सभी कॉलों में बहुत समय लगेगा।

जब हमें 5वीं फिबोनाची संख्या की आवश्यकता होती है, तो हमें केवल एक बार निम्न फाइबोनैचि संख्याओं की आवश्यकता होती है, लेकिन हम उनकी गणना उससे कई गुना अधिक करते हैं। हम इस निरर्थक गणना को कम कर सकते हैं यदि हम इसके बजाय गणना किए गए मानों को कहीं संग्रहीत करते हैं। यह गतिशील प्रोग्रामिंग का मूलमंत्र है।

एक बार गणना करें और बाद में पुन:उपयोग करें।

आइए फ़ाइब फ़ंक्शन के याद किए गए कार्यान्वयन को देखें।

letfibStore = {};
functionfibDP(n) {
   if (n<= 1) return n;
if (fibStore[n]) {
   returnfibStore[n];
}
   fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
   returnfibStore[n];
}

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

आप -

console.log(fibDP(7));
console.log(fibDP(8));
console.log(fibDP(9));
console.log(fibDP(4));

यह आउटपुट देगा -

13
21
34
3

आप इसका परीक्षण बड़े मूल्यों के लिए भी कर सकते हैं।