解 河內塔之謎


假設有三座底盤,其一底盤上有N層塔,如果依規定(大者在小者下方)將它全部移到另一底盤,總共需移動T(N)次。


T(1)=1

T(2)=2T(1)+1=2+1=3

T(3)=2T(2)+1=22+2+1=7

T(4)=2T(3)+1=23+22+2+1=15

………

T(N)=2N-1+2N-2+……..+ 23+22+2+1=2N1

 

如果N=64,假設移動一次花了一秒,將六十四層塔全部移到另一底盤,總共需移動T(64)次,需T(64)秒,而T(64)=264-1=18,446,744,073,709,551,615秒,約需58萬億年。


 

回上一頁