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

등록일 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이다.
따라서 이를 관계를 점화식으로 다음과 같이 나타낼 수 있다.
*원하는 자료를 검색 해 보세요.
  • 하노이탑 0페이지
    1. 탑의 이동의 조건 ? a에 있는 ring둘을 b로 옮기는 문제 ? 한 번에 하나의 ring만 옮길 수 있음 ? 작은 ring은 반드시 큰 ring 위에 있어야 함 ? ring의 개수는 변할 수 있음 그림 1.1 탑의 이동 2. 문제 해결 방법 가. 손으로 그림을 ..
  • [수학] 하노이의 탑 2페이지
    Ⅰ. 『 하노이의 탑 』- 줄거리 「하노이의 탑」의 줄거리는 수학자인 주인공 나 에게 어느 날 하노이 씨 에게서 하노이의 탑이 무너졌다! 이 메시지를 다른 두 명의 수학자에게 보내라. 라는 내용의 이메일을 전해 받으면서 이야기는 시작된다. 하노이의 탑은 세 개의 기둥 ..
  • [자료구조] 자료구조 C로 구현한 하노이탑 2페이지
    ..FILE:하노이탑1.cpp #include #include #define MAX 10 void ringmove(int,char,char,char); void main() { while(1) { int n; printf("\n\n ..
  • 하노이 탑 과제를 통해 본 아동의 문제 해결 과정 분석 (An analytic study of children's problem solving process with Tower of Hanoi) (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..
  • 하노이탑 C 프로그램 레포트 + 소스 4페이지
    하노이탑 C 프로그램 레포트 + 소스(1) 하노이탑이란?(2) 하노이탑의 분할정복과정(3) 하노이탑 C 프로그래밍(4) 실행결과(5) 하노이탑 분석
  • 컴퓨터과학 : 하노이 탑 프로그래밍 과정에서 나타나는 사고 패턴에 관한 심층 분석 (Analysis of Computational Thinking Pattern in Programming Hanoi Tower) (Analysis of Computational Thinking Pattern in Programming Hanoi Tower) 6페이지
    정보과학적 사고는 지식정보가 기반이 되는 정보화 사회에서 중요하게 요구되어진다. 문제를 분석하고,설계하고, 해결하는 과정 속에서 논리적이고 비판적인 사고가 나타나며 그러한 과정의 반복 속에서 분석적이고 재귀적인 사고가 나타나게 된다. 컴퓨터 프로그래밍은 자신의 아이디어..
  • [C언어,자료구조]하노이탑 실행순서 및 이동 횟수 (120층까지) 7페이지
    ..FILE:hanoi.JPG ..FILE:hanoi.cpp #include #define MAX_LAYER 120 int Input_hanoi(); // 원반 수를 입력 받기 위한 함수 선언부 void Show_hanoi(int n); // 11이상..
더보기
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [하노이탑,컴퓨터공학,알고리즘] 하노이탑