recursion - हनोई का टॉवर: रिकर्सिव एल्गोरिदम




towers-of-hanoi (16)

हालांकि मुझे किसी भी समस्या को समझने में कोई समस्या नहीं है, लेकिन मैं हनोई समस्या के टॉवर के लिए रिकर्सिव समाधान के आसपास अपने सिर को लपेट नहीं सकता। Wikipedia से कोड यहां दिया गया है:

procedure Hanoi(n: integer; source, dest, by: char);
Begin
    if (n=1) then
        writeln('Move the plate from ', source, ' to ', dest)
    else begin
        Hanoi(n-1, source, by, dest);
        writeln('Move the plate from ', source, ' to ', dest);
        Hanoi(n-1, by, dest, source);
    end;
End;

मैं बेस केस और छोटी टुकड़ों में समस्या को तोड़ने की अवधारणा को समझता हूं जब तक आप एक डिस्क को स्थानांतरित करने में सक्षम नहीं होते। हालांकि, मैं यह नहीं समझ सकता कि गैर-बेस केस में दो रिकर्सिव कॉल कैसे काम करते हैं। शायद कोई मेरी मदद कर सकता है? धन्यवाद।


/ ** * * / पैकेज com.test.recursion;

/ ** * @Author kamals1986 हनोई समस्या के टॉवर के लिए रिकर्सिव एल्गोरिदम * एल्गोरिदम शक्ति द्वारा बढ़ता है (2, एन)। * / पब्लिक क्लास टॉवरऑफहनोई {

private static String SOURCE_PEG = "B";

private static String SPARE_PEG = "C";

private static String TARGET_PEG = "A";

public void listSteps(int n, String source, String target, String spare) {
    if (n == 1) {
        System.out.println("Please move from Peg " + source + "\tTo Peg\t"
                + target);
    } else {
        listSteps(n - 1, source, spare, target);
        listSteps(1, source, target, spare);
        listSteps(n - 1, spare, target, source);
    }
}

public static void main(String[] args) {
    long startTime = System.currentTimeMillis();
    new TowerOfHanoi().listSteps(18, SOURCE_PEG, TARGET_PEG, SPARE_PEG);

    long endTime = System.currentTimeMillis();

    System.out.println("Done in " + (endTime - startTime) / 1000
            + "\t seconds");
}

}


इन सभी स्पष्टीकरणों को पढ़ने के बाद मैंने सोचा कि मैं उस विधि के साथ वजन करूँगा जो मेरे प्रोफेसर हनोई रिकर्सिव समाधान के टावर्स को समझाने के लिए प्रयोग किया जाता था। एन के साथ फिर से एल्गोरिदम है जो छल्ले की संख्या का प्रतिनिधित्व करता है, और ए, बी, सी खूंटी का प्रतिनिधित्व करता है। फ़ंक्शन का पहला पैरामीटर रिंगों की संख्या है, दूसरा पैरामीटर स्रोत पेग का प्रतिनिधित्व करता है, तीसरा गंतव्य पेग है, और चौथाई अतिरिक्त पेग है।

procedure Hanoi(n, A, B, C);
  if n == 1
    move ring n from peg A to peg B
  else
    Hanoi(n-1, A, C, B);
    move ring n-1 from A to C
    Hanoi(n-1, C, B, A);
end;

मुझे स्नातक स्कूल में पढ़ाया जाता था ताकि कभी भी छोटे से सोचने में शर्मिंदा न हो। तो, आइए एन = 5 के लिए इस एल्गोरिदम को देखें। 5. खुद को पहले पूछने का सवाल यह है कि अगर मैं 5 वें अंगूठी को ए से बी में ले जाना चाहता हूं, तो अन्य 4 अंगूठियां कहां हैं? अगर 5 वीं अंगूठी पेग ए पर कब्जा कर लेती है और हम इसे बीजी में ले जाना चाहते हैं, तो अन्य 4 अंगूठियां केवल पेग सी पर हो सकती हैं। समारोह के ऊपर एल्गोरिदम में हनोई (एन -1, ए, सी, बी) कोशिश कर रहा है उन सभी 4 अन्य छल्ले को पीजी सी पर ले जाएं, इसलिए अंगूठी 5 ए से बी तक जाने में सक्षम हो जाएगी। इस एल्गोरिदम के बाद हम n = 4 देखेंगे। अगर अंगूठी 4 को ए से सी में ले जाया जाएगा, जहां रिंग 3 हैं और छोटे? वे केवल पेग बी पर हो सकते हैं। अगला, एन = 3 के लिए, यदि अंगूठी 3 ए से बी में ले जाया जाएगा, तो रिंग 2 और 1 कहां हैं? निश्चित रूप से पेग सी पर। यदि आप इस पैटर्न का पालन करना जारी रखते हैं तो आप कल्पना कर सकते हैं कि रिकर्सिव एल्गोरिदम क्या कर रहा है। यह दृष्टिकोण नौसिखिया के दृष्टिकोण से अलग है जिसमें यह पहली डिस्क और पहली डिस्क को अंतिम रूप में देखता है।


एक साल पहले मैंने कार्यात्मक प्रोग्रामिंग कोर्स किया था और एल्गोरिदम के लिए यह चित्र खींचा था। आशा करता हूँ की ये काम करेगा!

(0)  _|_         |          |
    __|__        |          |
   ___|___       |          |
  ____|____  ____|____  ____|____

(1.1) |          |          |
    __|__        |          |
   ___|___      _|_         |
  ____|____  ____|____  ____|____ (A -> B)

(1.2) |          |          |
      |          |          |
   ___|___      _|_       __|__
  ____|____  ____|____  ____|____ (A -> C)

(1.3) |          |          |
      |          |         _|_
   ___|___       |        __|__
  ____|____  ____|____  ____|____ (B -> C)



(2.1) |          |          |
      |          |         _|_
      |       ___|___     __|__
  ____|____  ____|____  ____|____ (A -> B)



(3.1) |          |          |
      |          |          |
     _|_      ___|___     __|__
  ____|____  ____|____  ____|____ (C -> A)

(3.2) |          |          |
      |        __|__        |
     _|_      ___|___       |
  ____|____  ____|____  ____|____ (C -> B)

(3.3) |         _|_         |
      |        __|__        |
      |       ___|___       |
  ____|____  ____|____  ____|____ (A -> B)

3 अंगूठियों की समस्या को 2 2-अंगूठी की समस्या (1.x और 3.x) में विभाजित किया गया है


एक सीएस छात्र के रूप में, आपने गणितीय प्रेरण के बारे में सुना होगा। हनोई के टॉवर का पुनरावर्ती समाधान समान रूप से काम करता है - केवल अलग-अलग हिस्सा वास्तव में बी और सी के साथ खोना नहीं है क्योंकि पूरा टावर समाप्त होता है।


जैसा कि हमारे कुछ दोस्तों ने सुझाव दिया है, मैंने पिछले दो उत्तरों को हटा दिया है और मैं यहां समेकित हूं।

यह आपको स्पष्ट समझ देता है।

सामान्य एल्गोरिदम क्या है ....

कलन विधि:

solve(n,s,i,d) //solve n discs from s to d, s-source i-intermediate d-destination
{
    if(n==0)return;
    solve(n-1,s,d,i); // solve n-1 discs from s to i Note:recursive call, not just move
    move from s to d; // after moving n-1 discs from s to d, a left disc in s is moved to d
    solve(n-1,i,s,d); // we have left n-1 disc in 'i', so bringing it to from i to d (recursive call)
}

यहां कामकाजी उदाहरण है यहां क्लिक करें


तीन टावर अर्थात् स्रोत टावर, गंतव्य टावर और सहायक टावर हैं। स्रोत टावर में सभी डिस्क हैं और आपका लक्ष्य सभी डिस्क को गंतव्य टावर में ले जाना है और ऐसा करने में सुनिश्चित करना है, आपने कभी भी छोटी डिस्क के ऊपर एक बड़ी डिस्क नहीं डाली है। हम नीचे दिए गए चरणों में रिकर्सन का उपयोग करके इस समस्या को हल कर सकते हैं:

हमारे पास स्रोत टावर पर डिस्क की संख्या है

बेस केस: एन = 1 यदि स्रोत टावर में केवल एक डिस्क है, तो इसे गंतव्य टावर पर ले जाएं।

रिकर्सिव केस: एन> 1

  • शीर्ष एन -1 डिस्क डिस्क स्रोत टावर से सहायक टॉवर तक ले जाएं
  • गंतव्य टॉवर पर केवल शेष, nth डिस्क (चरण 1 के बाद) को ले जाएं
  • अब एन-1 डिस्क को हेल्पर टॉवर में गंतव्य पर ले जाएं
    टावर, एक सहायक के रूप में स्रोत टावर का उपयोग कर।

जावा में स्रोत कोड:

private void towersOfHanoi(int n, char source, char destination, char helper) {
    //Base case, If there is only one disk move it direct from source to destination
    if(n==1){
        System.out.println("Move from "+source+" to "+destination);
    }
    else{
        //Step1: Move the top n-1 disks from source to helper
        towersOfHanoi(n-1, source, helper, destination);
        //Step2: Move the nth disk from source to destination
        System.out.println("Move from "+source+" to "+destination);
        /*Step3: Move the n-1 disks(those you moved from source to helper in step1) 
         * from helper to destination, using source(empty after step2) as helper
         */
        towersOfHanoi(n-1, helper, destination, source);
    }
}

पहली रिकर्सिव कॉल स्रोत से सबसे बड़ी एक को सहायक सहायक ढेर के रूप में उपयोग करके सभी टुकड़ों को स्थानांतरित करती है। जब सबसे बड़ा छोड़कर सभी टुकड़े किए जाते हैं तो सबसे बड़ा होगा और सबसे बड़ा एक मुफ़्त है। अब आप सबसे बड़े को नष्ट करने के लिए स्थानांतरित कर सकते हैं और सभी टुकड़ों को नियत से स्थानांतरित करने के लिए एक और रिकर्सिव कॉल का उपयोग कर सकते हैं।

रिकर्सिव कॉल सबसे बड़े टुकड़े (यानी वे इसे अनदेखा करेंगे) के बारे में कुछ भी नहीं जान पाएंगे, लेकिन यह ठीक है क्योंकि रिकर्सिव कॉल केवल छोटे टुकड़ों से निपटेंगे और इस प्रकार सबसे बड़े टुकड़े को स्वतंत्र रूप से आगे और पीछे ले जाया जा सकता है।


प्रश्न का उत्तर, प्रोग्राम कैसे जानता है, यह भी "aux" के लिए "src" है, और अजीब "src" को "dst" में खोलने के लिए प्रोग्राम में निहित है। यदि आप 4 डिस्क के साथ मुट्ठी चाल को तोड़ते हैं, तो ऐसा लगता है:

hanoi(4, "src", "aux", "dst");
if (disc > 0) {
    hanoi(3, 'src', 'dst', 'aux');
        if (disc > 0) {
            hanoi(2, 'src', 'aux', 'dst');
                if (disc > 0) {
                    hanoi(1, 'src', 'dst', 'aux');
                        if (disc > 0) {
                            hanoi(0, 'src', 'aux', 'dst');
                                END
                        document.writeln("Move disc" + 1 + "from" + Src + "to" + Aux);
                        hanoi(0, 'aux', 'src', 'dst');
                                END
                        }

4 डिस्क (यहां तक) के साथ पहला कदम भी एसआरसी से ऑक्स तक जाता है।


मुझे दर्द महसूस होता है!

यद्यपि यह एक पुरानी पोस्ट है, मुझे लगता है कि वास्तव में क्या समझने की जरूरत है, यह "इसे इस पर ले जाएं" दृष्टिकोण नहीं है, लेकिन उत्तर में रिकर्सन के दुष्प्रभाव का उपयोग करना शामिल है।

मेरे लिए एक अमूल्य मदद "द लिटिल शेमर" थी जो एक को पुनरावर्ती कार्यों को सोचने और लिखने के लिए सिखाती है।

हालांकि, यह पाठक को अगले रिकर्सिव कॉल में लौटाए गए परिणाम के परिणामों का उपयोग करने के लिए सिखाता है।

हनोई के टॉवर में, जवाब प्रतिफल परिणाम में नहीं है, लेकिन लौटा परिणाम के अवलोकन में।

जादू फ़ंक्शन पैरामीटर के सफल पुनर्वसन में होता है।

हां समस्या वास्तव में तीन भागों में है:

  • एक छोटे टावर को अतिरिक्त पेग में ले जाना
  • गंतव्य डिस्क पर अंतिम डिस्क ले जा रहा है
  • शेष पेड़ को अतिरिक्त पेग पर गंतव्य पेग पर ले जाना।

योजना में:

(define (th n a b c)
    (if (zero? n) 'done
        (begin
           (th (- n 1) a c b)
           (display (list a c))
           (newline)
           (th (- n 1) b a c))))
(th 5 'source 'spare 'destination)

हालांकि यह फ़ंक्शन पैरामीटर का प्रदर्शन है जो समस्या का समाधान है और कॉल की संरचना जैसे डबल पेड़ को महत्वपूर्ण रूप से समझना है।

समाधान proof by induction की शक्ति और परंपरागत नियंत्रण संरचनाओं के साथ कुश्ती वाले सभी प्रोग्रामर को एक गर्म चमक बताता है।

संयोग से, हाथ से समस्या को हल करने के लिए काफी संतोषजनक है।

  • डिस्क की संख्या गिनें
  • यदि यहां तक ​​कि, पहली डिस्क को अतिरिक्त पेग पर ले जाएं, तो अगला कानूनी कदम बनाएं (शीर्ष डिस्क शामिल नहीं है)। फिर शीर्ष डिस्क को गंतव्य पेग पर ले जाएं, अगली कानूनी चाल (nittd) बनाएं। फिर शीर्ष डिस्क को स्रोत पेग पर ले जाएं, अगली कानूनी चाल (nittd) बनाएं ...
  • यदि अजीब है, तो पहली डिस्क को गंतव्य पेग पर ले जाएं, अगला कानूनी कदम बनाएं (शीर्ष डिस्क शामिल नहीं है)। फिर शीर्ष डिस्क को अतिरिक्त पेग पर ले जाएं, अगली कानूनी चाल (nittd) बनाएं। फिर शीर्ष डिस्क को स्रोत पेग पर ले जाएं, अगली कानूनी चाल (nittd) बनाएं ...

हमेशा एक ही हाथ से शीर्ष डिस्क पकड़े हुए और हमेशा उसी दिशा में उस हाथ को ले जाकर सर्वश्रेष्ठ किया जाता है।

n डिस्क के लिए चाल की अंतिम संख्या 2^n - 1 , move n disc to destination लिए move n disc to destination के माध्यम से आधे रास्ते है।

आखिरकार, यह मजाकिया है कि एक सहयोगी, आपकी पत्नी / पति या यहां तक ​​कि कुत्ते (यहां तक ​​कि वे जो भी नहीं सुन रहे हैं) को समस्या का वर्णन कर सकते हैं।


मैं भी रिकर्सन पाने की कोशिश कर रहा हूं।

मुझे लगता है कि एक रास्ता मिला है,

मैं इसे चरणों की एक श्रृंखला की तरह सोचता हूं (चरण स्थिर नहीं है यह पिछले नोड के आधार पर बदल सकता है)

मुझे 2 चीजों को समझना है:

  1. पिछले नोड
  2. कदम दयालु
  3. कदम के बाद कॉल से पहले और क्या (यह अगली कॉल के लिए तर्क है

उदाहरण

कारख़ाने का

1,2,6,24,120 ......... या

1,2 * (1), 3 * (2 * 1), 4 * (3 * 2 * 1,5 * (4 * 3 * 2 * 1)

अंतिम नोड द्वारा चरण = एकाधिक

चरण के बाद मुझे अगले नोड, सार 1 तक पहुंचने की आवश्यकता है

ठीक

function =

n*f(n-1) 

its 2 steps process
from a-->to step--->b

मुझे इस मदद की उम्मीद थी, बस 2 थानिक के बारे में सोचें, नोड से नोड तक कैसे प्राप्त करें, लेकिन नोड -> चरण -> नोड

नोड -> चरण फ़ंक्शन चरण का शरीर है -> नोड अन्य फ़ंक्शन का तर्क है

अलविदा :) उम्मीद है कि मैंने मदद की


यह आसान है। मान लीजिए कि आप ए से सी में जाना चाहते हैं

अगर केवल एक डिस्क है, तो बस इसे ले जाएं।

यदि एक से अधिक डिस्क हैं, तो करें

  • सभी डिस्क (एन -1 डिस्क) को ले जाएं, नीचे ए से बी को छोड़कर
  • नीचे डिस्क को ए से सी तक ले जाएं
  • एन-1 डिस्क को ए से सी के पहले चरण से ले जाएं

ध्यान रखें कि, एन -1 डिस्क को स्थानांतरित करते समय, एनएच बिल्कुल कोई समस्या नहीं होगी (एक बार यह सभी अन्यों की तुलना में बड़ा हो)

ध्यान दें कि n-1 डिस्क को फिर से उसी समस्या पर दोबारा शुरू किया जाता है, जब तक कि n-1 = 1 तक, इस मामले में आप पहले पर होंगे (यदि आपको इसे अभी स्थानांतरित करना चाहिए)।


यहां स्पष्टीकरण जाता है। तस्वीर को देखो ->

Movetower(3,a,b,c) कॉल करके, आप टावर A से टॉवर B तक सभी 3 डिस्क को स्थानांतरित करना चाहते हैं। तो अनुक्रमिक कॉल हैं ->

1. Movetower(3,a,b,c)  // No Move needed
2. Movetower(2,a,c,b)  // No move needed
3. Movetower(1,a,b,c)  // Here is the time to move, move disc1 from a to b
4. Movetower(2,a,c,b)  // Returning to this call again, this is the time to move disc2 from a to c
5. Movetower(1,b,c,a)  // Again the time to move, this time disc1 from b to c
6. Movetower(3,a,b,c)  // Returning to this call again, this is the time to move disc3 from a to b
7. Movetower(2,c,b,a)  // Not the time to move
8. Movetower(1,c,a,b)  // Here is the time to move, move disc1 from c to a
9. Movetower(2,c,b,a)  // Returning to this call again, this is the time to move disc2 from c to b
10.Movetower(1,c,a,b)  // Here is the time to move, move disc1 from a to b

आशा करता हूँ की ये काम करेगा :)

एनीमेशन के लिए: https://www.cs.cmu.edu/~cburch/survey/recurse/hanoiex.html


http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html पर पुनरावर्ती हनोई कार्यान्वयन का एक अच्छा स्पष्टीकरण है।

सारांश यह है कि, यदि आप नीचे की प्लेट को स्टिक ए से चिपकाने के लिए ले जाना चाहते हैं, तो आपको पहले ए से सी तक सभी छोटी प्लेटों को स्थानांतरित करना होगा। दूसरी रिकर्सिव कॉल तब प्लेटों को स्थानांतरित करने के लिए है जिन्हें आप सी में ले जाते हैं आपके बेस केस के बाद बी पर वापस एक बड़ी बी को ए से बी तक ले जाया गया।


Tower (N,source,aux.dest):

  1. if N =1 Then
       Write : Source -> dest
       return
    end of if
    
  2. पीजी स्रोत से peg aux तक एन -1 डिस्क ले जाएँ

    call Tower (N-1, source, dest, aux)
    
  3. स्रोत लिखें -> dest
  4. पेग ऑक्स से पेग dest से एन -1 डिस्क ले जाएँ

    call Tower (N-1, source, dest, aux)
    
  5. वापसी

public static void hanoi(int number, String source, String aux, String dest)
{
    if (number == 1)
    {
        System.out.println(source + " - > "+dest);
    }
    else{
        hanoi(number -1, source, dest, aux);
        hanoi(1, source, aux, dest);
        hanoi(number -1, aux, source, dest);
    }
}

void TOH(int n, int a, int b){
        /*Assuming a as source stack numbered as 1, b as spare stack numbered as 2 and  c as target stack numbered as 3. So once we know values of a and b, we can determine c as there sum is a constant number (3+2+1=)6.
       */
int c = 6-a-b;
if(n==1){
    cout<<"Move from "<<a<<" to "<<b<<"\n";
}
else{
    // Move n-1 disks from 1st to 2nd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.
    TOH(n-1, a, c);
    // Move the last alone disk from 1st to 3rd stack.
    TOH(1, a, b);
    // Put n-1 disks from 2nd to 3rd stack. As we are not allowed to move more than one disks at a time, we do it by recursion. Breaking the problem into a simpler problem.        
    TOH(n-1, c, b);
}
}
int main() {

TOH(2, 1, 3);
cout<<"FINISHED                        \n";
TOH(3, 1, 3);
cout<<"FINISHED                        \n";
TOH(4, 1, 3);
return 0;
}




towers-of-hanoi