javascript - क्रॉकफोर्ड के हनोई फ़ंक्शन("द गुड पार्ट्स" से)




recursion towers-of-hanoi (2)

इस सवाल का पहले से ही उत्तर दिया गया है:

फिलहाल मैं डगलस क्रॉकफोर्ड की किताब पढ़ रहा हूं, और हनोई समारोह के टावर मेरे सिर पर थोड़ा सा है। कंसोल में सामान लॉगिंग के साथ भी मैं वास्तव में समझ नहीं पा रहा था कि क्या चल रहा है। मेरे परिवर्धन के साथ यहां कार्य किया गया है:

var hanoi = function (disc, src, aux, dst) {
  console.log(disc);
  console.log(src, dst);    
  if (disc > 0) {
    hanoi(disc - 1, src, dst, aux);
    console.log('Move disc ' + disc + ' from ' + src + ' to ' + dst);
    hanoi(disc - 1, aux, src, dst);
  }
}

hanoi(3, 'Src', 'Aux', 'Dst');

यह निम्न में परिणाम:

3
सीनियर डीएसटी
2
सीनियर ऑक्स
1
सीनियर डीएसटी
0
सीनियर ऑक्स
डिस्क 1 को एसआरसी से डीएसटी तक ले जाएं
0
ऑक्स डीएसटी
डिस्क 2 को Src से Aux में ले जाएं
1
डीएसटी ओक्स
0
डीएसटी एसआरसी
डिस्क 1 को डीएसटी से औक्स में ले जाएं I
0
सीनियर ऑक्स
डिस्क 3 को सीआरसी से डीएसटी तक ले जाएं
2
ऑक्स डीएसटी
1
ऑक्स सीनियर
0
ऑक्स डीएसटी
डिस्क 1 को ऑक्स से सीआरसी तक ले जाएं
0
डीएसटी एसआरसी
डिस्क 2 को ऑक्स से डीएसटी तक ले जाएं
1
सीनियर डीएसटी
0
सीनियर ऑक्स
डिस्क 1 को एसआरसी से डीएसटी तक ले जाएं
0
ऑक्स डीएसटी

और मैं एक प्रारंभिक बिंदु पर खो गया हूँ परिणाम 6 की पंक्ति में, यह Src Aux से Src Dst तक कैसे वापस जा सकता है?

और जब डिस्क 1 की पहुंच हो जाती है तो एक बार फिर यह कैसे हो सकता है जब फ़ंक्शन केवल "डिस्क -1" का प्रयोग कर ही बुलाता है?


भ्रम उत्पन्न होता है क्योंकि उत्पादन का पाठ प्रतिनिधित्व पुनरावर्तन को समझने का सबसे अच्छा तरीका नहीं है। डिस्क की संख्या "ऊपर नहीं जा रही" है, बल्कि hanoi(1) जो hanoi(0) एक बार चलने के लिए जारी है।

मैंने JSBin पर एक संशोधित उदाहरण बनाया है जो रिक्त स्थान के साथ एक (कुछ हद तक) सुंदर तरीके से आउटपुट प्रिंट करता है। केवल "चाल" वास्तव में कुछ भी करते हैं, बाकी की रेखाएं पूरी समस्या को बाद में पूरी तरह से निपटने के लिए छोटी उप-समस्याओं को हल करने के लिए केवल पुनरावर्ती कॉल हैं

आप इस जावा एपलेट पर एक नज़र भी देखना चाह सकते हैं जो एल्गोरिथ्म कैसे काम करता है, यह दिखाता है - यह समझना आसान हो सकता है


हनोई के टावर्स एक उत्कृष्ट उदाहरण हैं कि किस तरह से रिकर्सन दी गई समस्या को आसान बना सकता है। यह विचार इस प्रकार है: आपको एन डिस्क को एक स्रोत स्टैक से एक गंतव्य स्टैक पर ले जाना है, एक समय में एक डिस्क और आप कभी भी छोटी डिस्क पर एक बड़ी डिस्क नहीं डाल सकते हैं आप सहायक स्टैक का उपयोग कर सकते हैं। मान लीजिए एन = 10. आप इसे कैसे हल करने के बारे में पता नहीं है लेकिन आप समस्या को सरल बना सकते हैं (आप आशा करते हैं):

move 9 disks to the auxiliary stack,  
move the remaining (and largest!) disk to the destination stack, and  
move the 9 disks from the auxiliary stack to the destination stack  

फिर, आपको पता नहीं है कि 9 डिस्क स्टैक को कैसे स्थानांतरित करना है, लेकिन इससे कोई समस्या नहीं है:

move 8 disks from the auxiliary stack to the source stack,  
move the remaining disk to the destination stack (there are 2 disks now), and  
move the 8 disks from the source stack to the destination stack  

इसे दोहराएं, जब तक आप को ले जाने के लिए ढेर नहीं है, केवल 1 डिस्क बड़ी है

डिस्क की संख्या के बारे में फिर से जा रहा है: आप फ़ंक्शन को एन-1 डिस्क के लिए कॉल करते हैं, जो फ़ंक्शन में एन को सौंपा जाता है। फ़ंक्शन समाप्त होने तक यह एन ही मौजूद होता है, और पिछले स्तर पर लौटता है। फिर आप फिर से एन के पुराने मूल्य प्राप्त करें







towers-of-hanoi