C 로 구현한 하노이의 탑(Tower of Hanoi)

소개

함수의 재귀호출을 이용하는 유명한 예제인 `하노이의 탑` 을 C언어를 이용해 구현해 보았다. 프로그램 시작과 동시에 disc 의 개수를 입력받도록 하였으며 매번 disc 를 옮길때마다 출력해주도록 코딩하였다. 매번 step 마다 남은 step을 한 번만 보여줄 것인지, 모두 출력할 것인지를 묻도록 하였다. disc 의 개수가 몇개가 되어도 정확하게 결과를 보여줌을 확인하였다.

목차

1. 개요
2. 프로그램 동작순서
3. 코드첨부

본문내용

1. 개요
C언어를 배울 때 재귀함수에 대해 배운다. 그 때 배우는 대표적인 예제가 하노이의 탑이다. 나는 메모리 동적할당을 이용하여 사용자가 원하는 만큼의 disc 의 개수를 입력받고 disc 들이 매 스텝마다 옮겨가는 과정을 모두 출력하여 보여주었다.

2. 프로그램 동작 순서
main 함수에서 disc 의 개수를 입력받고 메모리 동적할당을 이용하여 각 bar 마다 disc 개수만큼의 메모리를 만들어준다. Initialization을 해준 후에, Hanoi 함수를 호출한다. Hanoi 함수를 들여다 보면 재귀적 호출을 함을 알 수 있는데, bar 에 disc 가 하나 남았을 때는 그 디스크를 목표 bar 에 옮기는 Move 함수가 들어있다. 그 아래를 보면 맨 밑의 disc를 제외한 나머지 전부를 여분의 bar 에 옮긴후 맨 밑의 disc를 목적지 bar 로 옮기고, 다시 나머지 모든 disc를 목적지 bar에 옮기는 작업을 확인할 수 있다.

3. 프로그램 코드

#include<stdio.h>
#include<stdlib.h>

/*
global variables.
*/
int turn;
int* bar[3];
int plate_num;
int print_mode;

/*
print each step.

참고자료

· 없음