하노이탑 관련 자료입니다. (문제 포함)

소개글

하노이탑에 관련된 소개 자료와 문제가 포함되어 있는 자료입니다.

목차

없음

본문내용

하노이탑(Hanoi Tower)
♥ 하노이탑 (Hanoi Tower)
1883년 프랑스 수학자 Edouard Lucas가 제시한 다음과 같은 하노이 탑 문제 (Hanoi Tower Problem) 를 생각하여 봅시다.
Vietnam의 Hanoi시 외곽에 있는 Benares사원의 한가운데 있는 Dome에 다음과 같은 전설이 쓰여져 있는 동판이 있다.
동판에 다이아몬드막대가 세 개 있고, 크기가 서로 다른 64개의 황금 원판이 한 막대에 꽂혀 있다. 이 때, 다음과 같은 규칙으로 황금 원판을 다른 막대로 모두 옮기는 놀이를 신(God)이 하고 있다.
(1) 한 번에 한 개의 황금 원판만을 옮긴다.
(2) 크기가 큰 황금 원판은 반드시 크기가 작은 황금 원판 아래쪽에 있어야 한다.
그러면 신이 이 놀이를 다 마칠 때면 (즉, 황금 원판이 다른 막대로 모두 옮겨졌다면), 이 세상은 연기처럼 사라질 것이다.
위의 무시무시한 전설은 실제로 황금 원판을 한 개 움직이는데 1초가 걸린다면, 황금 원판이 다른 막대로 모두 옮기는데 걸리는 시간은 대략적으로 5,000 억년 이상이 되고, 실제로 우리가 살고 있는 태양계의 추정 수명은 5,000억년 미만이므로, “이 세상은 연기처럼 사라질 것이다.” 라는 이야기는 과학적으로 증명할 수 있는 사실이기도 하다.
그러면 위의 하노이탑 문제는 어떻게 해결할 수 있는가 알아보도록 하자.
먼저 하노이탑 문제를 일반적으로 기술하면 다음과 같다.
< 하노이탑 문제 (Hanoi Tower Problem) >
동판에 막대가 세 개 있고, 크기가 서로 다른 n 개의 원판이 한 막대에 꽂혀 있다.
이 때, 다음과 같은 규칙으로 원판을 다른 막대로 모두 옮기는 놀이를 한다.
(1) 한 번에 한 개의 원판만을 옮긴다.
(2) 크기가 큰 원판은 반드시 크기가 작은 원판 아래쪽에 있어야 한다.
그러면 원판을 모두 다른 막대로 옮기는데 필요한 이동(move) 회수는 모두 몇 번 인가 알아보시오.

참고 자료

http://puzzllo.co.kr/board/index.php?boardid=board_pla2&mode=list&goodCode=&k_gubun=1