फाइबोनैचि संख्याएं वे संख्याएं हैं जिनमें पहली दो के बाद श्रृंखला में प्रत्येक संख्या पहले दो की योग होती है। श्रृंखला 1, 1 से शुरू होती है। उदाहरण:
1, 1, 2, 3, 5, 8, 13, 21, 34, …
हम nth उत्पन्न करने के लिए एक प्रोग्राम लिख सकते हैं:
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(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वीं फाइबोनैचि संख्या चाहिए, तो हमें केवल निचली फाइबोनैचि संख्याओं की एक बार आवश्यकता होती है लेकिन हम उन्हें उससे कहीं अधिक बार गणना करते हैं। यदि हम केवल गणना किए गए मानों को कहीं स्टोर कर दें तो हम इस अनावश्यक गणना को कम कर सकते हैं। यह डायनामिक प्रोग्रामिंग का मूल है।
एक बार गणना करें और बाद में पुनः उपयोग करें।
आइए फाइब फ़ंक्शन के मेमोइज़्ड कार्यान्वयन को देखते हैं।
let fibStore = {};
function fibDP(n) {
if (n <= 1) return n;
if (fibStore[n]) {
return fibStore[n];
}
fibStore[n] = fibDP(n - 1) + fibDP(n - 2);
return fibStore[n];
}
अब हम एक स्टोर, fibStore का उपयोग कर रहे हैं ताकि हम उन मानों को ट्रैक कर सकें जिनकी हमने पहले ही गणना कर ली है। यह अत्यधिक अनावश्यक गणनाओं को कम करता है और फ़ंक्शन को कुशल रखता है।
आप इसका परीक्षण इस तरह कर सकते हैं:
console.log(fibDP(7)); console.log(fibDP(8)); console.log(fibDP(9)); console.log(fibDP(4));
इससे निम्न आउटपुट मिलेगा:
13 21 34 3
आप इसे विशाल मानों के लिए भी परीक्षण कर सकते हैं।