ハノイの塔

なんちゃってPrologっぽく書いてあるけど、Prologでは動かない擬似コード。

ハノイの塔 (1 スタート　ゴール　空き 手順) :- 手順=[ (スタート.ゴール) ].

ハノイの塔 (n スタート　ゴール　空き 手順) :- 

     ハノイの塔(n-1 スタート　空き　ゴール 手順１) ,

     ハノイの塔(1 スタート　ゴール　空き　手順２) ,

     ハノイの塔(n-1 空き　ゴール　スタート 手順３),

     連結([手順１　手順２　手順３] , 手順].

関数	条件	hanoii
hanoii		X	終
hanoii	それ以外	再帰呼び出し3回

単純に、n-1の呼び出しが2回、1枚の移動が1回の線形和なので、ｎの２倍のオーダーで終了します。