재귀알고리즘(하노이타워)

하노이 타워를 재귀함수를 통해 구현 해보자.

 

 

 

 

하노이타워의 조건은 다음과 같다.

 

1. 원반은 한번에 하나씩만 옮길 수 있다.

 

2. 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안된다.

 

위 그림 ABC 원반을 3번 기둥으로 옮기기 위해서는 다음과 같은 패턴이 들어간다.

 

C를 옮기기 위해서는 B를 옮겨야 한다.

B를 옮기기 위해서는 A를 옮겨야 한다.

A는 옮기면 된다.

 

~를 옮겨야 한다. 

 

여기서 원반 갯수가 늘어나도 ~~를 옮겨야 한다는 건 달라지지 않는다.

 

좀 더 보강해서 5개의 원반이 있다고 하자 (A, B, C, D, E)

 

ABCDE를 3번 기둥에 옮기기 위해서는 (A,B,C,D)를 2번기둥에 옮겨야 한다.

E를 옮긴 후

ABCD를 3번 기둥에 옮긴다.

 

ABCD를 3번 기둥에 옮기기 위해서는 (A,B,C)를 2번기둥에 옮겨야 한다.

D를 옮긴 후

ABC를 3번 기둥에 옮긴다.

 

ABC를 3번 기둥에 옮기기 위해서는 (A,B)를 2번기둥에 옮겨야 한다.

C를 옮긴 후

AB를 3번 기둥에 옮긴다.

 

AB를 3번 기둥에 옮기기 위해서는 (A)를 2번기둥에 옮겨야 한다.

B를 옮긴 후

A는 3번 기둥에 옮긴다.

 

반복되는 재귀 식은 다음과 같다.

 

n를 3번 기둥에 옮기기 위해서는 n-1를 2번기둥에 옮겨야 한다. 

n를 옮긴 후

2번기둥에 있는 n-1를 1번기둥을 거쳐 3번 기둥에 옮긴다.

 

위 전제를 코드로 바꿔보자 

 

//(Hanoi_Tower(옮길 원반 수, 경유지, 목적지)

 

E를 3번 기둥에 옮기기 위해 (A,B,C,D)를 1번 기둥을 거쳐 2번기둥에 옮겨야 한다.

-> Hanoi_Tower(n, 2번기둥, 3번기둥) 

E를 옮긴 후

-> Move(E, 3번기둥)

2번기둥에 있는 n-1를 1번기둥을 거쳐 3번 기둥에 옮긴다.

-> Hanoi_Tower(ABCD, 3번기둥, 2번기둥)

A는 3번 기둥에 옮긴다.

 -> if(옮길 갯수가 1이면)

 

반복 되는 함수는 

Hanoi_Tower()

Move()

Hanoi_Tower()

 

끝

 

우선 각 기둥들을 다음과 같이 정의한다.

 

/*
1번 2번 3번 기둥 정의
*/
#define LEN 5

int Static_1[LEN] =
{ 0, };

int Static_2[LEN] =
{ 0, };

int Static_3[LEN] =
{ 0, };

 

Hanoi_Tower와 Move 함수를 정의한다.

 

void Move(int len, int *origin, int *dest)
{
	dest[len - 1] = origin[len - 1];
	origin[len - 1] = 0x0;
}

void Hanoi_Tower(int len, int *origin, int *trans, int *dest)
{
	if (len == 1)  //옮길 개수가 1이면
	{
		Move(len, origin, dest); //1번기둥에서 3번으로 옮긴다.
	}
	else
	{
		Hanoi_Tower(len - 1, origin, dest, trans);  //n-1개 원반을 2번기둥을 거쳐 3번기둥에 옮긴다.
		Move(len, origin, dest); //n번째 원반을 3번 기둥에 옮긴 후
		Hanoi_Tower(len - 1, trans, origin, dest); //n-1개 원반을 1번기둥을 거쳐 3번기둥에 옮긴다.
	}

}

 

Main 에서 기둥에 원반을 채운 다음 실행 시킨다.

 

int main(void)
{
	int i = 0;

	for (i = LEN; i >= 0; i--)
	{
		Static_1[i] = i + 1;

	}

	Hanoi_Tower(LEN, Static_1, Static_2, Static_3);

	return 0;

}

 

실행 화면

 

함수 실행 전 기둥 1에 원반(1,2,3,4,5) 확인

 

함수 실행 후 기둥 3에 원반 (1,2,3,4,5) 확인