문제

하노이탑(towers of Hanoi) 문제

• 3개의 말뚝: A,B,C
• 초기상황: 직경이 다른 n>0개의 원반이 A에 쌓여있음
• 목표: 모든 원반을 A에서 C로 옮김
• 이동순서를 "move from x to y" 형식으로 인쇄

<조건>

• 한번에 한개의 원반만을 이동
• 언제라도 직경이 큰 원반을 작은 원반 위에 놓지 말 것
• 남은 말뚝을 보조 말뚝으로 사용 가능

일반적으로, n개의 원반에 대해 $2^n-1$회의 이동이 필요하다

• n=1인 경우, 1회의 이동
• n=2인 경우, 3회의 이동
• n=3인 경우, 7회의 이동
• n=64인 경우, $2^{64}-1 = 1.844 * 10^{19}$ 회의 이동
  - 1회 이동에 1초 걸린다고 가정하면, 이는 $5.849 *10^8$년!

해결

hanoi는 아래의 매개변수들을 사용하여 재귀적 rHanoi를 구동한다

• n: 이동해야 할 원반의 수
• from: 출발 말뚝
• aux: 보조 말뚝
• to: 목표 말뚝

이중재귀(double recursion)의 한 예

Alg hanoi(n)
1. rHanoi(n,'A','B','C')        {initial call}
2. return


Alg rHanoi(n,from,aux,to)
	input integer n, peg from, aux, to
    output move sequence

1. if(n=1)                                   {원반이 한개밖에 없을 때는 간-단}
		write("move from", from, "to", to)
        return
2. rHanoi(n-1,from,to,aux)                   {첫번째 기둥의 (n-1)개의 원반을 두번째 기둥으로}
3. write("move from",from,"to",to)           {첫번째 기둥의 남은 원반 1개를 세번째로}
4. rHanoi(n-1,aux,from,to)                   {두번째 기둥의 (n-1)개의 원반을 세번쨰로}
5. return

아이디어를 정리하면 다음과 같다

1. n개의 원반이 첫번째 기둥에 있을 때,
   첫번째 기둥에서 (n-1)개의 원반을 두번째 기둥으로 이동
   (세번째 기둥을 보조 기둥으로 사용)

2. 첫번째 기둥의 남은 원반 1개를 세번째 기둥으로 옮김

3. 두번째 기둥에 있는 (n-1)개의 원반을 세번째 기둥으로 옮김
   (첫번째 기둥을 보조 기둥으로 사용)