हनोई टॉवर एल्गोरिदम: Python, C++ Code

हनोई का टॉवर क्या है?

टावर ऑफ हनोई एक गणितीय पहेली है जिसमें तीन छड़ें और घटते आकार की डिस्क का एक ढेर होता है, जो एक के ऊपर एक रखी होती हैं। इसे टावर ऑफ ब्रह्मा या लुकास टावर के नाम से भी जाना जाता है, क्योंकि फ्रांसीसी गणितज्ञ एडुआर्ड लुकास ने इसे 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 पर रखी होती हैं।

इस चरण में: स्रोत = खूंटी A, गंतव्य = खूंटी C, सहायक = खूंटी B.

अब, हमें शीर्ष n-1 डिस्क को स्रोत से हेल्पर तक ले जाने की आवश्यकता है।

नोट: हालांकि हम एक समय में केवल एक डिस्क को ही स्थानांतरित कर सकते हैं, लेकिन यह चरण हमारी 3-डिस्क की समस्या को 2-डिस्क की समस्या में बदल देता है, जिसे एक रिकर्सिव कॉल द्वारा हल किया जाता है।

चरण 2) जब हम पेग A से पेग B को गंतव्य मानकर रिकर्सिव कॉल करते हैं, तो हम पेग C को हेल्पर के रूप में उपयोग करते हैं।

ध्यान दें कि हम उसी टावर ऑफ़ हनोई समस्या के पहले चरण पर वापस आ गए हैं, लेकिन अब दो डिस्क के साथ। हम स्रोत से सहायक तक n-1 (अर्थात् एक) डिस्क ले जाते हैं, जो सबसे छोटी डिस्क को खूंटी A से खूंटी C पर ले जाता है।

इस चरण में: स्रोत = खूंटी A, गंतव्य = खूंटी B, सहायक = खूंटी C.

चरण 3) एल्गोरिदम के अनुसार, nवीं (दूसरी) डिस्क को अब गंतव्य, खूंटी B पर स्थानांतरित कर दिया गया है।

इस चरण में: स्रोत = खूंटी A, गंतव्य = खूंटी B, सहायक = खूंटी C.

चरण 4) अब, हम एल्गोरिथम के तीसरे चरण का अनुसरण करते हुए, n-1 डिस्क (डिस्क एक) को सहायक खूंटी C से गंतव्य खूंटी B पर ले जाते हैं।

इस चरण में: स्रोत = खूंटी A, गंतव्य = खूंटी B, सहायक = खूंटी C.

चरण 5) पुनरावर्ती कॉल पूरी होने के बाद, हम एल्गोरिदम के पहले चरण में अपनी पिछली स्थिति में वापस आ जाते हैं।

चरण 6) दूसरे चरण में, हम डिस्क 3 को स्रोत पेग A से गंतव्य पेग C पर ले जाते हैं।

इस चरण में: स्रोत = खूंटी A, गंतव्य = खूंटी C, सहायक = खूंटी B.

चरण 7) अगला कार्य शेष डिस्क को सहायक (पेग B) से गंतव्य (पेग C) तक ले जाना है। इस बार हम मूल स्रोत (पेग A) को सहायक के रूप में उपयोग करेंगे।

चरण 8) चूंकि हम एक साथ दो डिस्क को स्थानांतरित नहीं कर सकते, इसलिए हम डिस्क 1 के लिए एक रिकर्सिव कॉल करते हैं। हमारे अनुसार कलन विधिइस चरण में गंतव्य बिंदु पेग A है।

इस चरण में: स्रोत = खूंटी बी, गंतव्य = खूंटी ए, सहायक = खूंटी सी।

चरण 9) हमारी पुनरावर्ती प्रक्रिया पूरी हो गई है। अब हम डिस्क 2 को उसके स्रोत से उसके गंतव्य तक ले जाते हैं।

इस चरण में: स्रोत = खूंटी बी, गंतव्य = खूंटी सी, सहायक = खूंटी ए।

चरण 10) हम शेष n-1 डिस्क (डिस्क 1) को हेल्पर से डेस्टिनेशन में स्थानांतरित करके प्रक्रिया समाप्त करते हैं।

इस चरण में: स्रोत = खूंटी A, गंतव्य = खूंटी C, सहायक = खूंटी B.

उपनाम Code हनोई टावर के लिए

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 के लिए रिकर्सिव फ़ंक्शन को दो बार कॉल करती है।
• डिस्क 2, डिस्क 1 के लिए रिकर्सिव फ़ंक्शन को दो बार कॉल करती है।
• डिस्क 1 स्थिर समय में गति करती है, जिससे तीन डिस्क के लिए समय ज्ञात किया जा सकता है।

पुनरावृत्ति के रूप में व्यक्त:

= 2 × (दो डिस्क को हल करने में लगा समय) + डिस्क 3 को स्थानांतरित करने में लगा स्थिर समय

= 2 × (2 × एक डिस्क को हल करने में लगा समय + डिस्क 2 को स्थानांतरित करने में लगा स्थिर समय) + डिस्क 3 को स्थानांतरित करने में लगा स्थिर समय

= (2 × 2) × डिस्क 1 को स्थानांतरित करने में लगने वाला स्थिर समय + 2 × डिस्क 2 को स्थानांतरित करने में लगने वाला स्थिर समय + डिस्क 3 को स्थानांतरित करने में लगने वाला स्थिर समय

n डिस्क के लिए, यह इस प्रकार हो जाता है:

2^N-1 डिस्क 1 + 2 को स्थानांतरित करने में लगने वाला स्थिर समय ×^N-2 × डिस्क 2 को स्थानांतरित करने में लगने वाला स्थिर समय + ….

इस ज्यामितीय प्रगति का योग O(2) हैⁿ – 1), जो सरल होकर यह बन जाता है ओ(२ⁿ)एक घातीय समय जटिलता।

2) स्थानिक जटिलता:

टावर ऑफ हनोई की स्पेस कॉम्प्लेक्सिटी O(n) है। यह रिकर्सन कॉल स्टैक का उपयोग करता है, और स्टैक की अधिकतम गहराई डिस्क की संख्या n के बराबर होती है। इसीलिए इसकी स्पेस कॉम्प्लेक्सिटी O(n) है।

अक्सर पूछे जाने वाले प्रश्न