Jan 172013
 

We discussed problem of Tower of Hanoi earlier and written a recursive function to solve the problem, Recursive functions take lot of extra memory (New activation record for each call on the stack) (A detailed analysis of recursion is done in this post of mine).

Todays question is to write a Non-recursive function to solve problem of Tower Of Hanoi.

The function should not take more than O(n) time (n = number of Moves actually required to solve the problem) and O(1) extra space.

The signature of the function will be

/* The three char represents the characters representing three rods 
 * and n is the number of discs (initially in s) 
 */
 void towerOfHanoi(char s, char d, char e, unsigned int n)

Continue reading »

Jan 162013
 

Tower of Hanoi is a Mathematical Game. There are 3 pegs (Rods) and number of discs, each of different size, which can be inserted into the rods. All discs are initially inserted into one rod in increasing order (smallest at the top and largest disc at the bottom).

You have to move all the discs from source rod to Destination rod, with below 2 restrictions:

  1. Only one disc can be moved at a time.
  2. You cannot place a larger disc on the top of a smaller disc ever.

For example: If the Pegs are named as S, D & E (Source, Destination & Extra) and there are 4 discs, the initial state will be

And final state will be:

Write a function that accept the names of three rods (S, D & E) and the number of discs, and print the movement of discs between the rods such that all the rods are moved from S to D.

The signature of the function will be

/* The three char represents the characters representing three rods 
 * and n is the number of discs (initially in s) 
 */
 void towerOfHanoi(char s, char d, char e, int n)

Continue reading »