C 언어 구현 귀속 고전 한노타 초상해

문제 설명

한노타 문제는 고전적인 문제다.하노이 타워(Hanoi Tower)는 하노이 타워라고도 하는데 인도의 오래된 전설에서 기원한다.대범천이 세계를 창조할 때 세 개의 금강석 기둥을 만들었는데 한 기둥에 아래에서 위로 크고 작은 순서에 따라 64개의 황금 원반이 쌓여 있었다.대범천은 브라만에게 원반을 아래에서부터 크기 순서대로 다른 기둥에 다시 놓으라고 명령했다.또한 언제든지 작은 원반에서는 원반을 확대할 수 없고 세 기둥 사이에서 한 번에 한 개의 원반만 이동할 수 있다고 규정하고 있다.어떻게 조작해야 하냐고요?

문제 풀이 사고방식

먼저 문제를 분석하면 우리는 한 기둥의 원반을 다른 기둥으로 이동하려면 2^64를 이동해야 한다는 것을 안다.그러나 한 걸음 한 걸음 어떻게 움직일지 인위적으로 결정하기 어렵기 때문에 우리는 문제를 간소화해야 한다

일

64개의 원반을 기둥 1에서 기둥 3으로 이동하려면 위의 63개의 원반을 먼저 기둥 2로 이동한 다음에 맨 아래 원반을 기둥 1에서 기둥 3으로 이동해야 한다

이

위의 63개의 원반을 기둥 3으로 이동하려면 위의 62개의 원반을 먼저 기둥 2로 이동한 다음에 꼴찌의 두 번째 원반을 기둥 1에서 기둥 3으로 이동해야 한다
우리는 위의 절차를 반복해서 층층이 내려가기만 하면 된다

삼

상기 과정을 두 단계로 나눈다. 첫 번째 단계: n-1개의 접시를 한 기둥에서 다른 기둥으로 이동(n>1) 두 번째 단계: 한 접시가 한 기둥에서 다른 기둥으로 이동하는 것을 말한다.

프로그램 작성

#include
#include
// 

void move(char x, char y)
{   // 
	printf("%c-->%c
", x, y);
}

void hanoi(int n, char a, char b, char c)
{
	void move(char x, char y);
	if (n == 1)                         //    a》》》c
	{
		move(a, c);
	}
	else
	{
		hanoi(n - 1, a, c, b);     //   a b   c  
		move(a, c);                //   a》》》》c
		hanoi(n - 1, b, a, c);     // b   a c 
	}
}
int main()
{
	int n = 0;
	scanf_s("%d", &n);
	hanoi(n, 'a', 'b', 'c');
	system("pause");
	return 0;
}

오리지널