하노이 탑

하노이 탑에는 조건이 있다.

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.

2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

 

n개의 원판이 있고 a에서 c까지 보낸다고 했을 떄 예를 보자

 

n이 1인 경우

이 경우는 바로 c까지 보내면 된다. cout << a << " " c;

 

n이 2인 경우

이 경우에는 (n-1)이 a에서 b까지 옮긴다. == top(n-1),a,c,b 

그 다음은 n이 1연 경우랑 마찬가지로 제일 큰 원판을 c까지 보내면 된다.  cout << a << " " c;

마지막으로 (n-1)을 b에서 c까지 옮김 == top(n-1),b,a,c  

여기서 재귀를 볼 수 있다. 더 자세히 보게 n3인경우를 보자.

 

n이 3인경우

(n-1)이 a에서 b까지 옮긴다. == top(n-1),a,c,b  (위에 방법으로 재귀 함수를 통해 알 수 있음)

그 다음은 n이 1연 경우랑 마찬가지로 제일 큰 원판을 c까지 보내면 된다.  cout << a << " " c;

마지막으로 (n-1)을 b에서 c까지 옮김 == top(n-1),b,a,c  

이를 바탕으로 재귀함수 작성한다.

코드

#include<iostream>
using namespace std;
void top(int n ,int a,int b ,int c ) // a에서 c까지 
{
    if (n > 0)
    {
        top(n - 1, a, c, b); // n-1은 a에서 b로 보낸다
        cout << a <<" "<< c<<endl; // 마지막원판은 a에서 c번째로 
        top(n - 1, b, a, c);  // n-1은 b에서 c로 보낸다.
    }
}
int main()
{
    int n;
    cin >> n;
    top(n,1,2,3);
    return 0;
}