algorithm - solution to towers of Hanoi problem

Question

how do i solve for running time in the towers of Hanoi problem. I get a recurrence realation like t(n) = 2t(n-1) + 1. After drawing the recursion tree i get at every step values like 1+2+4+8... the height of the tree will be lg(n). how do i calculate the sum of the series? when do i stop?

Answer 1

你在递归树的每一层得到的是 2 的幂。因此，总和是：2^0 + 2^1 + 2^2 + ... + 2^{n-1}。

这是一个几何总和：http ://en.wikipedia.org/wiki/Geometric_progression

让S(n) = 1 + 2 + 4 + ... + 2^{n-1}. 然后：S(n) - 2*S(n) = 1 - 2^n

最后：S(n) = 2^n - 1。

Answer 2

你检查过 http://en.wikipedia.org/wiki/Tower_of_Hanoi吗？你里面什么都有。