COMP1927 - Tower of Hanoi

300px-Tower_of_Hanoi_4.gif

The object of the game is to move all the disks onto a different rod, whilst keeping each rod in descending order of height.

There's an intuitive iterative method; simply loop through, alternating between moving the smallest and next-smallest disk (right if even, and left if odd), to make the legal move, until it's sorted.

As well as a very elegant recursive way of doing this:

Code

int hanoi (int numDisks, int from, int to, int using) {
 
   int numMoves = 0;
 
   if (numDisks == 1) { 
      printf ("Move a disk from pin %d to pin %d\n", from, to);
      numMoves = 1;
   } else {
      numMoves += hanoi (numDisks-1, from, using, to);  
      numMoves += hanoi (1, from, to, using);
      numMoves += hanoi (numDisks-1, using, to, from);
   }
 
   return numMoves;
 
}

Complexity?action=AttachFile&do=get&target=hanoi.png

Complexity

Hanoi is O(2n). Proof by induction.