'하노이타워'에 해당되는 글 2건
- 2009.02.12 하노이탑 풀이 - 4층, 5층, 그리고 그 이상...
- 2009.02.12 하노이탑 풀이 (Hanoi tower)
반응형
하노이탑 3층 풀이에 이어 4층, 5층 풀이 입니다. 3층 풀이를 보시지 않으신 분들은 4층 풀이를 보기 전에 먼저 3층 풀이에 있는 '처음에 어떤 기둥으로 옮길 것인지'를 결정하는 방법과 3층 풀이를 충분히 보시기 바랍니다.
여기서는 3층 풀이에 해당하는 부분은 어느정도 생략되어 있습니다.
아래 link는 컴퓨터 상에서 해 볼 수 있는 하노이탑 게임입니다. 아래 설명을 보시면서 직접 해 보시면 더 이해가 쉬우실 것입니다.
하노이탑 4층 풀이
아래의 4개 층으로 된 탑을 1번 기둥에서 3번 기둥으로 옮기는 것입니다.
1번째 옮겨갈 위치는 4개 층이므로 3,2,3,2로 2번 기둥입니다.
그리고 3층 옮기기와 동일하게 하여 아래와 같이 3층을 2번 기둥으로 옮깁니다.
드디어 제일 큰 층을 목표기둥인 3번으로 옮길 수 있습니다.
이제 2번 기둥에 있는 3층탑을 3번 기둥으로 옮겨야 됩니다. 다음 차례에 제일 작은 층을 1, 3 번 기둥 중 어디로 옮겨야 할까요?
3개 층으로 된 탑을 3번으로 옮기는 것과 동일하기 때문에 3,1,3로써 3번 기둥으로 옮기면 됩니다.
역시 중간과정은 3층 옮기는 것과 동일합니다.
전체 15번으로 옮기기가 완료되었습니다.
하노이탑 5층 풀이
4층까지 했다면 그 이상의 층에서도 방법은 동일합니다. 중간에 어느쪽으로 옮겨갈 것인지만 잘 결정하시면 어려움이 없습니다.
처음 옮길 위치는 3,2,3,2,3으로 3번 기둥입니다.
3층 옮기기의 과정으로 아래와 같이 되었습니다.
4층 옮기기와 마찬가지로 4번째 층을 2번 기둥으로 옮깁니다.
이제 3번 기둥에 있는 3층탑을 2번으로 옮기는 과정입니다. 처음 옮길 위치는 2,1,2로 2번 입니다.
이렇게 해서 3층 옮기기가 완료되면 결과적으로 2번 기둥으로 4층옮기기가 완료되었습니다.
이제 제일 큰 층을 목표기둥인 3으로 옮깁니다.
2번 기둥의 4개층을 3번기둥으로 옮기는 것과 동일합니다.
처음 옮겨가야 할 곳은 3,1,3,1로 1번 기둥입니다.
3층 옮기기까지 완료되었습니다.
이제 2번에 있는 층을 기둥으로 3으로 옮기고 나서 보니 1번 기둥의 3층탑을 3번 기둥으로 옮기는 과정만 남았네요.
역시 다음에 옮길 위치는 3,2,3으로 3번 기둥입니다.
모두 31번의 과정을 통해 5층탑의 이동이 완료되었습니다.
이렇게 3, 4, 5층의 하노이탑을 옮기는 과정을 살펴보았습니다.
여기까지 하셨다면 지금까지와 동일한 방법으로 6, 7, 8 혹은 그 이상의 층도 문제없이 하실 수 있다는 걸 아실 것입니다.
앞에서도 말씀드렸지만 중간에 어느층으로 이동할지만 잘 결정하시면 순서가 뒤섞이는 일 없이 끝까지 해 내실 수 있으실 것입니다.
반응형
반응형
하노이탑(하노이 타워)를 잘 할 수 있는 방법을 소개해 드립니다.
작년엔가 모 방송사의 스펀지라는 프로그램에서 공부잘하는 방법으로 소개된 것 중의 하나가 하노이탑입니다.
6살 아이에게 시켜 봤더니 꽤 흥미있어하며 오랫동안 집중력을 보이더군요.
직접 하다보면 그 속에 숨어있는 풀이방법의 원리를 깨우치게 되겠지만, 여기서는 부모나 이 게임을 가르쳐 주고자 하는 분들을 위해 그 풀이의 원리를 간단히 소개 드립니다.
이번에는 간단히 게임의 규칙과 처음 옮겨야 할 탑의 위치, 그리고 3층탑을 옮기는 방법을 소개해 드리겠습니다.
다음에는 4층, 5층, 그리고 그 이상의 층에 대해서도 옮기는 원리를 말씀드리겠습니다.
아래 link는 컴퓨터 상에서 해 볼 수 있는 하노이탑 게임입니다. 아래 설명을 보시면서 직접 해 보시면 더 이해가 쉬우실 것입니다.
게임의 목표
1. 한 쪽 기둥에 크기 순서대로 쌓여 있는 여러 층의 탑을 동일한 순서대로 다른 기둥으로 옮기는 것
위의 그림처럼 1번 기둥에서 아래 규칙대로 움직여서 최종적으로 3번 기둥으로 옮기는 거죠.
게임 규칙
1. 한 번에 한개의 층만을 다른 기둥으로 옮길 수 있다
2. 옮기려는 기둥에는 아무것도 없거나 옮기려는 층보다 큰 층이 있을 경우에만 옮길 수 있다
3. 옮기려는 기둥에 옮기려는 층보다 작은 층이 이미 있을 경우 그 기둥으로 옮길 수 없다.
4. 가능한 적은 회수로 전체 탑을 다른 기둥으로 옮긴다.
위 그림에서와 같이 2번 기둥에 있는 층은 자신보다 큰 층이 있는 1번 기둥으로는 옮길 수 있으나 자신보다 작은 층이 있는 3번 기둥으로는 옮길 수 없습니다.
처음 옮겨가야 할 기둥은 어디?
하나의 층이 옮겨갈 수 있는 곳은 최대 두군데 입니다. 아래 그림처럼 1번 기둥에 탑이 쌓여 있고 최종적으로 3번 기둥으로 모두 옮기고자 할 경우 제일 처음에 제일 작은 층은 2번 기둥으로 가야 할까요? 아니면 3번 기둥으로 가야할까요?
처음에 어디로 옮기느냐에 따라 마지막에 전체 탑이 어느 기둥으로 옮겨지는지 결정됩니다.
제일 처음 옮겨가야 할 기둥은 다음과 같이 간단히 결정할 수 있습니다.
- 제일 밑에 있는 층이 목표인 3번 기둥으로 간다
- 그 위의 층은 다른 기둥인 2번으로 간다
- 다시 그 위의 층은 앞의 기둥과 다른 2번 기둥으로 간다
이렇게 하면 3층인 탑은 3,2,3으로 제일 처음 3번 기둥으로 옮기면 됩니다. 마찬가지로 8층 탑의 경우는 3,2,3,2,3,2,3,2로 제일 처음 2번 기둥으로 옮겨야 합니다.
3층탑 옮기는 방법
다음은 3층탑을 옮기는 방법입니다.
첫번째 옮기는 위치는 앞에서 알아본 봐와 같이 목표인 3번 기둥입니다.
그 다음 두번째로 큰 층을 비어 있는 2번 기둥으로 옮깁니다.
제일 작은 층을 다시 두번째 층 위로 옮깁니다.
제일 큰 층을 목표인 3번 기둥으로 옮깁니다.
제일 작은 층을 비어 있는 1번 기둥으로 옮깁니다. 여기서도 2번 기둥에 있는 2층 탑을 3번으로 옮긴다고 생각하면 제일 작은 층이 어디로 가야할 지는 쉽게 결정할 수 있습니다. (앞에서의 방법에 따라 3,1로 1번 기둥으로 가야겠죠..)
드디어 모든 층이 3번 기둥으로 옮겨져서 게임을 끝내게 됩니다.
3층 탑 옮기기가 익숙해 지면 앞에서 이야기 한 처음 옮겨가야 기둥을 정하는 방법과 3층탑 옮기기를 응용하여 3층 이상의 탑도 쉽게 옮길 수 있게 됩니다.
참고로 층의 개수에 따른 최소로 옮길 수 있는 회수는 다음과 같습니다.
n층의 최소 회수 = 2의 n승 -1
3층일 경우 2의 3승 -1 이므로 2x2x2-1 = 7
4층일 경우 2의 4승 -1 이므로 2x2x2x2-1 = 15
8층일 경우 2의 8승 -1 이므로 2x2x2x2x2x2x2x2x-1 = 255
반응형
Prev
