Problem on TOH

Question

We solve TOH problem recursively breaking the task in three sections, which of the following recurrence will accord well with the approach , that is shows correct order of work done on each recursive step

A)  T(n)=T(n-1)+1+T(n-1)

B) T(n)=T(n-1)+T(n-1)+1

C) T(n)=1+T(n-1)+T(n-1)

D) T(n)=T(n-1)+T(n-1)+2

Answer 1

Tower of Hanoi function works as:

TOH(n, x,y,z){

if(n>=1)

{

1.TOH(n, x,z,y) .//....(T(n-1))

2.move x->y  .//.....(1)

3.TOH(n,z,y,x)  //.....(T(n-1))

} }

thus TOH function is recursively called and step 2 is just move which takes O(1) time so as it is asked order of work, option 1 is correct.

Comments

why ordering of 1 matters here?

Answer 2

As we know disks are to be arranged using 3 tower or peg.

All disks are on 1st peg in such a way that largest at the bottom and then decreasing in size towards top.

Aim is to move n disks from 1 to 3rd peg using the 2nd.

n-1 disks are moved to 2nd stand.

Then  the largest disk is moved to 3rd stand. (1 move)

Then recursively the n-1 disks are moved to the 3rd stand.

So T(n) =T(n-1)+1+T(n-1)

Comments

not getting

then why b) or c) not correct?

---

Because in b or c the order of work done is not correct. The question asks the correct working order. So according to tower of Hanoi rules only a has correct order.

---

but u told 2nd also using n-1 peg??

---

Suppose 3 disks (a, b, c) and the stands are 1,2,3

       ''''''             a

    ''''''''''''''''          b

'''''''''''''''''''''''''''''''''   c

They can be on any one of the 3 stands. Say stand 1.

Now aim is to move the 3 disks in any of the other stand using the left.

Say if we want to move from 1 to 2 so we use the 3 stand. Or if we want to move from 1to 3 we use the 2stand.

Basically no significance of numbered stands. The recursive relation represents the no of movements required to solve the problem. Stepwise movements would be moving the top 2 disks a b to  stand 2.(recursively)

Now we can move  c(largest disk)  to stand 3. Now it's fixed there.

Then the 2 disks a, b to 3 (recursively)

Hope it helps:)

---

I am still confused

why ordering of 1 matters here? :(

Answer 3

Is Option A correct ?

Comments

yes, explain