recategorized by
3,122 views
5 votes
5 votes
______ is the number of moves of the smallest disc in Tower of Hanoi implementation where the tower consisting of 17 discs (numbered from 0 to 16)

Answer given:  $2^{16}$ = 65536
Please explain
recategorized by

5 Answers

Best answer
7 votes
7 votes

this problem is  INCOMPLETE   as it does not specify the number of rods used for this instance of TOH.

So, the best we can do is to take the first version this problem which is from the temple of Kashi Vishwanath, which contains 3 rods.

$n$ represents the total number of disks and $S_n$ denotes the sequence of moving disks, each number represent the numbered $\text{n}^{\text{th}}$ disk that is moved as per the sequence. So,

\[\begin{array}{|c|ccccccccccccccc|} \hline n & S_n & & & & & & & & & & & & & & \\\hline 1 & 1 & & & & & & & & & & & & & & \\ 2 & 1 & 2 & 1 & & & & & & & & & & & & \\ 3 & 1 & 2 & 1 & 3 & 1 & 2 & 1 & & & & & & & & \\ 4 & 1 & 2 & 1 & 3 & 1 & 2 & 1 & 4 & 1 & 2 & 1 & 3 & 1 & 2 & 1 \\\hline \end{array}\]

from which we observe that the smallest disk marked by the digit $1$ makes $2^{(n-1)}$ moves in each case.

Hence, answer = $2^{16}$ as we have 17 disks in this case.

selected by
4 votes
4 votes

for  1 disc one move 

for 2 disc 2 move 

for 3 disc 4 move 

like this for n it will we 2n-1 time smallest disc will be move.

2 votes
2 votes

if we follow this algo:

TOH(n,L,M,R)
{
                if(n==0) return;
                else 
                {
                          TOH(n-1 , L , R , M)
                          Move(L-R) 
                          TOH(n-1 , M , L, R)
                 }
}
 Using this algo Function call  TOH(0) = 0 TOH(1) = 3  TOH(3) = 7  
                         there will be n+1 level of tree
                         so total function TOH(n)= $2^{n+1} -1$
  Number of moves TOH(0) = 0 TOH(1) = 1 TOH(2) = 3 TOH(3) = 7 
                              
                          so total moves   TOH(n) = $2^{n} -1$
so total moves will be $2^{17} -1$   
                              = 131071

DIcs 0(smaller disc moves) TOH(1) = 1  TOH(2) = 2 TOH(3) = 4  TOH(4) = 8
                                        in general $2^{n-1}$ 
                                        $2^{17-1} = 65536

1 votes
1 votes

The formula is 2n -1.. i.e. 217 -1

check this out for help.. 

Related questions

11 votes
11 votes
1 answer
2
dd asked Oct 31, 2016
2,828 views
In the tower of Hanoi $x , y , z$ are the positions and we are to move 10 disks from $x$ to $y$. What are the $128$th and $768$th moves ?(A) $x\rightarrow y$ and $x\right...
0 votes
0 votes
0 answers
4
iarnav asked May 27, 2017
635 views
how to Write a program in C which implements tower of Hanoi using recursion? and please explain lines of code if possible.It 'll be a great help.