हनोई टॉवर एल्गोरिदम: Python, C++ कोड
हनोई का टॉवर क्या है?
हनोई का टॉवर एक गणितीय पहेली है जिसमें तीन छड़ें और एक के ऊपर एक रखी गई कई डिस्क शामिल हैं। इसे ब्रह्मा का टॉवर या लुकास टॉवर के नाम से भी जाना जाता है, क्योंकि फ्रांसीसी गणितज्ञ एडौर्ड लुकास ने 1883 में इसे पेश किया था। यह पहेली तीन छड़ों के बीच सोने की डिस्क को घुमाने की किंवदंतियों पर आधारित है।
इस पहेली में तीन छड़ें और ढेर की गई डिस्क की एक चर संख्या है। उन छड़ों को चक्रीय टावरों के रूप में डिज़ाइन किया गया है। इसलिए, व्यास में बड़ी डिस्क नीचे की तरफ़ और छोटी डिस्क ऊपर की तरफ़ रखी गई हैं।
शुरुआत में हमें तीन खूंटे या छड़ें दी जाती हैं। और उनमें से एक (A, उदाहरण में दिखाया गया है) पर सभी डिस्क रखी हुई हैं। हमारा लक्ष्य कुछ खास नियमों का पालन करके डिस्क के पूरे ढेर को एक छड़ (A) से दूसरी छड़ (C) पर ले जाना है।
पहेली की प्रारंभिक संरचना इस प्रकार है-
और यह अंतिम लक्ष्य है-
हनोई टॉवर के नियम
हनोई टॉवर के लिए कुछ आवश्यक नियम यहां दिए गए हैं:
- इस पहेली की प्रारंभिक अवस्था में, सभी डिस्क रॉड एक में रखी जाएंगी।
- अंतिम स्थिति यह है कि रॉड एक से सभी डिस्क रॉड दो या रॉड तीन पर रख दी जाएंगी।
- हम किसी भी समय ऑन-डिस्क को एक रॉड से दूसरे रॉड पर ले जा सकते हैं।
- हम रॉड से केवल सबसे ऊपरी डिस्क को ही हटा सकते हैं।
- एक डिस्क को किसी अन्य छोटी डिस्क के ऊपर नहीं रखा जा सकता।
मूल किंवदंती 64 डिस्क को हिलाने के बारे में थी। पुजारी नियमों के अनुसार एक बार में एक डिस्क को हिला सकते थे। किंवदंती के अनुसार, एक भविष्यवाणी थी कि अगर वे यह कार्य पूरा कर लेते हैं तो दुनिया खत्म हो जाएगी। समय जटिलता अनुभाग में, हम दिखाएंगे कि n डिस्क की एक टॉवर ऑफ़ हनोई सेटिंग की लागत 2^n - 1 चाल होगी।
इसलिए, यदि पुजारियों को डिस्क को स्थानांतरित करने के लिए 1 सेकंड की आवश्यकता होती है, तो पहेली को हल करने के लिए उन्हें कुल 2 ^ 64 - 1 सेकंड या 584,942,417,356 वर्ष, 26 दिन, 7 घंटे और 15 सेकंड की आवश्यकता होगी।
हनोई टॉवर के लिए एल्गोरिदम
हनोई के टॉवर को हल करने का एक सामान्य तरीका एक पुनरावर्ती एल्गोरिथ्म है। सबसे पहले, हमें स्रोत और गंतव्य के रूप में दो छड़ या खूंटियों पर निर्णय लेना होगा, और अतिरिक्त खूंटी एक सहायक या सहायक होगी।
हनोई टॉवर पहेली को सुलझाने के चरण यहां दिए गए हैं:
- शीर्ष n-1 डिस्क को स्रोत खूंटी से सहायक खूंटी तक ले जाएं।
- इसके बाद, nवीं डिस्क को स्रोत खूंटी से गंतव्य खूंटी पर ले जाएं।
- अंत में, शेष n-1 डिस्क को हेल्पर पेग से गंतव्य पेग तक ले जाएं।
नोटयदि हमारे पास एक ही डिस्क है, तो हम उसे सीधे स्रोत से गंतव्य तक ले जा सकते हैं।
हनोई टॉवर पहेली को कैसे हल करें
आइए तीन डिस्क के लिए एल्गोरिथ्म को स्पष्ट करें और खूंटी A को स्रोत, खूंटी B को सहायक, तथा खूंटी C को गंतव्य मानें
चरण 1) प्रारंभ में, सभी डिस्कों को खूंटी A पर रखा जाएगा।
इस स्तर पर:
स्रोत = पेग ए
गंतव्य = पेग सी
सहायक = खूंटी बी
अब, हमें शीर्ष n-1 डिस्क को स्रोत से हेल्पर तक ले जाने की आवश्यकता है।
नोट: यद्यपि हम एक समय में केवल एक डिस्क ही स्थानांतरित कर सकते हैं, लेकिन इससे हमारी समस्या 3-डिस्क समस्या से 2-डिस्क समस्या में बदल जाती है, जो एक पुनरावर्ती कॉल है।
चरण 2) चूंकि हम खूंटी A से पुनरावर्ती कॉल करते हैं और गंतव्य खूंटी B है, इसलिए हम सहायक के रूप में खूंटी C का उपयोग करेंगे।
ध्यान दें कि हम दो डिस्कों के लिए हनोई टावर समस्या के समान चरण एक पर पुनः आ गए हैं।
अब हमें n-1 या एक डिस्क को स्रोत से सहायक तक ले जाने की आवश्यकता है, सबसे छोटी डिस्क को खूंटी A से खूंटी C तक ले जाना है।
इस स्तर पर:
स्रोत = खूंटी ए
गंतव्य = खूंटी बी
हेल्पर = खूंटी सी
चरण 3) फिर, हमारे एल्गोरिथ्म के अनुसार, nth या 2nd डिस्क को गंतव्य या खूंटी B में स्थानांतरित किया जाना चाहिए।
इस स्तर पर:
स्रोत = खूंटी ए
गंतव्य = खूंटी बी
हेल्पर = खूंटी सी
चरण 4) अब, हम अपने एल्गोरिथ्म के तीसरे चरण के अनुसार n-1 डिस्क या डिस्क एक को हेल्पर या खूंटी C से गंतव्य या खूंटी B तक ले जाएंगे।
इस स्तर पर:
स्रोत = खूंटी ए
गंतव्य = खूंटी बी
हेल्पर = खूंटी सी
चरण 5) पुनरावर्ती कॉल पूरा करने के बाद, एल्गोरिथ्म के पहले चरण में हम अपनी पिछली सेटिंग पर लौट आएंगे।
चरण 6) अब, दूसरे चरण में, हम अपने स्रोत को अपने गंतव्य तक ले जाएंगे, जो कि डिस्क 3 को खूंटी A से खूंटी C तक ले जाना है।
इस स्तर पर:
स्रोत = खूंटी ए
गंतव्य = खूंटी सी
सहायक = खूंटी बी
चरण 7) अब हम देख सकते हैं कि
d का मतलब है कि बचे हुए डिस्क को हेल्पर (पेग बी) से गंतव्य (पेग सी) तक ले जाना। इस मामले में हम प्रारंभिक स्रोत या पेग ए को हेल्पर के रूप में इस्तेमाल करेंगे।
चरण 8) चूंकि हम दो डिस्क को एक साथ नहीं ले जा सकते, इसलिए हम डिस्क 1 के लिए पुनरावर्ती कॉल करेंगे। अंतिम चरण और हमारे अनुसार कलन विधिइस चरण में गंतव्य खूंटी ए है।
इस स्तर पर:
स्रोत = खूंटी बी
गंतव्य = खूंटी A
हेल्पर = खूंटी सी
चरण 9) अब हमारा रिकर्सिव कॉल पूरा हो गया है। फिर हम डिस्क 2 को उसके स्रोत से उसके गंतव्य तक ले जाते हैं।
इस स्तर पर:
स्रोत = खूंटी बी
गंतव्य = खूंटी सी
सहायक = खूंटी ए
चरण 10) फिर हम अपने शेष n-1 या डिस्क 1 को हेल्पर से गंतव्य तक ले जाते हैं।
इस स्तर पर:
स्रोत = खूंटी ए
गंतव्य = खूंटी सी
सहायक = खूंटी बी
हनोई टॉवर के लिए छद्म कोड
START Procedure Tower_Of_Hanoi(disk, source, dest, helper) IF disk == 1, THEN move disk from source to dest ELSE Tower_Of_Hanoi (disk - 1, source, helper, dest) move disk from source to dest Tower_Of_Hanoi (disk - 1, helper, dest, source) END IF END Procedure
प्रोग्राम कोड C++
#include <bits/stdc++.h> using namespace std; void tower_of_hanoi(int num, string source, string dest, string helper) { if (num == 1) { cout << " Move disk 1 from tower " << source << " to tower " << dest << endl; return; } tower_of_hanoi(num - 1, source, helper, dest); cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl; tower_of_hanoi(num - 1, helper, dest, source); } int main() { int num; cin >> num; printf("The sequence of moves :\n"); tower_of_hanoi(num, "I", "III", "II"); return 0; }
उत्पादन
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
प्रोग्राम कोड Python
def tower_of_hanoi(n, source, destination, helper): if n==1: print ("Move disk 1 from peg", source," to peg", destination) return tower_of_hanoi(n-1, source, helper, destination) print ("Move disk",n," from peg", source," to peg", destination) tower_of_hanoi(n-1, helper, destination, source) # n = number of disks n = 3 tower_of_hanoi(n,' A','B','C')
आउटपुट:
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
हनोई टॉवर की जटिलता
हनोई टॉवर की समय और स्थान जटिलता इस प्रकार है:
1) समय जटिलता:
अगर हम अपने एल्गोरिथ्म पर नज़र डालें, तो हम देख सकते हैं कि हम (n-1) डिस्क के लिए दो बार रिकर्सिव कॉल शुरू कर रहे हैं। (n-1) डिस्क के लिए उन रिकर्सिव कॉल को अन्य ((n-1)-1) में तोड़ा जा सकता है और इसी तरह तब तक चलता रहेगा जब तक हमें स्थानांतरित करने के लिए केवल एक डिस्क न मिल जाए।
तीन डिस्क के लिए-
- डिस्क 3, डिस्क दो के लिए पुनरावर्ती फ़ंक्शन को दो बार कॉल करता है।
- डिस्क 2, डिस्क XNUMX के लिए पुनरावर्ती फ़ंक्शन को दो बार कॉल करता है।
- डिस्क 1 निरंतर समय के भीतर चल सकती है, और तीन डिस्क के लिए समय हल कर सकती है।
= 2*(दो डिस्क के लिए हल करने का समय) + डिस्क 3 को स्थानांतरित करने के लिए स्थिर समय
= 2*(2*एक डिस्क को हल करने में लगा समय + डिस्क 2 को स्थानांतरित करने में लगा स्थिर समय) + डिस्क 3 को स्थानांतरित करने में लगा स्थिर समय
= (2*2) (डिस्क 1 को स्थानांतरित करने के लिए स्थिर समय) + 2*डिस्क 2 को स्थानांतरित करने के लिए स्थिर समय + डिस्क 3 को स्थानांतरित करने के लिए स्थिर समय
N डिस्क के लिए इसे इस प्रकार लिखा जा सकता है –
(2N-1 * डिस्क 1 + 2 को स्थानांतरित करने के लिए स्थिर समयN-2 * डिस्क 2 को स्थानांतरित करने के लिए स्थिर समय + ….
इस ज्यामितीय प्रगति का परिणाम O(2 .) होगाN-1) या ओ(२n), जो घातांकीय है।
2) स्थान जटिलता
हनोई के टॉवर की स्पेस जटिलता 0(n) है। ऐसा इसलिए है क्योंकि हमें प्लेटों के अनुक्रम को संग्रहीत करने की आवश्यकता है। जब हम रिकर्सन का उपयोग कर रहे हैं, तो यह स्टैक का उपयोग कर रहा है। और स्टैक का अधिकतम आकार "n" हो सकता है। इसलिए स्पेस जटिलता O(n) हो जाती है।