Question

C++

1. What is the minimum number of steps if there are 1, 2, 3, 4, or more disks? Try and solve the puzzle and fill in the table.

1	1
2	3
3	7
4	15
5	?
6	?
7	?
8	?

2. Write an explicit formula for the minimum number of steps required for the puzzle? Use H(n) = ? where n is the number of disks

3. What would be the best ADT to use for the posts in the puzzle? Why is that data structure best?

4. What would be the base case (n = 1) of this problem if a recursive solution was employed? Use three of the ADTs from the previous question for storage. The three posts are labeled A, B, C. Post A is the the starting post and Post C is the ending post. Write the answer in in pseudo code.

5. What are the rest of the cases given the base case?

if (n == 1)

            disk = A.top()

            A.pop()

            C.push(disk)

please refer to concept of "Tower of Hanoi"

Answer 1

1. What is the minimum number of steps if there are 1, 2, 3, 4, or more disks? Try and solve the puzzle and fill in the table.

1	1
2	3
3	7
4	15
5	31
6	63
7	127
8	255

2. Write an explicit formula for the minimum number of steps required for the puzzle? Use H(n) = ? where n is the number of disks

We can derive a common pattern using values in the above table;

for number of disks (n=1), we have number of steps: 1 (2^1-1)

for number of disks (n=2), we have number of steps: 3 (2^2-1)

for number of disks (n=3), we have number of steps: 7 (2^3-1)

for number of disks (n=4), we have number of steps: 15 (2^4-1)

for number of disks (n=5), we have number of steps: 31 (2^5-1)

for number of disks (n=6), we have number of steps: 63 (2^6-1)

for number of disks (n=7), we have number of steps: 127 (2^7-1)

for number of disks (n=8), we have number of steps: 255 (2^8-1)

Thus,formula: H(n)= 2^n - 1; where n=number of disks

3. What would be the best ADT to use for the posts in the puzzle? Why is that data structure best?

Best data structure for the posts in this puzzle is a stack. Stack follows convention of first in last out. In this puzzle, we have three rings arranged in ascending order from top to bottom residing on a tower(stack) at any given point of time. The largest ring is placed first on the post and removed last following the convention of stack. Similarly, the smallest ring is placed last on top of other rings and removed first before any other ring thus, following he convention of a stack. Thus, stack is the best data structure.

4. What would be the base case (n = 1) of this problem if a recursive solution was employed? Use three of the ADTs from the previous question for storage. The three posts are labeled A, B, C. Post A is the the starting post and Post C is the ending post. Write the answer in in pseudo code.

If we follow recursive appeoach, the best case scenario would when our problem is reduced to only 1 disk out of n disks. This means we need to transfer only one disk from our source to destination. Using the formula we derived above, this can be achieved in 1 step only (2^1-1). This would be the case when we would want to move our largest disk whoch is being kept at the bottom of the source to our destination. If we wish to track the movement of every disk form one tower to another we can write the best case as follows:

void towerOfHanoi(int n, char source, char auxillary, char destination){

if ( n == 1){

disk=source.top;

source.pop();

destination.push(disk);

cout<<"Move disk 1 from "<<source<<" to "<<destination;

         return;

}

}

5. What are the rest of the cases given the base case?

Rest of the function includes recursive calls to the function towerOfHanoi with no of disks equals one less than the given number as 1 dis is already shifted to its correct place.

towerOfHamoi(n-1,source,destination,auxillary);

cout<<"Move disk 1 from "<<source<<" to "<<destination;

towerOfHanoi(n-1,auxillary,source,destination);

In this algorithm we are calling the funtion towerOfHanoi recursively. Base case if achieved when we have already one disk left to be moved. This is shown above. For rest of the n-1 disks, we will first move them from source to destination using auxillary rod. Once n-1 disks are moved to auxillary rod, we can easily move the last remaining disk in source to destination. We will then recursively repeat our approach considering there are n-1 disks.