Sunday, September 29, 2013

Tower Of Hanoi Continued...

As I have described in the previous post , Here is the Recursion Tree of the Tower. If you are able to draw the recursion tree of a a problem you will be able to code that too very easily.

This Tree is self explanatory , In this we have Decomposed the 3 Disc problem into 3 steps and recursively solved the same.

So, Now we can write the Program for the same , It does not depend which programming language you use to code , the algorithm will be the same.

Tower Of Hanoi Algorithm Implementation.

int main()
int number_of_discs;
printf("Enter the Number of discs:");

void Towers(int N,char From, char To, char Via)
printf("Moving %c to %c\n ", From , To);
  Towers(N-1,From,Via,To);                     //(N-1,A,C,B)
  printf("Moving %c to %c\n" , From , To);    //(1,A,B,C)
  Towers(N-1,Via, To,From);                   //(N-1,C,B,A)


Tower Of Hanoi

Today I will try to explain the Tower Of Hanoi Algorithm in Full detail. I don’t want you to just mug up the 3 lines of code and pass an exam . I want you to learn How we reach to the solution. How we decompose the problem and recompose it again to get the solution which is very important to solve a problem like this. You will also learn how to apply the recursion to get the desired solution.

Tower Of Hanoi:- The problem description is as follows:
We have Three pillars/pegs and N discs of different size on One pillar/peg such that They are in Incresing order of size from top to bottom.

What we have to do?
We have to move the Discs from  Source Peg to  Destination Peg  keeping the following constraints in Mind.

1.)We can take one peg out at a time.
2.)We can’t place small disc below the larger one during the task.
3.)We can only use one more pillar for help to complete the solution.



We have described the problem the solution above. Now we have to think how to solve the same.

Let Us decompose the problem and try to solve it 
Let us Assume that we have only one Disc On peg A and We have to move the same to the Peg B.The solution is obvious , We will just pick the disc and put it on B and the problem is solved , let us see the same in Picture.
Solution of 1 disc Problem

(1,A,B,C) denotes that we have moved 1 disc from A to B using C.

SO, (1,A,B,C) solves the One Disc Problem.

Now , Let Us Assume that We have Two Disc and We have to move both disc from A to B. Let us see the solution of Two Disc Problem in Picture.

Solution Of 2 Discs problem

So, To solve 2 Disc problem we have followed the following 3 steps:
1.) (1,A,C,B)
2.) (1,A,B,C)
3.) (1,C,B,A)

Now Let us Take the 3 Disc Problem, Now we have to move the 3 discs from A to B.

Solution of 3 Disc Problem:

Now if We see The solution of 2 Disc Problem(2,A,B,C) is :
1) (1,A,C,B)  
2.) (1,A,B,C)
3.) 1(C,B,A)
So,The First 3 steps:
1.) (1,A,B,C)
2.) (1,A,C,B)
3.) (1,B,C,A)
 of the 3 disc problem is the solution of Problem (2,A,C,B)

And,The 4th Step:
4.) (1,A,B,C)
is the solution of Problem(1,A,B,C)

And the last 3 steps:
5.) (1,C,A,B)
6.) (1,C,B,A)
7.) (1,A,B,C)
is the solution of Problem(2,C,B,A)

So the solution of 3 disc problem(3,A,B,C) can be written as:
1.) (2,A,C,B)
2.) (1,A,B,C)
3.) (2,C,B,A).

and Similarly the solution of N disc problem(n,A,B,C) can be written as:
1.) (n-1,A,C,B)
2.) (1,A,B,C)
3.) (n-1,C,B,A).

So, In this way we have decomposed the problem into three parts to solve it.
Now let us say 

So the Tower of hanoid problem is (N,From,To,Via) which can be solved in three steps:

1.) (n-1,From,Via,To) -- first solve the problem of moving n-1 discs From to Via .
2.) (1,From,To,Via) -- Then solve the problem of moving 1 disc From to To.
3.) (n-1,Via,To,From) -- Then Solve the problem of moving n-1 disc from Via to To back.

Monday, September 23, 2013

Storage Classes in C

Today I am going to explain the most important concept of C language.
If you have gone through any interview , It is quite possible that you came across the questions like:

  • What do you mean by storage class in C?
  • How many storage classes are there in C?
  • Explain the different storage classes in C ?

So, I will be explaining the storage class concept in full detail with all its types.

Let us start by understanding What it means by a Storage class?

We know that Every variable posses the following property:

  • Lifetime: Lifetime of a variable defines "till what time we can access a particular variable". 
  • Scope: Scope of a variable defined "Where we can access a variable in our hundred and thousands lines of code".
  • Default value: what is the default value of the variable when it is only declared that is programmer has not assigned any value to it explicitly.
  • Storage place: Storage of a variable defined Where the variable is getting the memory to be accessed.

All the above properties are tied to the variables , and the specifiers consisting of these properties specify the storage class of a variable...

So, We can say that Storage class is an attribute/specifier which defines Lifetime,scope,storage and default value of a variable.

For defining different lifetime,scope,storage and default value the storage classes are categorized into 4 categories:

So, just by saying that this is an auto variable, a static variable , a extern variable or a register variable we are
telling about all the four properties of a variable.

Explanation of all the classes coming soon one by one.