भरे गए सेल
जोड़
टेबल के बिना कॉल

  • भरा जा रहा है
  • यहाँ से पढ़ा
  • उत्तर

गतिशील प्रोग्रामिंग से फ़िबोनाची के बारे में और

गतिशील प्रोग्रामिंग से फ़िबोनाची

फ़िबोनाची संख्याएँ गतिशील प्रोग्रामिंग का सबसे जाना-माना पहला उदाहरण हैं। सामान्य रिकर्शन वही पद बार-बार माँगता है, लेकिन हर पद को याद रखने वाली टेबल से काम केवल n के साथ बढ़ता है। कोई पद चुनें, बॉटम-अप या टॉप-डाउन चुनें, और एक-एक चरण चलकर देखें कि हर सेल केवल एक बार भरता है। टेबल को भरते देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। n, यानी जिस पद को निकालना है, और विधि चुनें: बॉटम-अप टेबल को बाईं ओर से भरता है, टॉप-डाउन रिकर्शन बनाए रखता है पर पहले टेबल में देखता है, और तब टेबल के नीचे की पंक्ति उन कॉल का स्टैक होती है जो अभी पूरी नहीं हुईं। “नया उदाहरण” दूसरा n चुनता है। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।

यह कैसे काम करता है

  1. “पद n” में वह पद n लिखें जिसे निकालना है, और बॉटम-अप या टॉप-डाउन चुनें।
  2. “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें।
  3. देखें कि हर सेल अपने से पहले के दो सेल कैसे पढ़ता है। टॉप-डाउन में, टेबल के नीचे की पंक्ति उन कॉल का स्टैक है जो अभी पूरी नहीं हुईं।

बॉटम-अप और टॉप-डाउन

बॉटम-अप, जिसे टेबुलेशन भी कहते हैं, F(0) = 0 और F(1) = 1 से शुरू होकर टेबल को बाएँ से दाएँ भरता है: हर नया सेल अपने से पहले के दो सेल का योग होता है। टॉप-डाउन, जिसे मेमोइज़ेशन भी कहते हैं, रिकर्सिव परिभाषा को बनाए रखता है: F(n) निकालने के लिए F(n − 1) और F(n − 2) माँगें। सामान्य रिकर्शन से फ़र्क यह है कि हर कॉल पहले टेबल में देखती है, और कोई पद तभी निकालती है जब उसका सेल अभी खाली हो। दोनों हर सेल को एक बार भरते हैं और n − 1 जोड़ करते हैं।

सामान्य रिकर्शन इतना धीमा क्यों है

टेबल के बिना, F(n) F(n − 1) और F(n − 2) को कॉल करता है, वे दोनों F(n − 3) को कॉल करते हैं, और इसी तरह आगे: कॉल एक ट्री बनाती हैं जिसमें वही पद बार-बार आते हैं। कॉल की संख्या 2·F(n + 1) − 1 है, जो उतनी ही तेज़ी से बढ़ती है जितनी फ़िबोनाची संख्याएँ ख़ुद: F(10) के लिए 177 कॉल, F(20) के लिए 21,891 और F(40) के लिए 33 करोड़ से ज़्यादा। ऐसी ओवरलैपिंग सबप्रॉब्लम (एक-दूसरे पर चढ़ी उप-समस्याएँ) के लिए ही गतिशील प्रोग्रामिंग बनी है।

अक्सर पूछे जाने वाले प्रश्न

गतिशील प्रोग्रामिंग क्या है?

किसी समस्या को हल करने का एक तरीका, जिसमें उसे ऐसी छोटी समस्याओं में बाँटा जाता है जो एक-दूसरे पर चढ़ी होती हैं, हर छोटी समस्या एक बार हल की जाती है, और उसका उत्तर एक टेबल में रखा जाता है। फ़िबोनाची संख्याएँ सबसे आसान उदाहरण हैं: हर पद अपने से पहले के दो पदों से बनता है।

मेमोइज़ेशन और टेबुलेशन में क्या फ़र्क है?

मेमोइज़ेशन रिकर्सिव कोड बनाए रखता है और हर उत्तर को पहली बार निकालते ही सहेज लेता है, ताकि बाद की कॉल उसे बस पढ़ लें। टेबुलेशन टेबल को ऐसे क्रम में भरता है कि किसी सेल को जिस उत्तर की ज़रूरत हो, वह पहले से मौजूद रहे। दोनों वही जोड़ करते हैं; टेबुलेशन में कॉल स्टैक की ज़रूरत नहीं पड़ती, और मेमोइज़ेशन केवल वही सेल निकालता है जिनकी सच में ज़रूरत है।

F(n) के लिए कितने जोड़ चाहिए?

टेबल के साथ n − 1: F(2) से F(n) तक हर पद के लिए एक। हमेशा केवल आख़िरी दो पद पढ़े जाते हैं, इसलिए कोई प्रोग्राम पूरी टेबल की जगह केवल दो संख्याएँ भी रख सकता है।

ऐप n = 40 पर क्यों रुकता है?

F(40) = 10,23,34,155 अभी भी स्क्रीन पर आराम से आ जाता है, और सामान्य रिकर्शन को इसके लिए 33,11,60,281 कॉल चाहिए होतीं। इससे बड़े पद तेज़ी से बढ़ते हैं: F(78) सबसे बड़ा पद है जिसे JavaScript की संख्या बिल्कुल सही रख पाती है।

क्या कुछ कहीं भेजा जाता है?

नहीं। सब कुछ आपके ब्राउज़र में ही निकाला जाता है, और आपकी आख़िरी सेटिंग इस ब्राउज़र के लोकल स्टोरेज में रहती हैं।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

एडिटर पर जाएँ