하노이의 탑 플래쉬 게임.

며칠전 스펀지에서 방송된 하노이 탑의 플래시게임 입니다.
집행력과 집중력을 향상시킨다고 방송되었습니다.

플래쉬로 제작된 하노이의 탑 입니다.
당신의 능력을 테스트해보세요. ^^

게임규칙.
1. 한번에 하나만 이동.(모든 원판을 마지막 기둥으로.)
2. 작은원반 위로 큰 원반을 이동할 수 없다.
3. 최소 이동횟수로 이동. (최소이동횟수=2^원판수-1)
    원판이 3개일때 최소이동횟수는 2*2*2 -1 =7 회
4. 가장위의 원판만 이동가능.

하노이의 탑 게임1

 

하노이의 탑 게임2
(출처: http://www.mathsisfun.com/games/towerofhanoi.html)
 

최소이동 횟수:
원판 3 개 : 2*2*2-1 = 7 회
원판 4 개 : 2*2*2*2-1 = 15 회
원판 5 개 : 2*2*2*2*2-1 = 31 회 (5개의 원판을 최소횟수로 이동하는 플래쉬화면)
원판 6 개 : 2*2*2*2*2*2-1 = 63 회
원판 7 개 : 2*2*2*2*2*2*2 -1 = 127 회

이동법칙: 이동하려는 원판의 수가 홀수일때는 이동하고자하는 막대로 보내고
이동하려는 원판의 수가 짝수일때는 이동하고자하는 막대를 제외한 막대로 먼저 보낸다.

하노이의 탑 의 규칙성
첫번째. 원판이 둘일때를 생각해 봅니다. 가장위의 원판을 목표하는 기둥으로 보내는 가장아래원판을 이동할수 없지요. 그래서 맨위의 원판을 목표기둥 이외의 기둥으로 보냅니다. 그리곤 맨아래 원판을 목표기둥으로 보내고 빼두었던 맨위의 원판을 목표기둥으로 보내면됩니다.
두번째. 원판이 셋일때를 생각해 봅니다. 둘일때와 같이 맨위의 원판을 빈기둥으로 보내면 될까요? 이렇게 해서는 맨아래의 원판을 최소횟수로 빼낼수가 없습니다. 그래서 셋일때는 맨위의 원판을 목표한 기둥으로 보냅니다.그리고 가운데 원판을 빈 기둥으로, 맨아래 다시 맨위의 원판을 가운데 원판위에 놓습니다. 이제 맨아래 원판을 목표기둥으로 보냅니다. 두개의 원판이 남았죠?
이는 첫번째 경우와 같은 방법으로 목표기둥으로 보내면 됩니다.

이둘이 하노의 탑을 최소횟수로 이동하는 가장 큰 핵심알고리즘입니다. 원판이 많아져도 셋과 둘일때와 같은 방법, 곧 원판이 짝수일때와 홀수 일때로 나누어 생각하면 되지요.


이 게임은 프로그래밍을 배워온 사람이라면 누구나 만들어 보았을 것입니다.
프로그래밍 알고리즘 중 재귀호출을 배울때 경험해 보았을 것입니다. 재귀호출을 같은 함수를 여러번 계속하여 호출하여 하나의 프로그램을 완성하는 것입니다.

하노이의 탑의 기원을 살펴보면

세상이 만들어 질때 가운데 구멍뚤린 원판이 한 사원에 보관이 되었습니다.
이 원판들은 모두 크기가 달랐으면 세 개의 기둥중 하나의 기둥에 넓은 원판이 아래에 그위에 보다 좁은 원판들로 차례로 포개어져 보관 되었습니다.
이 64개의 원판들을 한번에 하나씩 다른 기둥으로 모두 이동하게 되면 세상의 종말이 올것이라하였습니다.
이를 모두 이동하려면 위의 계산 방식으로 계산해 보면 2^64-1 = 18446744073709551615 번의 이동이 필요하고 1초에 하나의 원판을 이동한다하여도 5833억년 이 소요됩니다. ^^


하노이의 탑 규칙성 게시물