algorithm - 分析算法-递归方程(汉诺塔)

Question

我在维基百科上看到了这个求解汉诺塔的递归算法。谁能给我解释一下我是如何得到这个算法的递归方程的？

Recursive solution

• label the pegs A, B, C — these labels may move at different steps
• let n be the total number of discs
• number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

• move n−1 discs from A to B. This leaves disc n alone on peg A
• move disc n from A to C
• move n−1 discs from B to C so they sit on disc n

The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.

Answer 1

前三步可以在线性时间内完成，后三步是递归的部分，那么，明文写的就简单写递归的形式:

T(n,A,C) = T(n-1,A,B) + 1 + T(n-1,B,C).

另一方面，因为标签不重要，T(n,A,B) = T(n,B,C)=T(n,A,C)=...，我们可以去掉标签，所以等式将是？