решение башни Ханоя проблемы

Question

как решить проблему времени в Ханое. Я получаю рекуррентную реализацию, такую ​​как t (n) = 2t (n-1) + 1. После рисования дерева рекурсии я получаю на каждом шаге такие значения, как 1 + 2 + 4 + 8 ... высота дерева будет (п). Как рассчитать сумму ряда? когда я остановлюсь?

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? У вас все есть.