Thuật toán đệ quy làm việc cho Towers của Hà Nội như thế nào?

Question

Đây là mã từ một cuốn sách tôi đã giải thích đệ quy. Vấn đề là tôi không hiểu các bước tiến hành bởi các chương trình:

var hanoi = function(disc,src,aux,dst) { 
    if (disc > 0) { 
     hanoi(disc - 1,src,dst,aux); 
     document.write("Move disc " + disc + " from " + src + " to " + dst + "<br />"); 
     hanoi(disc - 1,aux,src,dst); 
    } 
}; 

hanoi(3,"src","aux","dst"); 

Đây là cách Output đọc:

Move disc 1 from src to dst 
Move disc 2 from src to aux 
Move disc 1 from dst to aux 
Move disc 3 from src to dst 
Move disc 1 from aux to src 
Move disc 2 from aux to dst 
Move disc 1 from src to dst 

Ai đó có thể phá vỡ này xuống từng bước? Nó sẽ rất hữu ích cho tôi.

Answer 1

Tôi đã tìm ra. Khi được chia nhỏ, mã chạy như sau:

var write = function(string) { 
document.write(string); 
} 

var i = 0; 

var hanoi = function(disc,src,aux,dst) { 
    if (disc > 0) { 
    hanoi(disc - 1,src,dst,aux); 
    write("Move disc " + disc + " from " + src + " to " + dst + "<br />"); 
    hanoi(disc - 1,aux,src,dst); 
    } 
}; 

hanoi(3,"src","aux","dst"); 

/* 
hanoi(3,"src","aux","dst"); 
    if (disc > 0) { 
    hanoi(2,'src','dst','aux'); 
     if (disc > 0) { 
     hanoi(1,'src','aux','dst'); 
      if (disc > 0) { 
      hanoi(0,'src','dst','aux'); 
       END 
      write("Move disc " + 1 + " from " + src + " to " + dst + "<br />"); 
      hanoi(0,'aux','src','dst'); 
       END 
      } 
     write("Move disc " + 2 + " from " + src + " to " + dst + "<br />"); 
     hanoi(1,'dst','src','aux'); 
      if (disc > 0) { 
      hanoi(0,'src','dst','aux'); 
       END 
      write("Move disc " + 1 + " from " + src + " to " + dst + "<br />"); 
      hanoi(0,'aux','src','dst'); 
       END 
      } 
     } 
    write("Move disc " + 3 + " from " + src + " to " + dst + "<br />"); 
    hanoi(2,'aux','src','dst'); 
     if (disc > 0) { 
     hanoi(1,'aux','dst','src'); 
      if (disc > 0) { 
      hanoi(0,'src','dst','aux'); 
       END 
      write("Move disc " + 1 + " from " + src + " to " + dst + "<br />"); 
      hanoi(0,'aux','src','dst'); 
       END 
      } 
     write("Move disc " + 2 + " from " + src + " to " + dst + "<br />"); 
     hanoi(1,'src','aux','dst'); 
      if (disc > 0) { 
      hanoi(0,'src','dst','aux'); 
       END 
      write("Move disc " + 1 + " from " + src + " to " + dst + "<br />"); 
      hanoi(0,'aux','src','dst'); 
       END 
      } 
     } 
    } 
*/ 

Phần khó hiểu nhất này là hình dung END của vòng lặp đệ quy đầu tiên. Chỉ khi đĩa == 0 thì câu lệnh với đĩa == 3 cuối cùng cũng được viết.

Answer 2

lẽ là giải pháp đơn giản nhất để Towers Hà Nội làm việc như thế này:

Để di chuyển x đĩa từ peg A đến peg C, sử dụng peg B như một "aux" peg:

1. Move x-1 đĩa từ chốt A đến chốt B, sử dụng chốt C làm chốt móc.
2. Di chuyển x đĩa thứ hai từ cọc A sang cọc C (không cần chốt móc, vì bạn chỉ di chuyển một đĩa).
3. Di chuyển các đĩa x-1 từ giá peg B sang giá trị C, sử dụng giá trị peg A làm giá đỡ aux.

Lưu ý rằng để di chuyển x đĩa, bạn phải di chuyển x-1 đĩa. Bạn chỉ có thể sử dụng cùng một chức năng để di chuyển các đĩa x-1 này và chỉ chuyển đổi các chốt là nguồn, đích và chốt aux. Đó là điều làm cho Towers of Hanoi trở thành một ví dụ phổ biến về đệ quy, và đó là kiểu mẫu mà bạn cần thấy trong một vấn đề để làm cho công việc đệ quy cho bạn. Nó không cần phải "di chuyển x-1 đĩa", tất nhiên ... nó có thể là một cái gì đó như "danh sách thư mục con này". Cây (giống như một thư mục với thư mục con và như vậy) là một nơi mà đệ quy tỏa sáng. Cũng giống như các công việc khác, nơi để thực hiện công việc trên một mục, bạn có thể cần thực hiện cùng một công việc trên các mục con.

Bây giờ, để có đệ quy hữu ích, bạn cần "trường hợp cơ sở" - điều kiện nơi đệ quy sẽ dừng lại. Nếu bạn không, mã sẽ chạy mãi mãi (hoặc ít nhất là nó sẽ hết bộ nhớ hoặc tràn ngăn xếp cuộc gọi). Trường hợp cơ sở ở đây xảy ra khi x == 0 (vì di chuyển 0 đĩa nghĩa là bạn không làm gì, do if xung quanh thịt của hàm). Nó cũng có thể là khi x == 1, như sau đó bạn không phải recurse, nhưng thêm if trước khi mỗi cuộc gọi hanoi sẽ thêm một chút tiếng ồn (và lợi ích chính cho một giải pháp đệ quy là sự đơn giản của nó). Dù sao, khi x == 0, hàm trả về mà không làm bất cứ điều gì. Hàm được gọi là nó (có x == 1) bây giờ được tiếp tục làm việc của nó - trong trường hợp này, nói "di chuyển đĩa 1 từ src đến dest", và sau đó gọi hàm hanoi một lần nữa với các chuyển đổi args.

Dòng chảy đi một chút như thế này:

hanoi(3, src, aux, dest) 
    hanoi(2, src, dest, aux) 
    hanoi(1, src, aux, dest) 
     hanoi(0, src, dest, aux)  // no op 
     print "Move 1 from src to dest" 
     hanoi(0, aux, src, dest)  // no op 

    print "Move 2 from src to aux" 

    hanoi(1, dest, src, aux) 
     hanoi(0, dest, aux, src)  // no op 
     print "move 1 from dest to aux" 
     hanoi(0, src, dest, aux)  // no op 

    print "move 3 from src to dest" 

    hanoi(2, aux, src, dest) 
    hanoi(1, aux, dest, src) 
     hanoi(0, aux, src, dest)  // no op 
     print "Move 1 from aux to src" 
     hanoi(0, dest, aux, src)  // no op 

    print "Move 2 from aux to dest" 

    hanoi(1, src, aux, dest) 
     hanoi(0, src, dest, aux)  // no op 
     print "move 1 from src to dest" 
     hanoi(0, aux, src, dest)  // no op