[자료구조] 하노이의 탑 [C언어]

목차

◇ 하노이 탑의 문제를 푸는 방법
◇ 프로그램_하노이의 탑
◇ 실행결과

본문내용

[하노이의 탑] 3개의 탑이 있는데 첫 번째 탑에는 반경이 서로 다른 64개의 원반들이 쌓여있다. 각 원반은 반경이 큰 순서로 아래부터 쌓여있다. 이제 수도승들이 다음규칙에 의해 첫 번째 탑에서 세 번째 탑으로 원판을 옮기려 한다.
a) 한 번에 한 개의 원반만을 다른 탑으로 옮길 수 있다.
b) 쌓아 높은 원반은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 순환/반복 함수를 만들어라.

◇ 하노이 탑의 문제를 푸는 방법
1. 기둥 1에서 N-1개의 원반을 기둥 2로 옮긴다.
2. 기둥 1에서 1개의 원반을 기둥 3으로 옮긴다.
3. 기둥 2에서 N-1개의 원반을 기둥 3으로 옮긴다.

그러면 N-1개의 원반을 옮기는 방법은 기둥 1에서 N-1개의 원반을 기둥 2로 옮기는 방법을 새로운 문제로 생각하고 기둥 1에서 N-2개의 원반을 기둥 3으로 옮겼다가, 기둥 1에서 1개의 원반을 기둥 2로 옮기고 기둥 3에서 N-2개의 원반을 기둥 2로 옮기면 될 것이다.
이런 식으로 N-1개의 원반을 움직이는 문제에서 N-2개의 원반을 움직이는 문제로 문제의 크기를 줄여가다 보면 1개의 원반을 움직이는 기본적인 문제에 도달하게 될 것이다.

참고 자료

없음