Tower of Hanoi में महारत कैसे हासिल करें
संक्षेप में: Tower of Hanoi एक पुनरावर्ती नियम से हल होता है: n डिस्क को लक्ष्य खूंटी पर ले जाने के लिए, पहले n-1 डिस्क को मध्य खूंटी पर ले जाएं, फिर सबसे बड़ी डिस्क को लक्ष्य पर ले जाएं, फिर n-1 डिस्क को ऊपर ले जाएं। इस नियम को हर स्तर पर लागू करें और आप हमेशा न्यूनतम चाल गिनती तक पहुंचेंगे। न्यूनतम हमेशा दो की शक्ति से एक कम है: 3 डिस्क को 7 चाल चाहिए, 4 डिस्क को 15, 5 को 31, 6 को 63, 7 को 127।
खेल क्या है
Tower of Hanoi बाईं खूंटी पर डिस्क के एक ढेर से शुरू होता है, सबसे बड़ी नीचे, सबसे छोटी ऊपर। आपका लक्ष्य: पूरे ढेर को दाईं खूंटी पर ले जाना, दो नियमों का पालन करते हुए। एक समय में एक डिस्क ले जाएं। कभी भी छोटी डिस्क के ऊपर बड़ी डिस्क न रखें।
बस इतना ही। कोई टाइमर नहीं, कोई यादृच्छिकता नहीं, कोई छिपी जानकारी नहीं। बस तर्क और चाल बजट।
PlayMemorize 3 से 7 डिस्क तक स्केल करता है। चाल बजट इष्टतम न्यूनतम से ऊपर शुरू होता है ताकि शुरुआती लोग पैटर्न सीखते हुए भी जीत सकें; जैसे-जैसे आपका स्तर बढ़ता है, बजट गणितीय न्यूनतम की ओर कस जाता है।
न्यूनतम चाल गिनती: 3 डिस्क = 7 चाल, 4 डिस्क = 15 चाल, 5 डिस्क = 31 चाल, 6 डिस्क = 63 चाल, 7 डिस्क = 127 चाल। प्रत्येक स्तर को नीचे के स्तर से लगभग दोगुनी चाल चाहिए, साथ में एक। यदि आप चाल बजट से अधिक जाते हैं, तो राउंड हार के रूप में समाप्त होता है।
पुनरावर्ती एल्गोरिदम
Tower of Hanoi में सब कुछ एक पैटर्न से आता है, जिसे हर पैमाने पर बार-बार लागू किया जाता है:
खूंटी B को अस्थायी भंडारण के रूप में उपयोग करते हुए खूंटी A से खूंटी C पर n डिस्क ले जाने के लिए:
- n-1 डिस्क A से B पर ले जाएं (C को अस्थायी के रूप में उपयोग करते हुए)
- सबसे बड़ी डिस्क A से C पर ले जाएं
- n-1 डिस्क B से C पर ले जाएं (A को अस्थायी के रूप में उपयोग करते हुए)
यह पूरा एल्गोरिदम है। पहेली के हर स्तर पर, आप यही तीन-चरण संरचना निष्पादित कर रहे हैं। प्रतिभा यह है कि चरण 1 और 3 स्वयं एक ही समस्या के छोटे उदाहरण हैं, उसी नियम द्वारा हल किए गए।
आइए 3 डिस्क के माध्यम से ट्रेस करें। लक्ष्य: तीनों को खूंटी 1 से खूंटी 3 पर ले जाएं।
- चरण 1 (2 डिस्क खूंटी 1 से खूंटी 2 पर ले जाएं): डिस्क 1 को खूंटी 3 पर, डिस्क 2 को खूंटी 2 पर, डिस्क 1 को खूंटी 2 पर ले जाएं।
- चरण 2 (डिस्क 3 को खूंटी 1 से खूंटी 3 पर ले जाएं): एक चाल।
- चरण 3 (2 डिस्क खूंटी 2 से खूंटी 3 पर ले जाएं): डिस्क 1 को खूंटी 1 पर, डिस्क 2 को खूंटी 3 पर, डिस्क 1 को खूंटी 3 पर ले जाएं।
कुल: 7 चाल। इष्टतम।
तीन-चरण सोच। किसी भी डिस्क को छूने से पहले, तीन चरणों को जोर से नाम दें: “n-1 डिस्क मध्य में साफ करें; सबसे बड़ी को लक्ष्य पर ले जाएं; n-1 डिस्क ऊपर पुनर्निर्माण करें।” हर पुनरावृत्ति स्तर पर, आप एक कम डिस्क के साथ यही संरचना दोहरा रहे हैं। आप एक चाल अनुक्रम याद नहीं कर रहे - आप एक भग्न पैटर्न निष्पादित कर रहे हैं।
सुझाव: कोई भी चाल करने से पहले पूछें: “अभी मुझे कौन सी सबसे बड़ी डिस्क ले जानी है?” जब तक आप वह डिस्क नहीं ले जाते, आप जो कुछ भी करते हैं वह तैयारी है। यह ढांचा रखने से उद्देश्यहीन चालें रुकती हैं और आप इष्टतम पथ पर रहते हैं।
चाल गिनती क्यों निश्चित है
न्यूनतम चाल गिनती सीधे एल्गोरिदम से आती है। n डिस्क हल करने के लिए n-1 डिस्क दो बार हल करना होता है (चरण 1 और 3) साथ में सबसे बड़ी डिस्क की एक चाल (चरण 2)। तो कुल T(n) = 2 गुना T(n-1) जमा 1। T(1) = 1 के साथ, यह विस्तारित होता है: 1, 3, 7, 15, 31, 63, 127 डिस्क गिनती 1 से 7 के लिए।
प्रत्येक संख्या दो की शक्ति से एक कम है। तीन डिस्क: 8 घटा 1 = 7। चार डिस्क: 16 घटा 1 = 15। पांच डिस्क: 32 घटा 1 = 31। छह डिस्क: 64 घटा 1 = 63। सात डिस्क: 128 घटा 1 = 127।
यह संयोग नहीं है - यह n डिस्क हल करते समय n-1 डिस्क दो बार हल करने का प्रत्यक्ष परिणाम है। एक बार जब आप इसे समझते हैं, तो आप Hanoi को अनुमान लगाकर हल करने वाली पहेली के रूप में देखना बंद कर देते हैं और इसे निष्पादित करने वाले एल्गोरिदम के रूप में देखने लगते हैं।
कठिनाई के अनुसार रणनीति
3 से 4 डिस्क (सीखना): इस स्तर पर, चाल बजट आरामदायक है। प्रत्येक डिस्क को मानसिक रूप से नाम देने पर ध्यान दें - “छोटी,” “मध्यम,” “बड़ी” - ताकि आप कभी भ्रमित न हों। कुछ भी छूने से पहले तीन चरणों के माध्यम से ट्रेस करें। प्रत्येक खेल के बाद, चरणों को जोर से समझाएं।
सुझाव: पूर्ण समाधान में सबसे बड़ी डिस्क ठीक एक बार ले जानी चाहिए। यदि आप इसे फिर से ले जाना चाहते हैं, तो आपने एल्गोरिदम संरचना तोड़ दी है। सबसे बड़ी डिस्क की एकल चाल एक मील का पत्थर है - इससे पहले सब कुछ रास्ता साफ करना है; बाद में सब कुछ ऊपर ढेर करना है।
5 से 6 डिस्क (मध्यवर्ती): चाल बजट कस जाता है। प्रत्येक भटकने वाली चाल आपको महंगी पड़ती है। प्रत्येक स्तर पर पुनरावर्ती एल्गोरिदम को सख्ती से लागू करें। जब आप n से n-1 डिस्क पर पुनरावृत्त होते हैं, तो आपका मानसिक ध्यान बदलना चाहिए: आप अब एक अलग “स्रोत,” “लक्ष्य,” और “सहायक” खूंटियों के साथ एक छोटी Hanoi पहेली हल कर रहे हैं।
सहायक खूंटी स्वैप। पुनरावृत्ति के प्रत्येक स्तर पर, एक खूंटी स्रोत है, एक लक्ष्य है, और एक सहायक है। जैसे-जैसे आप पुनरावृत्त होते हैं ये भूमिकाएं बदलती हैं। जब खूंटी 1 से खूंटी 2 पर n-1 डिस्क ले जाते हैं, तो खूंटी 3 सहायक है। इस स्वैप को होशपूर्वक ट्रैक करें - यह 5 और 6 डिस्क पर भ्रम का सबसे आम स्रोत है।
7 डिस्क (चुनौती): 127 न्यूनतम चालों और तंग बजट के साथ, आप चाल दर चाल नहीं सोच सकते। चरण दर चरण सोचें। शुरू करने से पहले, शीर्ष-स्तरीय संरचना मैप करें: 6 डिस्क मध्य में ले जाएं (63 चाल), सबसे बड़ी डिस्क दाईं ओर ले जाएं (1 चाल), 6 डिस्क दाईं ओर ले जाएं (63 चाल)। फिर प्रत्येक 6-डिस्क चरण को उसी तरह विभाजित करें।
सावधान रहें: 7 डिस्क पर, अनुक्रम को चाल दर चाल याद करने की कोशिश करना अविश्वसनीय और अनावश्यक है। एल्गोरिदम पर भरोसा करें। जब आप हर शाखा बिंदु पर पुनरावर्ती नियम लागू करते हैं, तो सही चाल हमेशा निर्धारित होती है। संदेह और दूसरा अनुमान लगाना यह है कि आप चाल जलाते हैं और बजट समाप्त करते हैं।
सामान्य गलतियां
इसे परीक्षण-और-त्रुटि पहेली की तरह मानना। यादृच्छिक चालें कभी-कभी उत्पादक लगती हैं लेकिन मृत अंत में समाप्त होती हैं। Hanoi एक एल्गोरिदम है, प्रयोग द्वारा हल की जाने वाली पहेली नहीं। अपनी सोच से यादृच्छिकता को पूरी तरह हटा दें।
खूंटी भूमिकाओं का ट्रैक खोना। तीन समान खूंटियों पर, “स्रोत,” “लक्ष्य,” और “सहायक” एक साथ धुंधले हो सकते हैं, विशेष रूप से उच्च डिस्क गिनती पर। शुरू करने से पहले, अपने मन में खूंटियों को स्पष्ट रूप से लेबल करें: बाएं = प्रारंभ, केंद्र = मध्य, दाएं = लक्ष्य।
सबसे बड़ी डिस्क को एक से अधिक बार ले जाना। पुनरावृत्ति के शीर्ष स्तर पर, सबसे बड़ी डिस्क ठीक एक बार ले जाती है। यदि आप इसे फिर से ले जाना चाहते हैं, तो रुकें - एल्गोरिदम संरचना टूट गई है। तीन-चरण ढांचे पर वापस जाएं।
सबसे बड़ी डिस्क चेकपॉइंट। पुनरावृत्ति के प्रत्येक स्तर पर, n-वीं डिस्क को ठीक एक बार ले जाना चाहिए। पहले उप-चरण (n-1 डिस्क को सहायक खूंटी पर ले जाना) के बाद, n-वीं डिस्क मुक्त और न ले जाई हुई होनी चाहिए। चरण 2 के बाद, यह लक्ष्य खूंटी पर होनी चाहिए। यदि नहीं, तो आप एल्गोरिदम से भटक गए हैं।
चालें खत्म हो जाना। यह केवल तब होता है जब आप एल्गोरिदम का पालन नहीं कर रहे, या जब आपने चालें की हैं और फिर मानसिक रूप से “पूर्ववत” कर दी हैं (निष्पादन के बीच में अपना मन बदला और एक अलग पथ आजमाया)। एल्गोरिदम के प्रति प्रतिबद्ध रहें।
सावधान रहें: एक बार जब आपने पुनरावर्ती एल्गोरिदम का उपयोग करके एक चाल तय की है, तो उसके प्रति प्रतिबद्ध रहें। इसे निष्पादन के बीच में प्रश्न करने से बर्बाद चालें होती हैं। एल्गोरिदम इष्टतमता की गारंटी देता है - इस पर भरोसा करें और संकोच किए बिना निष्पादित करें।
अभ्यास योजना
सप्ताह 1 - एल्गोरिदम आंतरिककरण (3 डिस्क)। रोज़ 3-डिस्क खेल खेलें। प्रत्येक खेल के बाद, तीन चरणों को जोर से वर्णन करें। दोहराएं जब तक पैटर्न इतना परिचित न हो जाए कि आप पहली चाल करने से पहले पूरा समाधान बता सकें।
सप्ताह 2 - स्केलिंग (4 से 5 डिस्क)। 4-डिस्क खेल की ओर बढ़ें। पुनरावृत्ति अब दो स्तर गहरी जाती है। प्रत्येक खेल के बाद, संरचना ट्रेस करें: “मैंने 3 तक पुनरावृत्त किया, बड़ी डिस्क ले जाई, फिर से पुनरावृत्त किया।” 4 डिस्क पर तीन से चार खेल खेलें, फिर 5 पर जाएं।
सप्ताह 3 - दबाव (6 डिस्क)। 6 डिस्क पर, चाल बजट बाधा बन जाता है। एल्गोरिदम को अपने एकमात्र मार्गदर्शक के रूप में खेलें। न्यूनतम (63 चाल) के पांच चालों के भीतर दो 6-डिस्क खेल पूरा करने का लक्ष्य रखें।
सप्ताह 4 - महारत (7 डिस्क)। 7-डिस्क पहेलियों का प्रयास करें। किसी भी डिस्क को छूने से पहले शीर्ष-स्तरीय चरण योजना लागू करें। 7 डिस्क पर 127 के करीब चाल गिनती के साथ तीन लगातार जीत वास्तविक महारत का संकेत देती है।
सुझाव: डिस्क स्तर प्रति अपनी चाल गिनती का लॉग रखें। सत्रों में न्यूनतम की ओर अपनी गिनती गिरते देखना सबसे स्पष्ट बाहरी संकेत है कि पुनरावर्ती पैटर्न आंतरिक हो रहा है। 7 डिस्क के लिए 130 से ऊपर की चाल गिनती का मतलब है भटकने वाली चालें अभी भी दिख रही हैं; स्थिरता के साथ 135 से कम का मतलब संरचना ठोस है।
Tower of Hanoi उन कुछ खेलों में से एक है जहां महारत पूर्ण और मापनीय दोनों है। या तो आप पुनरावर्ती एल्गोरिदम जानते और निष्पादित करते हैं, या नहीं। एक बार जब आप करते हैं, तो हर कठिनाई स्तर उसी तर्क के आगे झुकता है। धीमे हो जाएं, अपने चरणों को नाम दें, एल्गोरिदम पर भरोसा करें, और समाधान हमेशा वहीं होता है।
Tower of Hanoi
क्लासिक · डिस्क के पूरे टावर को दूसरे खंभे पर ले जाएं, एक बार में एक, बड़ी कभी छोटी पर नहीं
अभी खेलें - यह मुफ़्त हैकिसी खाते की ज़रूरत नहीं। किसी भी डिवाइस पर काम करता है।