recategorized by
296 views
0 votes
0 votes

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 

  1. $2T(n − 1) +2$
  2. $2T(n-1) + 1$
  3. $T(n-1) +T(n − 2)$
  4. $2T(n)$
recategorized by

1 Answer

0 votes
0 votes

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.

Related questions

0 votes
0 votes
1 answer
1
gatecse asked Aug 4, 2019
296 views
In relational DBMS, the closure of functional dependencies facilitates To determine the candidate key To determine the foreign key To determine the dependency of an attr...
0 votes
0 votes
1 answer
2
gatecse asked Aug 4, 2019
326 views
The schema for the entire database is designed using Data definitional languageStructured query languageData manipulation language Schema structure language
0 votes
0 votes
0 answers
3
gatecse asked Aug 4, 2019
232 views
The Software Development Life Cycle (SDLC) is used in allProcess modelsDesign modelsProgramming modelsNone of these
0 votes
0 votes
0 answers
4
gatecse asked Aug 4, 2019
247 views
The complexity of algorithms is comparatively more accurate in the use ofAsymptotic analysisAmortized analysisBoth of theseNot dependent on the nature of analysis.