algorithm - ハノイの塔問題の解決策

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を確認しましたか？あなたはそこにすべてを持っています。