하노이의 탑(feat. 부셔버려)
하노이의 탑
재귀함수 문제의 대명사.
0) 귀납법
1) 1일때 맞다. => 종료조건 (수렴) 2) n일때, n+1도 맞다. => 작업부분(메서드)
1) 종료 조건
n=1일때, 1번째 원반을 시작기둥에서 목표기둥으로 옮긴다.
2) 메서드 부분
- n-1번째까지의 원반을 시작기둥에서 목표기둥이 아닌 제 3의 기둥으로 옮긴다. (n-1개를 동일하게 하노이)
- n번째 원반을 시작기둥에서 목표기둥으로 옮긴다. (1개 옮기는 것)
- n-1번째까지의 원반을 제 3의 기둥에서 목표기둥으로 옮긴다. (n-1개를 동일하게 하노이)
3) 코드
static void moveDisk(int disk_num, int start_stick, int final_stick) {
System.out.printf("%d번 원반을 %d에서 %d로 옮기세요.\n", disk_num, start_stick, final_stick);
}
// n은 원반 개수, start_stick은 시작점 위치,
// final_stick은 목적점 위치, 6-start_stick-final_stick은 나머지 한개 기둥의 위치
static void hanoi(int n, int start_stick, int final_stick) {
if(n==1) {
moveDisk(1, start_stick, final_stick);
return;
}
hanoi(n-1, start_stick, 6-start_stick-final_stick);
moveDisk(n, start_stick, final_stick);
hanoi(n-1, 6-start_stick-final_stick, final_stick);
}
마지막 수정일시: 2022-05-23 18:30
댓글남기기