나는 하노이 알고리즘을 이해하지 못한다

Question

솔직히 말해서 : 나는 우리가 마침내 재귀를 본 날까지 연초 (고등학교 고등학교)부터 프로그래밍에 능숙 해왔다. 하노이 타워의 재귀 코드를 이해할 수 없습니다. 목적지 타워와 원점 사이를 전환하는 것만 큼 명확하지 않은 점이 있습니다.

기본적으로 재귀가 무엇인지, 스택이 무엇인지는 알지만 타워의 순서가 변경된 이유를 이해할 수 없습니다.

도움을 주시면 대단히 감사하겠습니다. 고맙습니다. 조각 하노이의 탑의 규칙에 따라

private void Déplacer(short N, string o, string i, string d) 
    { 
     if (N == 1) 
     { 
      MessageBox.Show("Move " + o + "to " + d); 
      lstUn.Items.Add((lstUn.Items.Count + 1).ToString() + "-" + "Move " + o + " vers " + d); 
      return; 
     } 


     else 
     { 
     //Switch d and i 
      Déplacer((short)(N - 1), o, d, i); 
      lstUn.Items.Add((lstUn.Items.Count + 1).ToString() + "-" + "Déplace " + o + " vers " + d); 
      MessageBox.Show("Déplace " + o + " vers " + d); //1 vers 3 
      Déplacer((short)(N - 1), i, o, d); 

     } 

Answer 1

의 // N 번호, 당신은 작은 하나의 위에 더 큰 디스크를 넣을 수 없다.

3 개의 타워를 상상해보십시오. 타워 1에는 3 개의 디스크가 있습니다. 세 개의 디스크를 타워 3으로 이동하려면 가장 큰 디스크를 타워 1에서 타워 3으로 이동할 수 있어야합니다. 즉, 타워 1에서 타워 2로 두 개의 작은 디스크를 이동해야한다는 것을 의미합니다. 타워 1에서 타워 2로 두 디스크를 어떻게 이동합니까? 자, 디스크 1을 타워 3으로 옮겨야합니다. 그러면 디스크 2를 타워 2로 이동할 수 있습니다. 그러면 디스크 1을 타워 3에서 타워 2로 이동할 수 있습니다. 이제 디스크 3을 타워 3으로 이동할 수 있습니다. 두 개의 디스크를 타워 2에서 타워 3으로 이동해야합니다. 이는 디스크 1을 타워 1로 이동한다는 것을 의미합니다. 그런 다음 디스크 2를 타워 3에 놓습니다. 마지막으로 디스크 1에서 타워 3으로 이동하여 프로세스를 완료합니다.

그리고 이것이 알고리즘의 본질입니다. 하나의 타워에서 다른 타워로 몇 개의 디스크를 이동해야 할 때마다 재발합니다.

규칙의 결과로 가장 작은 디스크가 다른 모든 단계로 이동한다는 것입니다.

Answer 2

알고리즘에 대한 좋은 설명은 코드가 두 재귀 단계를 가지고 있기 때문에 타워의 순서가 변경

Answer 3

이 알고리즘의 구현을 줄 거의 라인이 얼마나 http://en.wikipedia.org/wiki/Tower_of_Hanoi#Recursive_solution

공지 사항에서 확인할 수 있습니다 다른 목적. 그 중 하나는 "타워 A에서 타워 C로 전체 스택 이동"(목표 1)입니다. 다른 목적은 "B 타워에 반지를 모두 넣어 타워 A에서 타워 C로 하단 링을 이동"(목표 2)입니다.

3 개의 링이있는 예를 보면 가장 쉽게 이해할 수 있습니다. 처음에 우리가 가진 :

A (3)(2)(1) 
B 
C 

우리는 C A에서 반지를 이동하지만, 우리가 처음 따라서 C.에 바닥 반지를 넣을 필요가하고 싶은, 우리는 목표 # 2로 시작합니다. 목표 # 2에서, 우리는 우리가 목표 # 1를 얻을 때 그것으로 스테핑 따라서, B 위에 다른 링을 모두 이동해야하지만, 대상 탑이 한 번 이루어 B로 변경, 우리가 얻을 :

A 
B (2)(1) 
C (3) 

이제 B부터 C까지 목표 # 1이 있습니다.하지만이를 수행하기 위해 먼저 B에서 C까지의 목표 # 2가 있습니다 (목표는 B에서 A까지 목표입니다). 그래서, 기본적으로 대상 타워가 변경됩니다. 왜냐하면 각 재귀 단계에서 목표 1과 목표 2 사이를 전환하기 때문입니다.