Non-recursive solution to tower of hanoi

Jan 172013
 
 Algorithms, Articles Tags:,  4 Responses »

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 »

Tower of Hanoi code

Jan 162013
 
 Algorithms, Articles Tags: 7 Responses »

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 »

Lambda functions and expressions in C++11

Jun 272012
 
 Articles, C++ Tags:,  No Responses »

In my opinion, the single biggest addition to C++11 is the Lambda function and expressions (for more features in C++ click here…).

Look at the case when you are calling std::sort function, you have to specify the comparator function and then pass that function as an argument to std::sort. In such situations, you may want to specify the function at the point of calling std::sort inline. Because that function (Comparator Function) has not other use but to be called to this API. This function may not even have a name , we don’t really care..  Continue reading »

C++11 feature – automatic type detection and decltype

Jun 212012
 
 Articles, C++, Featured Tags:,  4 Responses »

C++11 is the latest version of C++ language originally designed by Stroustrup. I read an interview of him where he said that the latest standard (C++11 or C++0x) feels like a new language.

I will be publishing the new features added to the core language and to the STL in following articles in next few days. The first change (in the core language) which I want to focus today is the introduction of automatic type detection. Continue reading »

 Older Entries