東方数学郷2

■食器って積み上げたくなりませんか？　■以降リファレンス。ハノイの塔とは、3つのポールがあり、そこの一つに大きい順に何個かのリングが積み上げてあり、それを動かして他の場所に山を再結成するという問題。ただし、小さいリングの上に大きいリングを乗せてはいけないという条件がある。　■実際のハノイの塔はn段を動かすのに2^n-1回動かすので、一秒に一回動かせるとすると、30段動かすのに30年かかります。　■今回の問題は、n段の山を動かすのに必要な手数をa(n)、動かした回数をb(n)とすると、a(n)=3(2^n-1)、b(n)=3*2^(n+1)-4n-6が成り立ちます。およそ数2B程度の問題でした。　■問題に不備や間違い、あるいはより良いアルゴリズムがありましたら、一報下さい。