 | 2006/09/20(Wed) 16:02:50 編集(投稿者)
■No17483に返信(ハルさんの記事)
> ハノイの塔ゲーム
> ハノイの寺院の中に有名な塔がある。
> その中に三本の棒が立っていて、そのうちの一本には半径の異なる２６枚の
> 円盤が大きさの順に刺さっている。
> ゲームは、次のルールに従ってすべての円盤を別の棒に移し変えよ、というものである。
> １．１回の移動では、１枚の円盤を移動する。
> ２．小さな円盤の上に大きな円盤を重ねてはならない。
> １日１回の移動を行うとして、ゲームが完結するのは、何日後か？
n枚の円盤を他の棒に移す手順（日数）を a[n] とおく。棒にA,B,Cと名前を付ける。
Aにあるn+1枚の円盤を移す手順は、n枚をBに移し、残った1枚をCに移し、Bのn枚をCに移せばよい。
よって a[n+1]=a[n]+1+a[n]。
以上より、漸化式 a[n+1]=2a[n]+1、a[1]=1 から一般項を求め、a[26]を計算すればよい。
ちなみに一般項は、a[n]=2^n-1 で a[26]=2^26-1=67108863 です。
|