하노이탑 하는 방법좀 가르쳐 주세요. 전 4학년에 정보생활에 하노이탑 하는 방법을 배우고 있습니다.
거기에서는 4개의 원판을 3개의 기둥에 끼워야 된다고 합니다.
제발 가르쳐 주세요. 내공 30겁니다.
제발 가르쳐 주세요 ㅠㅠ
답변자님,
정보를 공유해 주세요.
*네이버자료예요 참고하세요*
하노이탑 하는 법
동판에 막대가 세 개 있고, 크기가 서로 다른 4 개의
원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은 규칙으로
원판을 다른 막대로 모두 옮기는 놀이를 생각해 봅시다.
(1) 한 번에 한 개의 원판만을 옮긴다.
(2) 크기가 큰 원판은 반드시 크기가 작은 원판 아래쪽에
있어야 한다.
그러면 원판을 모두 다른 막대로 옮기는데 필요한 최소
이동회수는 모두 몇 번 인가 알아보시오.
| |||||||
하노이탑 문제 (Hanoi Tower Problem)
지난 강좌의 비둘기집 원리에 이어서 이산수학에서의 전형적인 예로 다음을 알아봅시다.
1883년 프랑스 수학자 Edouard Lucas가 제시한 다음과 같은 하노이 탑 문제 (Hanoi Tower Problem) 를 생각하여 봅시다.
Vietnam의 Hanoi시 외곽에 있는 Benares사원의 한가운데 있는 Dome에 다음과 같은 전설이 쓰여져 있는 동판이 있다.
동판에 다이아몬드막대가 세 개 있고, 크기가 서로 다른 64개의 황금 원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은 규칙으로 황금 원판을 다른 막대로 모두 옮기는 놀이를 신(God)이 하고 있다. (1) 한 번에 한 개의 황금 원판만을 옮긴다. (2) 크기가 큰 황금 원판은 반드시 크기가 작은 황금 원판 아래쪽에 있어야 한다. 그러면 신이 이 놀이를 다 마칠 때면 (즉, 황금 원판이 다른 막대로 모두 옮겨졌다면), 이 세상은 연기처럼 사라질 것이다.
위의 무시무시한 전설은 실제로 황금 원판을 한 개 움직이는데 1초가 걸린다면, 황금 원판이 다른 막대로 모두 옮기는데 걸리는 시간은 대략적으로 5,000 억년 이상이 되고, 실제로 우리가 살고 있는 태양계의 추정 수명은 5,000 억년 미만이므로, 이 세상은 연기처럼 사라질 것이다라는 이야기는 과학적으로 증명할 수 있는 사실이기도 하다. (우리가 여러 가지 역사적 사실에서 알 수 있듯이, 예전의 우리 선조들은 놀랍도록 과학적이다 !) 그러면 위의 하노이탑 문제는 어떻게 해결할 수 있는가 알아보도록 하자. 먼저 하노이탑 문제를 일반적으로 기술하면 다음과 같다.
이러한 문제는 전형적인 귀납적사고를 필요로 하는 문제이다. 즉, 특별한 몇 가지의 경우를 관찰하여 일반적으로 적용할 수 있는 규칙을 추론하고 이를 엄밀하게 수학적으로 증명하는 과정을 거쳐 문제를 해결하도록 합시다.
이제 원판이 두 개 뿐이면, 우리는 다음 그림과 같은 단계로 원판을 움직일 수 있다.
따라서 필요한 원판의 이동회수는 3 회이다.
이제 일반적으로 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) 라고 한다. [이에 관하여 우리는 다음에 자세히 학습하도록 한다.] 그러면 위 점화식에 차례로 대입하여 알아보면
등비수열의 합 공식을 이용하면, 일반적으로
구체적으로 검산하여 보면, 우리는 위의 식이 옳음을 알 수 있다. 따라서, 원래의 하노이탑 문제의 경우는 n = 64 인 경우이므로 필요한 원판의 이동 총수 (이것은 가장 최소의 이동 회수를 의미하며, 만약 이동순서를 잘못하면 그만큼 이동회수는 늘어 난다. ) 는
대략 1847 해 (해는 조 단위의 다음 단위)만큼의 이동이 필요하며, 만약 1번의 움직임에 1초가 걸린다고 가정하면, 대략 5000억년 이상이 걸리게 된다. 따라서 이 게임이 끝나게 되면 5000억년 이상의 시간이 경과한 이후이며, 그러면 우리 태양계의 운명도 끝이 난 이후일 것이다. 예전의 우리 선조들의 수학계산 능력이 매우 뛰어남을 짐작을 할 수 있다 (아마도 위와 같은 계산을 하였을까는 학생들의 상상에 맞기도록 합시다.)
이제 하노이탑 문제를 일반화할 수 있는 여러 방법에 대하여 알아보도록 하자.
먼저 다음과 같은 상황을 생각할 수 있다.
위 문제는 하노이탑 문제를 일반화할 수 있는 여러 방법 중 가장 간단한 모양이다. 문제의 가정에서 같은 크기의 2장의 원판은 똑같은 것으로 생각한다고 하였으므로, 2개의 같은 크기의 원판을 계속하여 같은 막대로 옮긴다고 가정하면, 이는 2개의 원판을 한꺼번에 움직인다고 생각하여 계산하여도 될 것이다. 따라서, 우리는 일반화된 하노이탑 문제에서 2n개의 원판이 있을 때 모두 옮기는데 필요한 원판의 이동회수를 A(2n)이라고 하면, 관계식
을 짐작할 수 있다.
위의 상황을 더욱 일반화하면 다음과 같이 생각할 수 있다. 크기 k 인 원판은 nk개이고, m 개의 서로 다른 크기를 갖는 일반화된 하노이 탑의 경우 총 n1+ n2 +... + nk 개의 원판을 모두 옮기는데 필요한 원판의 이동회수 A ( n1,n2,..., nk) 는 얼마인가 등 여러 가지 다양한 일반화를 생각할 수 있다.
이에 관하여는 참고문헌[ Knuth and et-al.]에 있는 Knuth의 책을 참고 하기 바랍니다. |
2009.10.26.
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
하노이탑 하는법
(4개의 원반을 다른 막대에 끼워라)
규칙:한번에 한개씩
규칙2:큰원반이 작은 원반위로가면 안됨
그냥 1,2,3,4로 할게요. 가장 큰수가 가장 작은판임
셋팅:1,2,3,4모두를 왼쪽기둥에 옮긴다.
1번째:4를 맨끝기둥에 옮긴다.
2번째:3을 중간기둥에 옮긴다.
3번째:4를 중간기둥에 옮긴다.
4번째:2를 맨끝기둥에 옮긴다.
5번째:4를 왼쪽기둥에 옮긴다.
6번째:3을 맨끝기둥에 옮긴다.
7번째:4를 맨끝기둥에 옮긴다.
8번째:1을 중간기둥에 옮긴다.
9번째:4를 중간기둥에 옮긴다.
10번째:3을 왼쪽기둥에 옮긴다.
11번째:4를 왼쪽기둥에 옮긴다.
12번째:2를 중간기둥에 옮긴다.
13번째:4를 맨끝기둥에 옮긴다.
14번째:3을 중간기둥에 옮긴다.
마지막:4를 중간기둥에 옮긴다.
이상이었습니다.
원반의 개수 | 최소 이동 횟수 |
1 | 1 |
2 | 3 |
3 | 7 |
4 | 15 |
5 | 31 |
6 | 63 |
7 | 127 |
참고로 고리의 수가 1개늘어날수록 최소 이동 횟수ⅹ2+1이 고리수의 최소 이동 횟수입니다.
그런 방식으로 8번째의 최수 이동 횟수는 127*2+1인 255가 되겠네요.
2009.10.27.
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
아... 하노이탑 8개의 원판을 맨 오른쪽으로 옴기는 놀이로 규칙은 다음과 같습니다.
1.원은 한번에 한개만 옮긴다.
2.아래있는 원판보다 큰 원판을 옮길수 없다.
미리 계산을 해서 최소 횠수가 몇 번인지 알아보세요.
2009.10.29.
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
