[C++] 기초 예시 - 7 : 함수 응용 - 하노이 탑 문제

Q. 하노이 탑의 솔루션 프로그램 작성 및 해당 이동 횟수를 출력하는 프로그램을 작성하라.

#include <stdio.h>

// 하노이 탑 함수
int again(int count, int x, char from, char tmp, char to)
{
	if (x == 1)
	{
		printf("%x 원판을 %c에서 %c로 옮긴다.\n", x,from,to);
		count ++;
	}
	else
	{
		count=again(count, x-1, from, to, tmp);
		printf("%x 원판을 %c에서 %c로 옮긴다.\n", x, from, to);
		count ++;
		count=again(count, x-1, tmp, from, to);
	}
	return count;
}

// 메인 함수
int main(void)
{
	int count = 0;
	int num;
	//static int count = 0;
	scanf("%d", &num);
	count = again(count, num, 'A', 'B', 'C');
	printf("움직인 횟수는 %d 입니다.", count);
	return 0;
}

 

추가 팁 : n개의 원판을 모두 다른 기둥으로 옮기는 데에까지 이동되는 횟수는 2^n - 1 이다. (ex. n=2 -> 3 / n=3 -> 7 / n=4 -> 15)