하노이의 탑은 수학 퍼즐이다. 세 개의 막대(혹은 말뚝 혹은 탑)과 여기에 쌓여질
서로 다른 크기의 원반들로 구성되어있다. 퍼즐이 시작 될 때는 원반들이 한 막대에 크기가
작은 것 부터 큰 순서로 제일 위에는 제일 작은 원반이 있는 원뿔 형태로 쌓여있다.
퍼즐의 목적은 전체 원반을 목적지 막대에 다음 규칙을 지키면서 옮기는 것이다.
- 한번에 한 원반만 옮길 수 있다.
- 옮길 때마다 한 막대의 맨 앞 원반을 다른 막대에 놓여진 원반 위로 올라가게 된다.
- 자기보다 작은 원반 위로 옮길 수 없다.
- 알고리즘
- 맨앞(Source) n-1개의 원반을 중간지점(Intermediate)로 옮긴다.
- 맨앞(Source) n번째 원반을 목표(Destination)지점으로 옮긴다.
- 중간지점(Intermediate)에 있는 n-1개 원반을 목표(Destination)지점으로 옮긴다.
- Java Source
public class TowersOfHanoiExample {
public static void main(String[] args) {
towersOfHanoi(3, 'A', 'B', 'C');
}
public static void towersOfHanoi(int n, char source, char intermediate, char destination) {
// 원반이 하나이면 A(처음)에서 C(목적지)로옮기고 리턴
if(n==1) {
System.out.println("원판 '1'이 기둥" + source + " 에서 기둥 " + destination + "로 이동");
return;
} else {
// STEP1 : n-1개의 원반을 destination(C)를 보조탑으로 이용해서 A에서 B로 이동
towersOfHanoi(n-1, source, destination, intermediate);
// STEP2: 1개를 A에서 C로 이동
System.out.println("원판 " + n + "이 기둥 " + source + " 에서 기둥 " + destination + "로 이동");
// STEP3: n-1개의 원반을 A를 보조탑으로 이용해서 B에서 C로 이동
towersOfHanoi(n-1, intermediate, source, destination);
}
}
}
近期评论