もしかして、有名問題??byaiu ｸｲｽﾞ一覧 [ｸｲｽﾞ大陸]

もしかして、有名問題??

2009/12/08 20:22




◎解答・解説	【2<sup>n</sup>－1回 n+1段の円盤の移動を行う場合、必ず以下の手順を踏まなければならない。 ①n+1段あるうちの上からn段までを中央の杭に移動させる。 ②残った一番下の円盤を右端に移動させる。 ③①で中央に移動させたn段の塔を右端に移す。 n+1段の円盤の移動にかかる最短回数をA(n+1)回とすると、 ①の操作にかかる最短回数はA(n)回 ②にかかる最短回数は1回 ③にかかる最短回数はA(n)回したがって、A(n+1)＝A(n)＋1＋A(n)　⇔　A(n+1)＝2A(n)＋1　となる。また、A(1)＝1 この漸化式を解くと、A(n)＝2<sup>n</sup>－1】