- भरा जा रहा है
- यहाँ से पढ़ा
- उत्तर
सबसे लंबा बढ़ता उपक्रम (LIS)
संख्याओं की एक सूची में से, उनका क्रम बनाए रखते हुए, आप कितनी संख्याएँ चुन सकते हैं कि हर संख्या पिछली से बड़ी हो? सबसे लंबा बढ़ता उपक्रम इसी का उत्तर है। एक सूची लिखें और देखें कि गतिशील प्रोग्रामिंग हर स्थान के लिए वहाँ खत्म होने वाला सबसे लंबा क्रम कैसे निकालती है। तालिका को भरते देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। संख्याओं की एक सूची लिखें। हर स्थान के लिए तालिका उस सबसे लंबे बढ़ते क्रम की लंबाई रखती है जो वहाँ खत्म होता है, और वह पिछला स्थान भी जिसे यह क्रम आगे बढ़ाता है। ऐसे क्रम के लिए जो कभी नीचे न जाए, “बराबर मानों की अनुमति दें” पर टिक करें। अंत में क्रम को उसके आखिरी मान से पीछे की ओर पढ़ा जाता है। “नया उदाहरण” दूसरी सूची बनाता है। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- संख्याओं की एक सूची लिखें, अल्पविराम या स्पेस से अलग करके। ऐसे क्रम के लिए जो कभी नीचे न जाए, “बराबर मानों की अनुमति दें” पर टिक करें।
- “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का उपयोग करें। कहीं भी जाने के लिए चरण स्लाइडर खींचें।
- हर स्थान की हर पिछले स्थान से तुलना होते देखें, फिर सबसे लंबे क्रम को नारंगी रंग में पीछे से पढ़ा जाता देखें।
तालिका कैसे काम करती है
तालिका में तीन पंक्तियाँ हैं: मान, हर स्थान पर खत्म होने वाले सबसे लंबे बढ़ते उपक्रम की लंबाई, और वह स्थान जिसे यह आगे बढ़ाता है। अकेला मान लंबाई 1 का क्रम है। फिर हर पिछले स्थान की जाँच होती है: अगर उसका मान छोटा है, तो वहाँ खत्म होने वाले क्रम को इस मान से बढ़ाया जा सकता है, जिससे उसकी लंबाई से एक ज़्यादा मिलता है। ऐसा सबसे लंबा विस्तार जीतता है, और उसका स्थान तीसरी पंक्ति में जाता है।
क्रम को पीछे से पढ़ना
सबसे लंबा बढ़ता उपक्रम उस स्थान पर खत्म होता है जिसकी लंबाई सबसे ज़्यादा है। वहाँ से तीसरी पंक्ति बताती है कि उससे पहले कौन-सा स्थान आता है, और उस स्थान की तीसरी पंक्ति बताती है कि उससे पहले कौन-सा, जब तक ऐसा स्थान न आ जाए जिससे पहले कोई नहीं है। इन मानों को क्रम से पढ़ें, तो यही उत्तर है। “बराबर मानों की अनुमति दें” पर टिक होने पर, कोई मान अपने बराबर मान के बाद भी आ सकता है, जिससे कभी नीचे न जाने वाला सबसे लंबा क्रम मिलता है।
अक्सर पूछे जाने वाले प्रश्न
उपक्रम और उप-ऐरे में क्या अंतर है?
उप-ऐरे पास-पास के मानों का एक खंड है। उपक्रम क्रम बनाए रखता है पर मान छोड़ सकता है, इसलिए 3, 10, 2, 1, 20 में 3, 10 और 20 मान एक बढ़ता उपक्रम बनाते हैं, भले ही उनके बीच 2 और 1 हैं।
LIS एल्गोरिदम कितना तेज़ है?
तालिका वाला तरीका स्थानों के हर जोड़े की तुलना करता है: n मानों के लिए n·(n − 1)/2 तुलनाएँ। पेशेंस सॉर्टिंग यह O(n log n) में करती है: यह हर लंबाई के लिए उस लंबाई का क्रम खत्म करने वाला सबसे छोटा मान रखती है, और हर नए मान को बाइनरी सर्च से उसकी जगह रखती है।
क्या सबसे लंबा बढ़ता उपक्रम एक ही होता है?
हमेशा नहीं। 1, 3, 2, 4 में 1, 3, 4 और 1, 2, 4 दोनों की लंबाई 3 है। तालिका लंबाई बताती है, और पीछे से पढ़ना इनमें से एक को ढूँढता है।
सबसे लंबा बढ़ता उपक्रम कहाँ उपयोग होता है?
फ़ाइलों और जीनोम की तुलना में, जहाँ कुछ तरीके पहले मिलती-जुलती पंक्तियाँ ढूँढते हैं और फिर उनके स्थानों का एक बढ़ता उपक्रम लेते हैं; शेड्यूलिंग और डिब्बे जमाने वाली पहेलियों में; और गणित में, जहाँ किसी यादृच्छिक फेरबदल के LIS की लंबाई अध्ययन का एक प्रसिद्ध विषय है।
क्या कुछ कहीं भेजा जाता है?
नहीं। सब कुछ आपके ब्राउज़र में ही निकाला जाता है, और आपकी पिछली सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ