A) Write a divide-and-conquer algorithm for the Towers of Hanoie problem (Pseudo

Question

A) Write a divide-and-conquer algorithm for the Towers of Hanoie problem (Pseudo code)
B) Show for your algorithm that S(n)=(2^n)-1
   (Here S(n) denotes the number of steps(moves), given an input of n disks) A) Write a divide-and-conquer algorithm for the Towers of Hanoie problem (Pseudo code)
B) Show for your algorithm that S(n)=(2^n)-1
   (Here S(n) denotes the number of steps(moves), given an input of n disks)
B) Show for your algorithm that S(n)=(2^n)-1
   (Here S(n) denotes the number of steps(moves), given an input of n disks)

Explanation / Answer

To solve tower of Hanoi with N discs

we can think of like that we have already moved N-1 discs to 3rd tower in order(smallest at top) and our goal is to move Nth disc to second tower and then again N-1 discs on 3rd tower to 2 nd tower i.e above Nth disc.

This can be formulated as

T(N)=T(N-1)+1+T(N-1)

= 2*T(N-1)+1

=2(2*T(N-2)+1)+1

=4T(N-2)+3

=8T(N-3)+5

...........

........

2N-1

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.