하노이의 탑
하노이탑 문제(Hanoi Tower Problem)
1883년프랑스 수학자Edouard Lucas가 제시한 다음과 같은하노이 탑 문제 (Hanoi Tower Problem)를 생각하여 봅시다.
Vietnam의 Hanoi시 외곽에 있는 Benares사원의 한가운데있는 Dome에 다음과 같은 전설이 쓰여져 있는 동판이 있다.
동판에 다이아몬드막대가 세 개 있고, 크기가 서로다른 64개의 황금 원판이 한 막대에 꽂혀 있다. 이때, 다음과 같은 규칙으로 황금 원판을 다른 막대로모두 옮기는 놀이를 신(God)이 하고 있다.
(1) 한 번에 한 개의 황금 원판만을 옮긴다.
(2) 크기가 큰 황금 원판은 반드시 크기가 작은 황금 원판 아래쪽에 있어야 한다.
그러면 신이 이 놀이를 다 마칠 때면 (즉, 황금 원판이다른 막대로 모두 옮겨졌다면), 이 세상은 연기처럼사라질 것이다.
동판에 막대가 세 개 있고, 크기가 서로 다른 n 개의원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은
규칙으로 원판을 다른 막대로 모두 옮기는 놀이를 한다.
(1) 한 번에 한 개의 원판만을 옮긴다.
(2) 크기가 큰 원판은 반드시 크기가 작은 원판
아래쪽에있어야 한다.
그러면 원판을 모두 다른 막대로 옮기는데 필요한 이동(move) 회수는 모두 몇 번 인가 알아보시오.
먼저 원판이한 개뿐이라면, 우리가 필요한 원판의 이동회수는1회이다.
이제 원판이두 개뿐이면, 우리는 다음 그림과 같은 단계로 원판을 움직일수 있다.
따라서 필요한 원판의 이동회수는3 회이다.
문제 1. 위의 내용을 참고하여, 하노이탑 문제에서 원판이 세 개일 때 필요한 원판의 최소 이동회수는 모두 몇 회인가 알아보시오. |
이제 일반적으로n개의 원판이 있을 때 필요한 원판의 이동 회수를알아보도록 하자. 이 경우의풀이전략은 다음과 같다.
먼저n개의 원판이 있을 때 모두 옮기는데 필요한 원판의 이동회수를P(n)이라고 하자. 그러면,
P(1) = 1
P(2) = 3
P(3) = 7
임을 알 수 있다.
일반적으로 P(n)은 P(n-1)로 부터 유도할 수 있다.
즉, 다음의 그림을 참고하여 생각하여 보자.
위의 그림을 보면, 모든 자연수 n에 대하여 우리는 관계식
P(n) = 2 P(n-1) + 1
을 추측할 수 있다.
위와 같은 인접한 항과의 관계식을 우리는점화식(recurrence formula)라고 한다.
그러면 위 점화식에 차례로 대입하여 알아보면
P(1) = 1 P(2) = 2 P(1) + 1 = 2 + 1 = 3 P(3) = 2 P(2) + 1 = 2 x 3 + 1 = 4 + 2 + 1 = 7 P(4) = 2 P(3) + 1 = 2 x 7 + 1 = 8 + 4 + 2 + 1 = 15 .......... |
<자료출저 : 충북대학교>
1. n=1 인 경우: 한번에 A기둥의 고리를 C기둥으로 옮긴다.
2. n=2 인 경우: 첫 번째 고리를 A기둥에서 B로 옮기고 두 번째 고리를 A기둥에서 C기둥으로 옮긴후 B기둥의 고리를 C로 옮긴다.
3. n=3 인 경우: n=2의 방법을 이용하여 첫번째와 두번째 고리를 A기둥에서 C기둥을 이용하여 B기둥으로 옮긴다. 그리고 세번째 고리를 A기둥에서 C기둥으로 옮긴후 다시 첫번째와 두번째 고리를 B에서 C로 이동한다.
4. n>3인 경우: 처음 n-1 개의 고리를 A기둥에서 C기둥을 거쳐 B기둥으로 이동시킨다. 그리고 n 번째 고리를 A기둥에서 C기둥으로 옮기고, n-1개의 고리를 다시 B기둥에서 A기둥을 거쳐 C기둥으로 옮긴다.
요약 :먼저 위쪽의 원반 n - 1개짜리 탑을 다른 막대로 옮겨놓은 다음 탑을 옮기려는 막대로 가장 큰 원반을 옮기고 나머지 원반 n - 1개를 가장 큰 원반 위로 옮겨놓으면 된다.