알고리즘 기초 (Foundation of Algorithms) 5판, 2장 연습문제(1)

소개글

• 2장 연습문제

목차

없음

본문내용

17. 하노이탑(Towers of Hanoi) 문제를 푸는 분할정복 알고리즘을 작성하시오. 하노이탑은 말뚝 3개와 크기가 모두 다른 구멍난 디스크 n개로 구성되어 있다. 문제는 한 말뚝에 쌓여있는 n개의 디스크를 모두 지정한 말뚝으로 옮기는 것이다. 문제를 풀 때 다음 규칙을 반드시 준수해야 한다.
(1) 세 개의 말뚝 이외에는 디스크를 놓을 수 없다.
(2) 한 번에 하나의 디스크만 옮길 수 있고, 말뚝의 맨 위에 있는 디스크만 옮길 수 있다.
(3) 큰 디스크를 작은 디스크 위에 올려놓을 수 없다.
(a) 작성한 알고리즘의 복잡도가 S(n)`=`2 ^{n} -1임을 증명하시오(여기서 n이 디스크의 개수이면 S(n)은 옮기는 횟수이다).
(b) 아무리 알고리즘을 다르게 만들어도 최소한 (a)에서 주어진 횟수만큼은 옮겨야 함을 증명하시오.

void hanoi(int n, index a, index b, index c) {
if (n <= 1 )
원판 n을 a에서 c로 옮긴다;
else {
hanoi(n-1, b, a, c);
}
}

(a)
S(n) = S(n-1) + 1 + S(n-1) 이다.
S(1) = 1 이다.
위의 식에서 S(n) = 2 * S(n-1) + 1 이 되고,
S(n) = 2S(n-1) + 1
= 2(2T(n-2) + 1) + 1
= 2(2(T(n-3) + 1) + 1) + 1
...
=
=> S(n) =
=> S(n) = 이 된다.
(b)
n = 1 일 때 1번 움직이므로 이 성립한다.
n = k 일 때 번 이하로 이동시킬 수 없다고 가정하고
n = k+1 일 때 번 이하로 이동시킬 수 없는지 확인한다.
k+1개 원반이 있을 경우 맨 밑의 원반 위의 k개를 반드시 옮겨야 한다.

참고 자료

없음