解決問題河內

Question

的塔我如何解決在河內問題的塔運行時間。我得到了像t（n）= 2t（n-1）+ 1這樣的遞歸關係。繪製遞歸樹後，我得到每一步的值，如1 + 2 + 4 + 8 ...樹的高度爲lg （N）。我如何計算系列的總和？我什麼時候停止？

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？你擁有一切。