हनोई के टावर: तीन खूँटों से न डिस्क खिसकाओ (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.६: तीन खूँटे और न डिस्क वाला क्लासिक हनोई टावर। ऊपर के टावर का रिकर्सिव मूव, हर खूँटे पर जावा स्टैक।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तीन डंडे हैं और डिस्क का एक ढेर। डिस्क पहली डंडे पर शुरू होती हैं, सबसे बड़ी नीचे, सबसे छोटी ऊपर। पूरा ढेर आखिरी डंडे पर ले जाना है। एक बार में एक डिस्क। बड़ी डिस्क छोटी पर कभी नहीं रख सकते। बीच वाली डंडे ही पार्किंग है। यही पहेली हनोई के टावर है, और साफ इंटरव्यू हल है रिकर्शन प्लस हर खूँटे पर एक स्टैक।

यह पोस्ट जावा में बिल्कुल शुरुआती लोगों के लिए मूल शिक्षण है। क्लासिक रिकर्सिव हनोई प्रश्नों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८, रिकर्शन और डायनामिक प्रोग्रामिंग। समस्या ८.६।

१. रोज़मर्रा की उपमा

पार्क के तीन खम्भे और फँसे हुए छल्लों का ढेर सोचो:

स्रोत खूँटा: जहाँ पूरा टावर शुरू होता है।
गंतव्य खूँटा: जहाँ पूरा टावर खत्म होना है।
बफ़र खूँटा: अस्थायी पार्किंग ताकि "बड़ा नीचे, छोटा ऊपर" का नियम न टूटे।

पाँच छल्लों का टावर खिसकाने के लिए पाँच अलग नियम नहीं बनाते। सबसे बड़े छल्ले के ऊपर के चार हटाओ (बफ़र पर पार्क, गंतव्य को उनका बफ़र बनाकर), बड़ा छल्ला गंतव्य पर सरकाओ, फिर चार का टावर उसके ऊपर ले आओ। वही ख्याल चार, तीन, दो और एक पर चलता है।

रिकर्शन वही आदत है: "वही विचार, छोटा ढेर", कोड में ढाला हुआ।

२. समस्या सादे शब्दों में

सेटअप:

तीन खूँटे: अक्सर ए (स्रोत), बी (बफ़र), सी (गंतव्य)।
n अलग-अलग आकार की डिस्क। डिस्क 1 सबसे छोटी, डिस्क n सबसे बड़ी (या उलटा लेबल; एक चुनो और पकड़ो)।
शुरुआत: सारी डिस्क स्रोत पर, सबसे बड़ी तल पर से सबसे छोटी ऊपर तक।
लक्ष्य: सारी डिस्क गंतव्य पर, वैध क्रम में।

नियम:

१. एक बार में सिर्फ एक डिस्क हिलाओ। २. चाल एक खूँटे की ऊपरी डिस्क लेकर दूसरे पर रखती है। ३. बड़ी डिस्क छोटी पर कभी मत रखो।

आउटपुट: वैध चालों का क्रम जो पहेली सुलझाए, या स्टैक-आधारित खूँटों पर वे चालें चलाने वाला प्रोग्राम।

उदाहरण (न = १, २, ३):

न	न्यूनतम चालें	ख्याल
१	१	स्रोत → गंतव्य
२	३	छोटी बफ़र पर, बड़ी गंतव्य पर, छोटी गंतव्य पर
३	७	२ को बफ़र पर, बड़ी गंतव्य पर, २ को गंतव्य पर
न	२^न - १	पुनरावृत्ति टी(न) = २ टी(न-१) + १

कोड से पहले स्पष्ट करो:

हर खूँटा डिस्क आकारों का Stack? (हाँ। ऊपर वही डिस्क हिल सकती है।)
लेबल: बड़ा पूर्णांक = बड़ी डिस्क, या उलटा? यहाँ: बड़ा इंट = बड़ी डिस्क।
चालें छापनी हैं या स्टैक बदलने हैं? दोनों बेहतर: moveDisks जो बदले, और वैकल्पिक लॉग।
अवैध चाल? अगर बड़ी छोटी पर बैठने वाली हो तो थ्रो या असर्ट।

३. पहले सोचो (रिकर्सिव मूव)

आधार केस

१ डिस्क स्रोत से गंतव्य: स्रोत से पॉप, गंतव्य पर पुश। हो गया।

रिकर्सिव केस

बफ़र इस्तेमाल कर न डिस्क स्रोत से गंतव्य ले जाने के लिए:

१. n - 1 डिस्क स्रोत → बफ़र, गंतव्य को अस्थायी खूँटा बनाकर। २. बची (इस उपसमस्या की सबसे बड़ी) डिस्क स्रोत → गंतव्य। ३. n - 1 डिस्क बफ़र → गंतव्य, स्रोत को अस्थायी खूँटा बनाकर।

हर रिकर्सिव कॉल में तीन खूँटों की भूमिकाएँ बदलती हैं। यही पूरा जादू है। "हमेशा बी पर पार्क" हार्डकोड नहीं करते।

आकार का नियम क्यों नहीं टूटता

प्रेरण से: n - 1 का वैध टावर एक इकाई की तरह हिल सकता है। कदम १ के बाद इस उपसमस्या की सबसे बड़ी डिस्क स्रोत पर अकेली (या इस कॉल से बाहर की और बड़ी डिस्क के नीचे) रहती है। कदम २ उसे ऐसे खूँटे पर रखता है जिसकी ऊपरी डिस्क खाली हो या उससे बड़ी हो (छोटी सब बफ़र पर हैं)। कदम ३ छोटा टावर ऊपर फिर बनाता है।

चाल: न = ३, ए → सी, बी से

डिस्क: ए पर 3 (तल), 2, 1 (ऊपर)।

कदम	क्रिया	ए (तल → ऊपर)	बी	सी
शुरू		३, २, १	खाली	खाली
१	२ हिलाओ: ए → बी, सी से	३	२, १	खाली
२	डिस्क ३: ए → सी	खाली	२, १	३
३	२ हिलाओ: बी → सी, ए से	खाली	खाली	३, २, १

"२ हिलाओ: ए → बी, सी से" खोलकर:

१. १ हिलाओ: ए → सी २. २ हिलाओ: ए → बी ३. १ हिलाओ: सी → बी

न = ३ के लिए कुल चालें: ७। पैटर्न हर न पर चलता है।

क्या न करो

सिर्फ न = ३ के लिए नेस्टेड लूप। इंटरव्यू में सामान्य रिकर्सिव ढाँचा चाहिए।
अगर समस्या खूँटों को स्टैक माँगे तो बिना स्टैक अनुशासन के ऐरे।
तीन-कदम योजना दिखाए बिना पूरे उप-टावर का "धोखा" नॉन-रिकर्सिव मूव।

४. जावा हल

हर खूँटे को Stack<Integer> लपेटे छोटी क्लास बनाओ। डिस्क मान आकार के साथ बढ़ते हैं: पुश से पहले ऊपर छोटी होनी चाहिए, या खूँटा खाली।

import java.util.Stack;

/**
 * One peg in Towers of Hanoi. Top of stack is the movable disk.
 * Larger int means larger disk.
 */
class Tower {
    private final Stack<Integer> disks = new Stack<Integer>();
    private final int index; // 0, 1, or 2 for logging

    Tower(int index) {
        this.index = index;
    }

    int index() {
        return index;
    }

    void add(int disk) {
        if (!disks.isEmpty() && disks.peek() <= disk) {
            throw new IllegalStateException(
                "Cannot place disk " + disk + " on " + disks.peek());
        }
        disks.push(disk);
    }

    void moveTopTo(Tower destination) {
        int top = disks.pop();
        destination.add(top);
        System.out.println(
            "Move disk " + top + " from " + index + " to " + destination.index());
    }

    /**
     * Move the top n disks from this tower to destination,
     * using buffer as temporary storage.
     */
    void moveDisks(int n, Tower destination, Tower buffer) {
        if (n <= 0) {
            return;
        }
        if (n == 1) {
            moveTopTo(destination);
            return;
        }
        // n-1 off this peg onto buffer (destination is their buffer)
        moveDisks(n - 1, buffer, destination);
        // largest of this subproblem to destination
        moveTopTo(destination);
        // n-1 from buffer onto destination (this peg is their buffer)
        buffer.moveDisks(n - 1, destination, this);
    }
}

तीन खूँटे बनाकर n सुलझाने वाला ड्राइवर:

void solveHanoi(int n) {
    Tower[] towers = new Tower[3];
    for (int i = 0; i < 3; i++) {
        towers[i] = new Tower(i);
    }

    // Source = towers[0]. Load largest first so it sits at the bottom.
    for (int disk = n; disk >= 1; disk--) {
        towers[0].add(disk);
    }

    towers[0].moveDisks(n, towers[2], towers[1]);
    // towers[2] now holds  n, n-1, ..., 1  (bottom → top)
}

न = २ की न्यूनतम जाँच (तीन छपी चालें):

// solveHanoi(2) prints something like:
// Move disk 1 from 0 to 1
// Move disk 2 from 0 to 2
// Move disk 1 from 1 to 2

अगर Tower पर मेथड की जगह फ्री फ़ंक्शन पसंद हो, वही तीन कदम रखो और स्रोत, गंतव्य, बफ़र आर्ग्युमेंट दो। रिकर्शन का आकार नहीं बदलता।

५. जटिलता तालिका

तरीका	समय	अतिरिक्त जगह	नोट
क्लासिक रिकर्शन	ओ(२^न) चालें	ओ(न) कॉल स्टैक	ठीक २^न - १ चालें; हर चाल स्टैक पर ओ(१)
स्पष्ट स्टैक से इटरेटिव	ओ(२^न) चालें	ओ(न)	वही सीमा; रिकर्शन का अनुकरण
सिर्फ बंद सूत्र	गिनने में ओ(१)	ओ(१)	गिनती २^न - १; चालें छापोगे तो फिर ओ(२^न)

क्लासिक तीन-खूँटा नियमों में २^न - १ वैध चालों से कम नहीं हो सकता। घातांकीय लागत समस्या है, तुम्हारे कोड का बग नहीं। रिकर्सिव हल की अतिरिक्त जगह कॉल गहराई ओ(न), प्लस खूँटों पर डिस्क भंडारण ओ(न)।

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

न = ० → कोई चाल नहीं। n <= 0 से बचाव।
न = १ → एक moveTopTo। आधार केस अकेले चले।
न = २, न = ३ → हाथ से चलाओ; गिनती ३ और ७ हो।
बफ़र भूमिका गलत → रिकर्सिव कॉल में गंतव्य और बफ़र बदलने से टावर बिगड़ता है।
सबसे छोटी पहले लोड → सबसे बड़ी ऊपर आ जाती है; add थ्रो करता है या पहेली अवैध शुरू होती है।
आकार तुलना उलटी → अगर "बड़ा इंट = बड़ी डिस्क" पलटो तो सुरक्षा जाँच भी पलटो।

आम गलतियाँ:

१. सिर्फ बीच की चाल कोड करना। दो n - 1 रिकर्सिव कॉल भूलने से डिस्क अटक जाती हैं। २. रिकर्सिव मेथड में खूँटा इंडेक्स हार्डकोड करना, भूमिकाएँ पास न करना। भूमिका घूमते ही टूटता है। ३. अवैध स्टैक मान लेना। add में जाँच न हो तो बग चुप रहते हैं जब तक अंतिम लेआउट गलत न दिखे। ४. न पर एक-गलत। खराब पिछली कॉल के बाद स्रोत पर सिर्फ n - 1 रहें तो भी n हिलाना। ५. सोचना डीपी मेमो मदद करेगा। हर उपसमस्या को सच में डिस्क हिलानी हैं; पथ-गिनती डीपी जैसा ओवरलैप "काम बचाओ" यहाँ नहीं। मेमो टेबल से ज़्यादा रिकर्शन संरचना मायने रखती है।

सुरक्षित प्रवेश:

void solveHanoiSafe(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("n must be >= 0");
    }
    solveHanoi(n);
}

७. दोस्त को समझाने वाला सार

हनोई के टावर पूछते हैं: न डिस्क खूँटा ए से खूँटा सी पर ले जाओ, खूँटा बी इस्तेमाल कर, कभी बड़ी को छोटी पर न रखो।

१. हर खूँटे को स्टैक मानो। ऊपर वही डिस्क हिल सकती है। २. आधार: एक डिस्क स्रोत → गंतव्य। ३. सामान्य: न-१ स्रोत → बफ़र (गंतव्य अस्थायी), एक स्रोत → गंतव्य, न-१ बफ़र → गंतव्य (स्रोत अस्थायी)। ४. कुल चालें: २^न - १। समय ओ(२^न), रिकर्शन गहराई ओ(न)। ५. हर पुश पर आकार नियम लगाओ ताकि अवैध अवस्था जल्दी फेल हो।

तीन-कदम योजना कह सको, सबसे बड़ी पहले लोड कर सको, और बफ़र भूमिका न मिलाओ, तो समस्या ८.६ तुम्हारी है।