ハノイの塔の計算時間についての質問です。

ハノイの塔の時間計算量が 2n - 1 になるのはなぜかを表したいのですが、どう説明したら解りやすいですか？


T(n) = (n段を解く手数) と書くことにすれば
T(n) = 2T(n-1) + 1

1. T(n) + 1 = 2{T(n-1) + 1} と変形できること
2. つまり, (1段のときの手数) + 1から順に2倍,2倍,2倍,…されていること
3. そのような規則に従うと, T(n)+1 = (T(1)+1)*2^(n-1) と表せること
4. T(1)=(1段のときの手数)=1 だから T(n)+1=2*2^(n-1) = 2^n
5. 結局, T(n) = 2^n - 1

というのが見つかったのですが、
なぜ1.で+1をするのか。等々わからないことだらけです
T(n)を求める時のテクニックでしょうか？

No.2 ベストアンサー 回答者： okormazd 回答日時： 2011/01/06 09:05

Aに積まれている円盤n-1枚を、Cに移す手順をT(n-1) とする。

CからBに移すのもT(n-1)、BからCに移すのにもT(n-1)かかります。
Aに積まれている円盤n枚を、Cに移す手順をT(n) とすると、
すでにCに積まれているn-1枚をBに移すのにT(n-1)、、n枚の一番大きい1枚をCに移すのに１回、
Bに移したn-1枚をCに移すのにT(n-1)かかるので、ｎ枚をCに移すには、2T(n-1)+1回かかります。
T(n)=2T(n-1)+1です。

したがって、
T(n)+1=2{(Tn-1)+1)}
ここで、n=2,3,4・・・nとすると、
T(2)+1=2{T(1)+1}
T(3)+1=2{T(2)+1}
T(4)+1=2{T(3)+1}
　・
　・
T(n-1)+1=2{(T(n-2)+1}
T(n)+1=2{T(n-1)+1}
で、辺々掛け算して、T(2)+1、T(3)+1、T(4)+1・・・T(n-1)+1で割ると、
T(n+1)+1=2^(n-1){T(1)+1}=2^(n-1)*2=2^n
結局、
T(n)=2^n-1
です。

「T(n)を求める時のテクニックで」す。

No.3 回答者： okormazd 回答日時： 2011/01/06 09:08

#2です。

T(n+1)+1=2^(n-1){T(1)+1}=2^(n-1)*2=2^n

これミスです。

T(n)+1=2^(n-1){T(1)+1}=2^(n-1)*2=2^n

ですね。

No.1 回答者： nattocurry 回答日時： 2011/01/06 08:36

T(n) = 2T(n-1) + 1

これを
T(n) + a = 2{T(n-1) + a}
の形にできそうだから、その形にしたのです。
「できそう」かどうかのひらめき？は、経験によるものでしょうね。

T(n) + a = 2{T(n-1) + a}
T(n) + a = 2T(n-1) + 2a
T(n) = 2T(n-1) + a
なので、a=1

よって、
T(n) + 1 = 2{T(n-1) + 1}