The Tower of Hanoi
Problem Solving/Algorithm notes 2011. 8. 28. 15:56
얼마전에 혹성탈출이란 영화를 봤는데.. 한 침팬지가 세개의 기둥을 두고 원반을 옮기는 퍼즐이 나온다..
영화에는 루카스타워라고 나오는데 정식 명칭은 하노이타워 (The Tower of Hanoi) 이다.
퍼즐을 푸는 규칙은 중간과정중에 작은 원반 위에 큰원반을 올려놓을 수 없다..
한쪽 원반을 다른쪽으로 다 옮기기 위해 최소 몇번의 운반이 필요할까..?
n 개의 원반을 옮기는데 2^n - 1 만큼의 운반이 필요하다고 한다..
원반이 몇개 안되면 금방 끝나는 작업이지만..
원반 개수가 하나씩 증가할때마다 총 필요한 운반 횟수는 기하급수적으로 증가한다..
이 작업을 simulation 해보자..
가장 교과서적인 방법으로 recursion 으로 풀 수 있다..
가장 밑에있는 n 번째 원반을 옮기기 위해서는
그 위에 있는 n-1 개를 중간에 옮겨놓고 마지막에 있던 원반을 마지막 기둥으로 옮기고
그리고나서 중간에 있던 n-1 개를 마지막 기둥으로 옮기는 전략이다..
1 /* Hanoi Tower */
2
3 #include <stdio.h>
4 void hanoi(int n, int from, int by, int to)
5 {
6 if (n == 1) {
7 printf("\nMove from %d to %d", from ,to);
8 return ;
9 }
10 hanoi(n-1, from, to, by);
11 printf("\nMove from %d to %d", from ,to);
12 hanoi(n-1, by, from, to);
13 }
14
15 int main()
16 {
17 int i = 0;
18 printf("0 to end..\n");
19 while (1) {
20 printf("\nEnter height of HANOI tower -> ");
21 scanf("%d", &i);
22 if (i <= 0)
23 break;
24 hanoi(i, 1, 2, 3);
25 }
26 return 0;
27 }
2
3 #include <stdio.h>
4 void hanoi(int n, int from, int by, int to)
5 {
6 if (n == 1) {
7 printf("\nMove from %d to %d", from ,to);
8 return ;
9 }
10 hanoi(n-1, from, to, by);
11 printf("\nMove from %d to %d", from ,to);
12 hanoi(n-1, by, from, to);
13 }
14
15 int main()
16 {
17 int i = 0;
18 printf("0 to end..\n");
19 while (1) {
20 printf("\nEnter height of HANOI tower -> ");
21 scanf("%d", &i);
22 if (i <= 0)
23 break;
24 hanoi(i, 1, 2, 3);
25 }
26 return 0;
27 }
'Problem Solving > Algorithm notes' 카테고리의 다른 글
| Euler's phi (Totient function) (0) | 2016.08.15 |
|---|---|
| Inversion Count (0) | 2016.01.31 |
| Gaussian Prime (0) | 2011.04.03 |
| 점과 선분과의 거리 (2) | 2011.01.22 |
| Konig's Theorem (0) | 2010.08.01 |
| Modular Multiplicative Inverse (0) | 2010.06.13 |
| Primality Testing (Miller-Rabin) (0) | 2010.03.23 |
| Modular Exponentiation (Big Mod) (2) | 2010.02.19 |
| KMP (Knuth-Morris-Pratt) Algorithm (0) | 2009.11.15 |
| Bell Number (0) | 2009.07.12 |