KPGCET-CSE-2019-30

Question

The tower of Hanoi puzzle with $n (n > 1)$ different dimensional disks stacked on peg A in the decreasing order of their size with largest dimensional disk at the bottom and smallest dimensional disk at the top. The disks are to be transferred from peg A to Peg B using peg C with one disk at a time such that under no circumstance larger disk should be stacked on smaller disk. The total number of disk transfers is given by 

• A. $2T(n − 1) +2$
• B. $2T(n-1) + 1$
• C. $T(n-1) +T(n − 2)$
• D. $2T(n)$

Comments

2T(n-1)+1

Answer 1

No of steps i.e. T(n) to move all the disks from A to C:

1. Move all the disks above largest disk to B i.e. T(n-1) steps
2. Then move the only disk from A to C i.e. 1 step .
3. Then move remaining (n-1) disks from B to C i.e. T(n-1) steps

Adding all, T(n)=2T(n-1)+1 .

Hence B is the right answer.