[하노이탑,컴퓨터공학,알고리즘] 하노이탑

등록일 2003.05.06 MS 워드 (doc) | 4페이지 | 가격 800원

목차

하노이탑에대한 설명
알고리즘 설명
c언어로 구현

본문내용

1883년 프랑스 수학자 루카스(Lucas, E)는 하노이 탑이라고 불려지게 된 유명한 문제를 고안해 내었다. 이것은 세 개의 기둥에서 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽 기둥으로 옮기는 것이다. 가운데 기둥을 이용할 수 있으나 원판은 한 번에 한 번씩만 옮겨야 하고, 절대로 작은 원판 위에 큰 원판을 올려놓을 수 없다. 이동 횟수가 가장 적은 방법을 찾으면서 9개의 원판을 모두 다른 기둥으로 옮겨놓는 게임이다.
원판을 몇 번을 옮겨야 모두 세 번째 기둥으로 옮길 수 있는지를 알아보자.
Tn을 한 기둥 위에 놓여있는 n개의 원판을 다른 기둥으로 옮기는데 필요한 회수라고 하자. n개의 원판을 옮기려면 위쪽에 있는 (n-1)개의 원판을 모두 다른 막대로 옮긴 후에 맨 아래 원판을 빈 막대로 옮기고, 다시 그 위에 (n-1)개의 원판을 옮겨 놓으면, 된다.
곧, n개의 원판을 이동하는 방법을 다음과 같다(기둥의 순서를 A, B, C라 하자)
{A→B로 (n-1)개 이동}+{A→C로 1개 이동}+{B→C로 (n-1)개 이동}
n개의 원판을 옮기는데 필요한 회수와 n+1개의 원판을 옮기는데 필요한 회수 사이에는 다음과 같은 관계가 있음을 알 수 있다.
Tn+1 =Tn + 1 + Tn = 2Tn + 1
한 개의 원판을 옮기는데 필요한 회수는 1이므로 T1 = 1이다.
따라서 이를 관계를 점화식으로 다음과 같이 나타낼 수 있다.
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기