C++로 보는 하노이탑

1. 하노이 탑
2. 하노이 탑 문제의 해결책
3. 하노이 탑 문제에 대한 C++ 프로그램

이 기사에서는 하노이 탑 문제와 C++의 재귀 솔루션에 대해 설명합니다.

하노이 탑

하노이 탑은 3개의 막대와 막대 주위를 이동할 수 있는 여러 개의 디스크가 포함된 수학 퍼즐입니다. 디스크는 위에서 아래로 내림차순으로 배치되어 스택을 형성합니다.

목표는 목적지(마지막) 로드의 모든 디스크를 이동하여 순서는 동일하게 유지하되 몇 가지 규칙을 따르는 것입니다.

1. 한 번에 하나의 디스크만 이동할 수 있습니다.
2. 어떤 디스크도 자신보다 작은 디스크에 놓을 수 없습니다.

이 규칙에 따라 디스크를 첫 번째 로드 또는 페그에서 마지막 로드로 이동해야 합니다. 이 작업을 수행하는 데 필요한 최소 이동 수는 2^n -1이며 여기서 n은 디스크 수입니다.

이것은 아래 그림에 설명되어 있습니다.

이제 Peg A에 있는 이 세 개의 디스크를 Peg B의 도움을 받아 목적지 Peg C로 이동해야 합니다.

하노이 탑 문제의 해결책

이 문제에 대한 반복적 솔루션과 재귀적 솔루션이 모두 있을 수 있지만 여기서는 디스크 수에 따라 반복적 솔루션이 달라지므로 여기서는 재귀적 솔루션에 대해 설명합니다. 재귀 솔루션의 경우 Peg A에 m 디스크가 있다고 가정합니다.

1. m-1 디스크를 Peg A에서 Peg B로 전송하는 데 동일한 기본 방법이 사용됩니다. 규칙을 위반하지 않는다고 가정하면 디스크 m은 이제 Peg A의 최상위 디스크입니다.
2. 디스크 m을 페그 A에서 대상 페그, 즉 페그 C로 이동합니다. 이는 간단한 절차이며 일반 규칙을 따릅니다.
3. 동일한 방법을 사용하여 방금 Peg B에 올려놓은 m-1 디스크를 Peg B에서 대상 페그, 즉 Peg C로 이동합니다. 제한을 위반하지 않고 디스크 m.
4. 종료 케이스에 도달할 때까지 이 단계를 반복합니다.
5. 종료 사례는 0개의 디스크를 이동하는 것입니다. 즉, 모든 디스크가 대상 페그에 있습니다.

하노이 탑 문제에 대한 C++ 프로그램

이 문제를 해결하기 위한 C++ 프로그램은 다음과 같습니다.

void TowerOfHanoi(int m, string first, string middle, string last) {
  cout << "Current iteration " << m << endl;
  if (m == 1) {
    cout << "Moving Disc from " << first << " to " << last << endl;
  } else {
    TowerOfHanoi(m - 1, first, last, middle);
    cout << "Moving disc " << m << " from " << first << " to " << last << endl;
    TowerOfHanoi(m - 1, middle, first, last);
  }
}
int main() {
  int di = 3;
  TowerOfHanoi(di, "PegA", "PegB", "PegC");
}

그러면 다음과 같은 결과가 나타납니다.

TowerOfHanoi 함수에서 매 반복마다 함수를 두 번 호출합니다. 먼저 첫 번째 말뚝에서 중간으로 이동한 다음 중간에서 마지막으로 이동합니다.

그러면 다음과 같은 트리가 만들어집니다.

main
  |--> TowerOfHanoi(3, ...)
  |      |
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |      |--> TowerOfHanoi(2, ...)
  |      |     |
  |      |     |--> TowerOfHanoi(1, ...)
  |      |     |--> TowerOfHanoi(1, ...)
  |      |<----|
  |<-----|
  |