하노이의 탑 규칙성

 

이 게시물에서는 하노이탑의 규칙성에 대해 이야기해 보려합니다.

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

최소이동 횟수:
원판 3 개 : 2*2*2-1 = 7 회
원판 4 개 : 2*2*2*2-1 = 15 회
원판 5 개 : 2*2*2*2*2-1 = 31 회
원판 6 개 : 2*2*2*2*2*2-1 = 63 회
원판 7 개 : 2*2*2*2*2*2*2 -1 = 127 회

이동하려는 원판의 수가 짝수와 홀수일때 맨위의 원판을 이동하는 기둥이 다르다는것과 이동의 목표가 맨아래의 원판을 이동가능하게 하기위한것이란 걸 염두에 두시면 쉽게 진행될 것입니다.

아래는 5개의 원판을 최소회수로 이동하는 방법(규칙) 을 플래시로 제작한 것입니다.
(목표기둥: 가장 오른쪽기둥)

 

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


하노이의 탑 의 규칙성

첫번째. 원판이 둘일때를 생각해 봅니다. 가장위의 원판을 목표하는 기둥으로 보내면 가장아래원판을 이동할수 없지요. 그래서 맨위의 원판을 목표기둥 이외의 기둥으로 보냅니다. 그리곤 맨아래 원판을 목표기둥으로 보내고 빼두었던 맨위의 원판을 목표기둥으로 보내면됩니다.

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

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

게임하기 : http://secstart.tistory.com