सॉर्ट "हनोई का टॉवर"

^{हनोई टावर}
केवल आलसी ने हीबे पर एडुआर्ड ल्यूक के प्रसिद्ध खेल के बारे में नहीं लिखा । ऐसा लगता है कि सभी कवर फटे हुए हैं और एल्गोरिथम के बारे में कुछ और जोड़ना संभव नहीं है। लेकिन नहीं, इस विषय में छिपे हुए संसाधन हैं। आज, विशेष रूप से, हम इस पहेली को पूर्ण रूप से हल करने के लिए एल्गोरिथ्म को फिर से करेंगे। (क्यों? बस मस्ती के लिए। शुक्रवार संभव।)

यह पोस्ट सच्चे प्रोग्रामिंग गुरू आंद्रेई मृग एस्ट्रेलिन की स्मृति को समर्पित है, जिन्होंने कभी इस एल्गोरिथम को मुझे सरल और समझदारी से समझाया था। नीचे दिया गया छद्म कोड उनके लेखक का पाठ है।


क्लासिक पहेली में, पहले पोल पर डिस्क को शुरू में आदेश दिया जाता है। लेकिन हम उन्हें किसी भी क्रम में स्ट्रगल करने देंगे।

इसके अलावा, डिस्क आकार को अद्वितीय माना जाता है। हम इस प्रतिबंध से नहीं चिपके रहेंगे और पुनरावृत्ति की अनुमति देंगे।

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

शेष शर्तें हम (लगभग) नहीं बदलते हैं:

• हमारे पास दो सहायक पोल हैं (खाली सरणियों की एक जोड़ी)।
• हम एक समय में एक डिस्क को स्थानांतरित कर सकते हैं।
• केवल छोटे लोगों को बड़े लोगों के लिए लाना (क्योंकि हमने एक ही डिस्क आकार की अनुमति दी है, हम एक ही आकार के अन्य पर शीर्ष पर स्थानांतरित डिस्क भी डाल सकते हैं)।
• हमें केवल शीर्ष डिस्क के साथ एक पोर्टेबल डिस्क की तुलना करने का अधिकार है (अर्थात, सभी 3 सरणियां स्टैक हैं)।

हमारा काम: क्लासिक पुनरावर्ती पहेली एल्गोरिथ्म लेने के लिए ...

def hanoi(n, source, helper, target): if n > 0: hanoi(n - 1, source, target, helper) if source: target.append(source.pop()) hanoi(n - 1, helper, source, target) 

... और इसे छंटनी में बदल दें!

वास्तव में, इस तथ्य से कि हमने डिस्क के आकार के लिए प्रारंभिक विकार और पुनरावृत्ति की अनुमति दी - इससे अनिवार्य रूप से कुछ भी नहीं बदला है। द्वारा और बड़ी, समस्या को उसी क्लासिक पुनरावर्ती तरीके से हल किया जाता है। समझने के लिए सबसे महत्वपूर्ण बात यह है कि सभी डिस्क आंदोलनों को कई चरणों में विभाजित किया गया है, जिनमें से प्रत्येक एक क्लासिक लघु हनोई है।

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

सिस्टम को शुरू में उल्लंघन किया गया था (इस तथ्य से कि डिस्क को इनपुट पर आदेश नहीं दिया गया है) प्रत्येक पुनरावृत्ति के साथ स्व-चिकित्सा है।

पुनरावृत्ति के संकल्प के लिए, यह बिल्कुल भी मायने नहीं रखता है। क्योंकि लगातार समान डिस्क हम बस एक डिस्क के रूप में चलते हैं।

एल्गोरिथ्म

हम कॉलम को ए , बी , सी ( ए शुरुआत में गैर-रिक्त) कहते हैं।

हम संचालन शुरू करते हैं:

ए -> सी () - एक डिस्क को ए से सी में स्थानांतरित करें ।
शीर्ष (A) , शीर्ष (C) - ऊपरी डिस्क A या C का आकार । यदि कॉलम खाली है, तो यह आकार = MaxInt ।
बी -> सी ( के ) - बी से सी में सभी डिस्क्स को शिफ्ट करें जिनका आकार के से कम है (हम ऐसा कर सकते हैं यदि ऊपरी डिस्क ए और सी के से कम नहीं है)।
स्वैप () - कॉलम बी और सी को पुनर्व्यवस्थित करें (या उनका नाम बदलें - हम परवाह नहीं करते हैं कि डिस्क कहां हैं)।
जबकि ( ए ) - ए खाली होने तक लूप।

फिर निम्नलिखित एल्गोरिथ्म काम करता है:

 //      A    ""  while(A) { K = top(A); //-""    while(top(C) < K){ B->C(top(C)); swap(); } A->C(); } // .  -  "" while(C) { B->C(top(C)); swap(); } 

© Mrrl

जटिलता

सबसे खराब स्थिति में, शास्त्रीय एल्गोरिथ्म के लिए समय की जटिलता को छाँटना, जो कि सरल और सुरुचिपूर्ण है, एक ही समय में अधिकतम अयोग्य है। सबसे अच्छे और औसत के लिए, मुझे यह अनुमान लगाना मुश्किल है।

स्मृति के रूप में, हम कह सकते हैं कि यदि पुनरावृत्ति का उपयोग किया जाता है, तो लागत इसी के अनुरूप होगी।

कार्यान्वयन

मैंने पायथन में अपना खुद का संस्करण नहीं लिखा है (मैं इसे बाद में करूंगा)। हालांकि, नीचे दिए गए "लिंक" अनुभाग में, मैंने कुछ लिंक पोस्ट किए हैं जहां आप विभिन्न भाषाओं में कार्यान्वयन देख सकते हैं। विशेष रूप से जावा में दिलचस्प विकल्प। लेखक ने पहेली को हल करने के लिए प्रसिद्ध पुनरावर्ती पद्धति को आधार नहीं बनाया, बल्कि रास्तों के सबसे छोटे पेड़ का निर्माण किया। संभवतः, यह सबसे प्रभावी उपाय है यदि आप "हनोई के टॉवर" की शैली में छँटाई लिखते हैं।

एल्गोरिदम के लक्षण

संदर्भ

हनोई का टॉवर

कार्यान्वयन: सी , जावा बनाम सी ++ बनाम पायथन , पायथन ।

श्रृंखला लेख:

• एक्सेल आवेदन AlgoLab.xlsm
• एक्सचेंज सॉर्ट
• निवेशन शॉर्ट्स
  • लाइब्रेरियन क्रमबद्ध
  • सॉलिटेयर सॉर्ट
  • सॉर्ट "हनोई का टॉवर"
  • युवा टेबल छँटाई
  • इनवर्ट सॉर्ट करें
  • क्रमबद्ध तुलना डालें
• चयन के आधार पर छाँटें
• मर्ज करना
• वितरण के आधार पर छाँटें
• हाइब्रिड सॉर्टिंग

AlgoLab एप्लिकेशन में, यह सॉर्टिंग अब उपलब्ध है। यद्यपि यह आवेषण के प्रकार के वर्ग के अंतर्गत आता है, एल्गोरिथ्म के अपव्यय के कारण, इसे "अन्य प्रकार" अनुभाग में रखा गया है। एक सीमा भी है - सॉर्ट किए गए सरणी में संख्या केवल 1 से 5 तक हो सकती है (डिस्क के कठिन प्रतिपादन के कारण)। अन्य नंबरों को अभी भी इनसे बदला जाएगा।

सरणी के आकार पर एक सीमा भी है - 20 से अधिक तत्व नहीं। यह विशुद्ध रूप से आपके हित में किया गया था - यदि आप एक ऐसा सरणी लेते हैं जो बहुत बड़ा है, तो ऐसा हो सकता है कि आपको इसे बहुत पुराने समय में सुलझाना पड़े।

यह लेख EDISON सॉफ्टवेयर के समर्थन से लिखा गया था, एक कंपनी जो पेशेवर रूप से स्मार्ट सिटी लाइटिंग विकसित करती है और पायथन साइटों को बनाए रखती है।