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

등록일 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이다.
따라서 이를 관계를 점화식으로 다음과 같이 나타낼 수 있다.
*원하는 자료를 검색 해 보세요.
  • 자료구조 하노이탑 소스 2페이지
    ◈ 하노이탑 ( The Tower of Hanoi ) ◈세 개의 말뚝( A, B, C )과 지름이 서로 다른 임의의 갯수의 원판(disk)이 주어진다. 주어진 조건은 지름이 큰 원판은 항상 작은 원판보다 아래에 오도록하며 말뚝의 상위에 있는 한 개의 원판만을 이동시킬 ..
  • 하노이 탑 과제를 통해 본 아동의 문제 해결 과정 분석 (An analytic study of children's problem solving process with Tower of Hanoi) 12페이지
    The purpose of this study is to analyze the metacognitive process of elementary school students in their ability to carry out the Tower of Hanoi expe..
  • [알고리즘] 하노이탑 4페이지
    하노이 탑"은, "독립된 막대기의 하나에 64개의 크기가 다른 크기의 돌이 크기에 따라 차례차례 쌓여져있는데, 그것을 자신의 돌의 크기보다 더 큰 돌이 쌓일 수 없다는 규칙을 조건으로 다른 곳에 차례차례 옮겨 쌓아야 한다. 단, 돌은 한번에 하나씩만 옮겨야 한다"라는 ..
  • 하노이탑 C 프로그램 레포트 + 소스 0페이지
    하노이탑 C 프로그램 레포트 + 소스(1) 하노이탑이란?(2) 하노이탑의 분할정복과정(3) 하노이탑 C 프로그래밍(4) 실행결과(5) 하노이탑 분석
  • [C언어,자료구조]하노이탑 실행순서 및 이동 횟수 (120층까지) 0페이지
    /* The tower of hanoi */01: #include 02:03: #define MAX_LAYER 12004:05: int Input_hanoi();06: void Show_hanoi(int n);07: void hanoi(int n, ch..
  • [수학] 하노이의 탑 2페이지
    Ⅱ. 『 하노이의 탑 』- 나의 감상 사실, 이 책은 나에게 어려운 책이었다. 처음에 과제로서 읽기는 했지만 수학소설이라는 장르자체부터도 내가 평소 잘 접할 수 있었던 장르의 책이 아니었기 때문에 거리감이 있었다. 더군다나 책 중간 중간 나오는 수학식들은 나로 하여..
  • 하노이탑 관련 자료입니다. (문제 포함) 5페이지
    하노이탑(Hanoi Tower)♥ 하노이탑 (Hanoi Tower)1883년 프랑스 수학자 Edouard Lucas가 제시한 다음과 같은 하노이 탑 문제 (Hanoi Tower Problem) 를 생각하여 봅시다.Vietnam의 Hanoi시 외곽에 있는 Benares사..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기