[알고리즘]하노이 탑 (Hanoi Tower) 원리 정리

소개글

- 하노이 타워의 개념
- 하노이 타워의 원리 ( 1개에서.....n개의 막대이동에 관한 정리)
- 그림과 함께 자세한 설명

목차

▶ 동판에 막대가 세 개 있고, 크기가 서로 다른 n 개의
원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은
규칙으로 원판을 다른 막대로 모두 옮기는 놀이를 한다. 총 이동(move)횟수는?
(1) 한 번에 한 개의 원판만을 옮긴다.
(2) 크기가 큰 원판은 반드시 크기가 작은 원판
아래쪽에있어야 한다.

▶ 막대의 갯수가 n개일때, 이동에 관한 원리 이해

본문내용

◑ 일반적으로 n개의 원판이 있을 때 필요한 원판의 이동 회수를 알아보도록 하자.

▶ 먼저 n개의 원판이 있을 때 모두 옮기는데 필요한 원판의 이동회수를 P(n)이라하면,
: P(1) = 1, P(2) = 3, P(3) = 7 임을 알 수 있다.
※ 일반적으로 P(n)은 P(n-1)로 부터 유도..

▶ 3개의 막대가 있을 때,

: 이동횟수는 7회이다.
:
▶ 따라서, <그림2-2>에서 보면
막대의 개수가 n개가 있을 때,

▶ 우선 3개를 <그림1-1>에서 옮기듯이 이동한다.

▶ 그리고, 다음 4번째 막대를
비워있는 곳으로 옮기고,

<그림 1-1>
▶ 미리 옮기 3개를 <그림1-1>의
방법으로 옮긴다.

▶ (n-4)번째도 위에 방법과 동일한 방법으로 반복한다.

▶ 이렇게, 하면 하노이 탑에 쌓인 n개의 모든 막대를 옮길 수가 있게 된다.

참고 자료

사이텍 미디어의 알고리즘 참고 및 서적