टावर ऑफ हनोई समस्या

परिचय

टावर ऑफ हनोई एक पहेली समस्या है। जहां हमारे पास तीन स्टैंड और n डिस्क हैं। प्रारंभ में, डिस्क पहले स्टैंड में रखी जाती हैं। हमें डिस्क को तीसरे या गंतव्य स्टैंड में रखना है, दूसरा या सहायक स्टैंड सहायक स्टैंड के रूप में उपयोग किया जा सकता है।

लेकिन पालन करने के लिए कुछ नियम हैं:

• हम प्रत्येक चाल के लिए केवल एक डिस्क स्थानांतरित कर सकते हैं।
• केवल सबसे ऊपर की डिस्क को एक स्टैंड से उठाया जा सकता है।
• कोई बड़ी डिस्क छोटी डिस्क के ऊपर नहीं रखी जाएगी।

इस समस्या को पुनरावृत्ति द्वारा आसानी से हल किया जा सकता है। सबसे पहले, पुनरावृत्ति का उपयोग करके शीर्ष (n-1) डिस्क को स्रोत से सहायक स्टैंड पर रखा जाता है, फिर अंतिम डिस्क को स्रोत से गंतव्य पर रखें, फिर फिर से (n-1) डिस्क को सहायक स्टैंड से गंतव्य स्टैंड पर पुनरावृत्ति द्वारा रखें।

इनपुट और आउटपुट

इनपुट: डिस्क की संख्या: 3
आउटपुट:
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C

एल्गोरिदम

toh(n, s, a, d)
इनपुट: डिस्क की संख्या, स्रोत, सहायक, गंतव्य
आउटपुट: उचित नियमों को बनाए रखते हुए स्रोत से गंतव्य तक डिस्क ले जाने के चरण

Begin
    यदि n = 1, तो
        s से d में डिस्क ले जाने का प्रदर्शन करें
    toh(n-1, s, d, a)
    s से d में डिस्क ले जाने का प्रदर्शन करें
    toh(n-1, a, s, d)
End

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

void TOH(int n, char s, char a, char d) {
    static int count = 0; // चालों की संख्या संग्रहीत करें
    if (n == 1) {
        count++;
        cout << count << ". Move disk " << n << " from " << s << " to " << d << endl;
        return; // आधार मामला, जब केवल एक डिस्क हो
    }
    TOH(n-1, s, d, a); // पुनरावर्ती कॉल फंक्शन
    count++;
    cout << count << ". Move disk " << n << " from " << s << " to " << d << endl;
    TOH(n-1, a, s, d);
}

int main() {
    int n;
    cout << "Enter the number of disks: "; cin >> n;
    TOH(n, 'A', 'B', 'C');
}

आउटपुट

Enter the number of disks: 3
1. Move disk 1 from A to C
2. Move disk 2 from A to B
3. Move disk 1 from C to B
4. Move disk 3 from A to C
5. Move disk 1 from B to A
6. Move disk 2 from B to C
7. Move disk 1 from A to C