하노이의 탑(Tower of Hanoi)

 

 

하노이의 탑(Tower of Hanoi)

·         하노이의 탑은 퍼즐의 일종입니다.

·         세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기

·         전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다.

·         수학에서 수열문제이며 프로그래밍에서 재귀함수 이용하여 풀 수 있는 가장 유명한 예제 중의 하나입니다.

 

http://bit.ly/2TRz60z

http://bit.ly/2vrR5kQ 

 

 

제한 사항(게임 규칙)

·         작은 원반은 큰 원반위에만 올라 갈 수 있으며 큰 원반은 작은 원반 위에 올라갈 수 없습니다.

·         한번에 하나의 원반만 옮겨야 한다.

 

 

게임의 목적

위 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.  

 

 

하노이의 탑 원리

일반적으로 원판이 n개 일 때 2n-1번의 이동으로 원판을 모두 옮길 수 있습니다.

3개의 기둥과, n개의 원판이 있습니다.

 

원판을 조건에 맞춰 다른 기둥으로 옮기기 위해 우선 왼쪽 기둥의 n-1개의 원판을 가운데 기둥으로 옮깁니다. 이때 오른쪽 기둥을 이용합니다.

 

그리고 왼쪽 기둥의 원판을 오른쪽 기둥으로 옮깁니다.

 

가운데 기둥의 n-1개의 원판을 오른쪽 기둥으로 옮깁니다.

  

 

하노이의 탑 원리 애니메이션