컴퓨터개론실습 하노이탑 레포트 공주교육대학교

소개글

공주교육대학교 컴퓨터개론실습 과제 하노이탑 레포트입니다.

목차

1. 하노이 탑의 개념과 규칙
2. 하노이 탑 5단 알고리즘의 자연어서술
3. 하노이 탑 5단 알고리즘의 순서도

본문내용

하노이 탑이란 프랑스 수학자 루카스가 고안한 문제이다. 이 문제에서 세 개의 말뚝과 지름이 서로 다른 임의 개수의 원판이 있고, 가운데 기둥을 이용해서 왼쪽 기둥에 놓인 크기가 다른 원판을 오른쪽 기둥으로 옮겨야 한다. 이때 지름이 큰 원판은 항상 작은 원판보다 아래에 와야 하고 말뚝의 상위에 있는 한 개의 원판만을 이동시킬 수 있다.
원판이 두 개인 경우와 세 개인 경우를 통해 원판을 옮기는 규칙을 알아보자.

가), 나)를 통해서 하노이 탑에서 원판을 옮기는 규칙을 일반화할 수 있다. 하노이 탑의 원판이 n개일 때, a-b-c의 단계를 지나면 문제를 해결할 수 있다. 처음에 놓인 하노이 탑에서 가장 아래의 원판을 n번 원판이라 하자.
a: 왼쪽 기둥에서 n-1개의 원판을 가운데 기둥으로 옮긴다. b: 1번 원판을 오른쪽 기둥으로 옮긴다. c: 가운데 기둥에서 n-1개 원판을 오른쪽 기둥으로 옮긴다

2. 하노이 탑 5단 알고리즘의 자연어서술

처음 배치되어 있는 원판을 위에서부터 1, 2, 3, 4, 5번 원판이라 칭하자.
1~4번 원판을 가운데 기둥으로 옮기고(a단계),
5번 원판을 오른쪽 기둥으로 옮기고(b단계),
1~4번 원판을 오른쪽 기둥으로 옮기면(c단계) 하노이 탑 5단을 해결할 수 있다.
이를 구체적으로 자연어서술이란 방식으로 표현해본다.

참고 자료

없음