얼마전에 혹성탈출이란 영화를 봤는데.. 한 침팬지가 세개의 기둥을 두고 원반을 옮기는 퍼즐이 나온다..
영화에는 루카스타워라고 나오는데 정식 명칭은 하노이타워 (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
The Tower of Hanoi  (0) 2011.08.28
Gaussian Prime  (0) 2011.04.03
Floating point number 연산시 Epsilon을 더하는(또는 빼는) 이유..  (2) 2011.03.02
Linear Diophantine Equation  (0) 2011.01.25
점과 선분과의 거리  (2) 2011.01.22
Articulation Points  (0) 2010.11.21
Konig's Theorem  (0) 2010.08.01
Modular Multiplicative Inverse  (0) 2010.06.13
Primality Testing (Miller-Rabin)  (0) 2010.03.23

Leave a Comment


to Top