This question is preferred to Data Structure and Algorithm. Program should be in MS Visual Studio code.

a)Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

Only one disk can be moved at a time.

Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.

No disk may be placed on top of a smaller disk.

The game can be recursively described by the given algorithm, where output of the algorithm is the sequence of moves required to solve Tower of Hanoi for n number of disks.

Sample input:

void Move(int n, char Beg, char Aux, char End)

{

if(n==1)//base case:

cout<

else

//general case:

{

Move(n-1, Beg, End, Aux);//first move n-1 disks from Beg to Aux using End

Move(1, Beg, Aux, End);//then move remaining 1 disk from Beg to End

Move(n-1, Aux, Beg, End);//then move the remaining n-1 disks from Aux to End

}

}

Using the given definition, find the sequence of moves generated by the algorithm to solve Tower of Hanoi for n=4 (i.e. 4 disks). Show all intermediate steps involved in solving the problem.