하노이 탑 문제(Hanoi Tower problem)는 재귀적 알고리즘의 전형적인 예
주어진 원반이 세 개의 기둥 중 하나에서 다른 기둥으로 옮기는 최소 횟수를 찾는 것이 목표
각 기둥은 크기가 다른 원반을 수납할 수 있으며, 한 번에 하나의 원반만 다른 기둥으로 옮길 수 있다.
하노이 탑 문제의 규칙
- 세 개의 기둥이 있으며, 원반이 하나의 기둥에서 다른 기둥으로 이동해야 한다
- 한 번에 하나의 원반만 이동할 수 있다
- 작은 원반이 큰 원반 위에 있을 수 없다
- B나 C와 같은 중간의 막대를 임시적으로 이용할 수 있으나, 앞의 조건들을 지켜야 한다.
재귀적 알고리즘
n개의 원반을 A에서 C로 옮
기는 방법은 다음과 같이 정의:
- n-1개의 원반을 A에서 B로 옮김
- 남은 가장 큰 원반을 A에서 C로 옮김
- B에 있는 n-1개의 원반을 C로 옮김
// 막대 from에 쌓여있는 n개의 원판을 막대 tmp를 사용하여 막대 to로 옮긴다
#include <stdio.h>
void hanoi_tower(int n, char from, char tmp, char to)
{
if(n == 1)
{
printf("원판 1을 %c에서 %c로 옮긴다\n", from, to)
}
else
{
hanoi_tower(n-1, from, to, tmp);
printf("원판 %d을 %c에서 %c로 옮긴다\n", n, from, to)
hanoi_tower(n-1, tmp, from, to);
}
}
int main(void)
{
hanoi_tower(4, 'A', 'B', 'C');
return 0;
}
'C Language' 카테고리의 다른 글
C언어 배열에 대해 학습하기 (1) (0) | 2024.06.19 |
---|---|
C언어 static, register, volatile 지정자 개념 (2) | 2024.06.19 |
C언어 전역변수와 지역변수, 매개변수(+가변매개변수)의 개념 (2) | 2024.06.19 |
C언어 사용자 정의 함수 (0) | 2024.06.19 |
C언어 라이브러리의 rand() 함수 (0) | 2024.06.18 |