河内塔问题解决方案1(Common Lisp实现)

河内塔问题的初始状态有A、B、C三根柱子，在A柱上有中间带孔从大到小由下到上重叠像“塔”一样的n个圆盘。目标状态是将“塔”移到B柱上，C柱作为过渡。规则是每次只能移动最上面的一个圆盘， 大圆盘不能压在小圆盘上。

这个问题可通过下述三个步骤解决：

（1）将A柱上顶层的n-1个圆盘移到C柱；

（2）将A柱底部最大的圆盘移到B柱；

（3）将n-1个圆盘从C柱移到B柱。

借助于递归，直到n的值为1时，才做实际的移动工作。

实现程序代码如下：

;从from柱移动一个圆盘到to柱

(defun move_disk (from to)

(print (list (list 'move 'disk 'from from 'to to))) ;建立指令

)

;借助spare柱, 将n个圆盘从from柱移动到to柱

(defun transfer ( from to spare n)

(cond

((equal n 1) (move_disk from to)) ;移动一个圆盘

(T

(append

(transfer from spare to (- n 1)) ;借助to柱, 将n-1个圆盘从from移到to

(move_disk from to) ; 移动最下面的圆盘

(transfer spare to from (- n 1)) ; 借助from柱, 将n-1个圆盘从spare移到to

)

)

)

)

;河内塔问题

(defun tower_of_hanoi (N)

(transfer 'A 'B 'C N)

)

程序的运行：

(tower_of_hanoi 3)

程序运行结果如下：