अतिरिक्त शर्तों के साथ, सरणी में संभावित अनुक्रमों की संख्या ढूँढना

Question

अनुक्रम {ए 1, ए 2, ए 3, ए 4, ..... एएन} है। एक रन अनुक्रम का अधिकतम सख्ती से बढ़ रहा है या सख्ती से लगातार घट रहा है। उदाहरण के लिए। अगर हमारे पास अनुक्रम है {1,2,3,4,7,6,5,2,3,4,1,2} हमारे पास 5 संभावित रन हैं {1,2,3,4,7}, {7, 6,5,2}, {2,3,4}, {4,1} और {1,2}।

चार संख्याओं एन, एम, के, एल को देखते हुए एन संख्याओं के संभावित अनुक्रमों की संख्या की गणना करें जिनमें सटीक एम चलता है, अनुक्रम में प्रत्येक संख्या के बराबर या उसके बराबर होती है और आसन्न संख्याओं के बीच अंतर होती है एल

के बराबर से कम है, एक साक्षात्कार के दौरान सवाल पूछा गया था।

मैं केवल एक ब्रूट फोर्स समाधान के बारे में सोच सकता हूं। इस समस्या के लिए एक कुशल समाधान क्या है?

Answer 1

मुझे लगता है कि आप 'ब्रूट फोर्स सॉल्यूशन' का मतलब है जिसका मतलब है कि 'एन, एम, के, एल' पर नेस्टेड-लूप को शामिल करने के लिए सीधा समाधान 'क्या हो सकता है? कभी-कभी सीधा समाधान काफी अच्छा होता है। उन समयों में से एक जब सीधा समाधान पर्याप्त अच्छा होता है तब आपके पास बेहतर समाधान नहीं होता है। एक और समय यह है कि संख्याएं बहुत बड़ी नहीं हैं।

इसी के साथ बंद मेरे सीने मैं विपरीत दिशा में छोरों लिखते हैं, या ऐसा ही कुछ होगा। मेरा मतलब है:

1. 2 सहायक डेटा संरचनाओं बनाएँ, एक संख्या < = कश्मीर, संख्या अपने पड़ोसियों के साथ जिसका अंतर < = एल है के सूचकांकों के लिए एक के सूचकांकों को रोकने के लिए।
2. संख्याओं की सूची के माध्यम से चलाएं और पूर्वगामी सहायक डेटा संरचनाओं को पॉप्युलेट करें।
3. उन 2 डेटा संरचनाओं में मूल्यों का चौराहे खोजें; रनों की खोज शुरू करने के लिए ये दिलचस्प जगहों के सूचकांक होंगे।
4. प्रत्येक दिलचस्प जगहों में देखें।

अन्यथा इस सबसे कारगर उपाय है जब तक किसी को दर्शाता है।

Answer 2

गतिशील प्रोग्रामिंग का उपयोग करें। सबस्ट्रिंग में प्रत्येक संख्या के लिए अधिकतम वृद्धि और अधिकतम घटते हुए बाद की अलग-अलग गणना बनाए रखें। जब आप अंत में एक नई संख्या को अंत में जोड़ते हैं तो आप नए नंबर के लिए गणनाओं को अपडेट करने के लिए इन गणनाओं का उपयोग कर सकते हैं। जटिलता: O (n^2)

Answer 3

यह एक पुनरावृत्ति समस्या के रूप में rephrased जा सकता है। # (एन, एम) ढूंढने के रूप में अपनी समस्या को देखें (मान लें कि के और एल तय हैं, उनका पुनरावृत्ति परिस्थितियों में उपयोग किया जाता है, इसलिए तदनुसार प्रचार करें)। अब अधिक प्रतिबंधित गणना कार्यों ए (एन, एम; ए) और डी (एन, एम, ए) के साथ शुरू करें, जहां ए अंतिम सेट आरोही के साथ उन सेटों की गणना करता है, डी अंतिम रन अवरोही वाले लोगों की गणना करता है, और यह मान है सेट में अंतिम तत्व।

एक्सप्रेस एक के मामले में # (एन, एम) (एन, एम; क) और डी (एन, एम; क) (इस पर योग है सब स्वीकार्य क)। आप ध्यान दें कि दोनों के बीच संबंध हैं (जैसे प्रतिबिंब ए (एन, एम; ए) = डी (एन, एम; के-ए)) लेकिन इससे गति तालिका भरने के अलावा गणना के लिए कोई फर्क नहीं पड़ता।

अब ए (एन, एम; ए) ए (एन -1, एम; डब्ल्यू), ए (एन -1, एम -1, एक्स), डी (एन -1, एम) के संदर्भ में व्यक्त किया जा सकता है। ; वाई) और डी (एन -1, एम -1; जेड)। विचार यह है कि यदि आप आकार एन -1 के सेट से शुरू करते हैं और अंतिम भाग की दिशा और अंतिम तत्व के मान को जानते हैं, तो आप जानते हैं कि तत्व जोड़ना मौजूदा रन में जोड़ देगा या रन जोड़ देगा। तो आप पिछले मामले की संभावनाओं से प्राप्त करने के संभावित तरीकों की संख्या को गिन सकते हैं।

मैं आपको यह रिकर्सन लिखने दूँगा। ध्यान दें कि यह वह जगह है जहां आप एल के लिए खाते हैं (केवल उन लोगों को जोड़ें जो एल दूरी प्रतिबंध का पालन करते हैं) और के (अंतिम मामलों की तलाश करें)।

तथ्य का उपयोग कर प्रत्यावर्तन बर्खास्त कि एक (1, 1, एक) = 1, ए (1, x> 1; क) = 0 (और इसी तरह डी के लिए)।

अब, के बाद से इस एक बहु प्रत्यावर्तन है, यकीन है कि एक तालिका में अपने कार्यान्वयन भंडार परिणाम हो सकता है और देखने की कोशिश कर रहा से शुरू होता है (आमतौर पर गतिशील प्रोग्रामिंग कहा जाता है)।