Computer Science, asked by rashminegi217, 1 year ago

X solves the tower of Hanoi problem, first with n disks in time t1 and then with n+2 disks in time t2. Assuming he takes same amount of time for each disk move and solves the problem in least steps possible, the relation between t1 and t2 is:

A. t2=t1+2 B. t2=2t1+2 C. t2=3t1+2 D. t2=4t1+3

Answers

Answered by TPS
0
Minimum number of moves required in solving a Tower of Honoi problem with n disks is 2^n-1

If he takes same amount of time for each disk move and solves the problem in least steps possible, 
t_1=2^n-1 where k is some constant. and 
t_2=2^{n+2}-1

Relation between the times are:
t_2=2^{n+2}-1\\ \Rightarrow t_2=2^n \times 2^2-1\\ \Rightarrow t_2=4 \times 2^n-1\\ \Rightarrow t_2=4 \times 2^n-4+3\\ \Rightarrow t_2=4 \times (2^n-1)+3\\ \Rightarrow t_2=4 \times t_1+3\\ \Rightarrow t_2=4t_1+3

Correct answer is D.
Similar questions