[재귀] 하노이 타워

함수의 재귀적 호출을 이용하여 c언어로 하노이 타워를 구현

 

하노이 탑 규칙

1. 가장 위의 원판만 이동 가능함

2. 작은 원판 위로 큰 원판이 올라갈 수 없음

3. 최소 이동횟수로 이동해야함

4. 한번에 하나의 원판만 이동해야 함

 

 

 

 

제일 밑의 원판을 옮기기 위해 위의 원판들을 B로 옮긴다 (A->B)

-> hanoi(n-1,a,c,b);

 

제일 밑의 원판을 A에서 C로 옮겨야 한다. (A->C)

-> printf("%d 원반이 %c -> %c\n",n,a,c);

 

제일 밑의 원판을 C로 옮겼으므로 B에 있던 원판들을 다시 A로 옮긴다 (B->C)/p>

-> hanoi(n-1,b,a,c);

 

// 하노이 타워  
void hanoi(int n, char a, char b, char c)
{      
	if(n==0)
	{
		return;
	}
	
	hanoi(n-1,a,c,b);
	printf("%d 원반이 %c -> %c\n",n,a,c);
	hanoi(n-1,b,a,c);  
}  

int main()
{     
	int n;
	scanf("%d",&n);
    
	hanoi(n,'A','B','C');
}