5. The Tower Of Hanoi ( 하노이 타워 )

 

원반이 3개인 경우의 그림부터 보자.

가장 작은 원반을 1번, 가장 큰 원반을 3번이라고 하자.

[그림 1 : 3개의 원반을 가지는 하노이의 탑 문제 ]

위의 그림에서 원반의 이동의 순서를 알아보도록 하자.

각 이동단계는 아래의 그림들과 같다.

 

[ 그림 Step 1 ]

 

[ 그림 Step 2 ]

 

[ 그림 Step 4 ]

 

[ 그림 Step 5 ]

[ 그림 Step 6 ]

 

[ 그림 Step 7 ]

위 그림을 통해 알 수 있는 규칙은 아래와 같다.

이 규칙은 원반이 4개인 경우에 대해서도 성립한다.

1. A막대기에 꽂혀있는 1번 원반과 2번 원반을 막대기 B로 이동시킨다.

2. 그리고 나서 가장 큰 원반인 3번 원반을 막대기 C로 이동시킨다.

3. B 막대기에 꽂혀있는 1번 원반과 2번 원반을 막대기 C로 이동시킨다.

 

아래는 알고리즘

아래는 프로그램 소스

아래는 프로그램 결과