円盤が6枚のハノイの塔を、最小の移動回数で解くときの移動回数はいくつか。

解説

正解は「63」です。n 枚の円盤を移すには、上の n−1 枚を作業用の柱へ移し、最も大きい円盤を目的の柱へ1回移し、n−1 枚を再び目的の柱へ移します。移動回数を T(n) とすると $T(n)=2T(n-1)+1$、$T(1)=1$ で、これを解くと $T(n)=2^n-1$ となります。n=6 では $2^6-1=63$ 回です。「64」は $2^6$ で、1を引き忘れた値です。「36」は $6^2$ で、移動回数が n の2乗に比例すると誤った値です。「32」は $2^5$ で、5枚の場合の回数31とも異なり根拠がありません。円盤が1枚増えるごとに移動回数はほぼ2倍になるので、計算量は $O(2^n)$ です。