1
$\begingroup$

What the recursive algorithm for moving $n$ disks says, is:

  1. If $n > 1$, move $n-1$ discs from A to B.
  2. Move the $n$th disk from A to C.
  3. If $n > 1$, move $n-1$ discs from B to C.

Let $T_n$ be the number of moves for moving n disks.

We have $ T_n=2T_{n-1}+1 , T_1=1 $, so $T_n=2^n-1, n \geq 1 $

Is it correct to say that for every algorithm solving the Hanoi Towers problem, it is true that $$ T_n=2T_{n-1}+c $$ So we would need to know $c$ (number of moves for moving the last disk from A to C) and some other $T_i$, in order to calculate $T_ n$ for every $n$.

Thank you in advance

$\endgroup$
  • 2
    $\begingroup$ It's hard to make a statement about every algorithm for a problem: what about the algorithm that acts exactly like yours, except that if $n=69105$, it first moves a single disk back and forth seventy thousand times? Now $T_{69105}$ isn't perfectly predictable from $T_{69104}$. $\endgroup$ – Draconis Dec 5 '19 at 16:46
  • $\begingroup$ Is this the 3-pegs variant? If so, your approach is the one based on divide-and-conquer which is known to be optimal, $\endgroup$ – Carlos Linares López Dec 6 '19 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.