ハノイの塔 in Lisp
Lispの学習として簡単なハノイの塔を解くプログラムを書いてみた
ハノイの塔ってなに?って人に説明すると
以下のルールにしたがって円盤を動かすパズルみたいなもの
- 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
- 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
- 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
一見難しく見えるけど再帰関数で書くと綺麗に書ける。Cで初めてハノイの塔のソース見た時の感動はやばかった。
ということでlispのソース
(defun hanoi (n s g) (let ((r (- 6 (+ s g)))) (if (> n 1) (hanoi (- n 1) s r) ) (format t "[~d] ~d to ~d ~1%" n s g) (if (> n 1) (hanoi (- n 1) r g) ) ))
実行結果
CL-USER> (hanoi 3 1 3) [1] 1 to 3 [2] 1 to 2 [1] 3 to 2 [3] 1 to 3 [1] 2 to 1 [2] 2 to 3 [1] 1 to 3 NIL
引数はn番目の円盤をsからgに動かすという意味。s,gは棒の番号を表す。1番なら一番左みたいな感じ
円盤を表すnは大きいほど、初期位置が下にある円盤。つまり1の円盤が一番小さく一番上にいる。
基本的な構文で詰まって時間かかった…
それでは