얼마전에 혹성탈출이란 영화를 봤는데.. 한 침팬지가 세개의 기둥을 두고 원반을 옮기는 퍼즐이 나온다..
영화에는 루카스타워라고 나오는데 정식 명칭은 하노이타워 (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 }




'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

to Top