来，大家用LISP写写算法里面经典的汉诺塔问题

Highflybird

如图：有三个大小都不等的盘子（中间穿孔），要从A杆移动到C杆处,在移动过程中遵循如下规则：

1、大盘不能放在小盘上。

2、每次只能移动一个。

3、可以用中间的B杆过渡。

请问按照大小顺序叠起来由A处到C处最少要移动几次？

如果是4个盘子呢又要几次？ 5个盘子呢又要几次？

当然可能还有更多盘子，他们有什么规律么？

函数要求盘子数做参数，返回要移动多少次，递归，迭代都写写。

aimisiyou

(defun c:hnt ()
  (setq n (getint "请输入汉诺塔圆盘个数N="))
  (setq k (getint "请输入第几次移动步骤K="))
  (if (>= k (lsh 2 (- n 1) ))
      (alert "移动序号超出范围，请重新输入移动步骤K")
      (progn
           (setq i 0)
           (while (= (rem k 2) 0)
              (setq k (lsh k -1))
              (setq i (+ i 1))
            )
           (setq j (/ (+ k 1) 2))
           (if (= (rem (- n i) 2) 0)
               (setq va (assoc (rem j 3) '((1 . AB)(2 . BC)(0 . CA))))
               (setq va (assoc (rem j 3) '((1 . AC)(2 . CB)(0 . BA))))
            )
            (cdr va)
        )
     )
)

Free-Lancer

转载一个说明
原文地址 http://blog.csdn.net/chang_xing/article/details/7389489
我的数据结构学习从汉诺塔开始，这个简单的算法我可是整整想了一晚上，现在终于有点明白了，上机单步了几遍，有所了解，吐舌头，还是写点什么以供以后参考，也希望能对正在学算法的盆友有所裨益······

       总得来说汉诺塔就是层叠递归调用的典型例子，一直是利用A—>B  A-->C  B-->C这样的单个步骤。

       具体来说，当盘数大于一时，不违背原则下（过程中总是大在下小的在上），A先借助B再放到C上。总是把盘数看成两个来解决问题。

       比如说，当盘数为二时，顾名思义，这个很简单只要三下即可完成。这个时候，可以这样想，如果是三个，就相当于二个完成，还有一个待完成，（注意要有把问题简化为两个盘的思想,这样是递归思想的思想实现），那么把完成的看成一个，剩下待完成的看成一个（带完成的还可以把最近要完成的看成一个，剩下的先别管），这样问题就回到了二个盘数时的第一步完成状态，接下来就是递归的精华了（我是膜拜数学的强大，一个式子可以表达万种情感），然后C上的（二个看成一个那）在借助B放到A上，这样第三个就可以从B放到C上，接下来又是二个了（这个是真正的二个），看基本步骤完成。当盘数是N时，也是利用这种思想，一步一步简化，递归完成。

       接下来谈一下N个盘要几次完成问题

        书上说是2^n-1次，经过计算验证是正确的。当然我有我的思考计算，哈哈····思考如下：

        当完成n个时设用M(n)次，那么，如上我说的算法当完成n个（也就是n+1个时了）还有一个，这时需要把在C上的看成一个，借助B移动到A上（这时最后一个已到B上），当然要做M（n）次搬动了，完成后，B上的最后一个（（n+1）个）搬动到C上。这时，问题又回到了n次开始，当然需要M(n)次了。这么一来就是M（n）*2次，加上最后一个的两次，总共是M(n)*2+2=M(n+1)次，好了现在是纯数学问题了，可以利用数学知识算出来最后结果，（我还没算，哈哈，我数学不好呀），步骤没错的话，应该结果是M（n）=2^n-1.

        以上只是个人体会，写的有些弱智，有什么不正确的还请高人指教。

       下面是程序具体实现，（上面为C下面C++）仅供参考

Love-Lisp

1. ;;打印移动轨迹
   
2. (defun move (a b)
   
3.   (princ a)
   
4.   (princ " ==> ")
   
5.   (princ b)
   
6.   (princ "\n")
   
7.   1
   
8.   )
   
9. ;;递归移动汉诺塔
   
10. (defun hanoi (n a b c)
    
11.   (if (= 1 n)
    
12.     (move a c)
    
13.     (+
    
14.       (hanoi (1- n) a c b)
    
15.       (move a c)
    
16.       (hanoi (1- n) b a c)
    
17.       )
    
18.     )
    
19.   )
    
20. ;;汉诺塔递归算法
    
21. (defun c:tt ()
    
22.   (initget 6)
    
23.   (setq n (getint "\n输入汉诺塔个数:"))
    
24.   (setq a (hanoi n "A" "B" "C"))
    
25.   (princ "移动次数:") (princ a)
    
26.   (princ)
    
27.   )

;;打印移动轨迹<br /> (defun move (a b)<br />   (princ a)<br />   (princ " ==> ")<br />   (princ b)<br />   (princ "\n")<br />   1<br />   )<br /> ;;递归移动汉诺塔<br /> (defun hanoi (n a b c)<br />   (if (= 1 n)<br />     (move a c)<br />     (+<br />       (hanoi (1- n) a c b)<br />       (move a c)<br />       (hanoi (1- n) b a c)<br />       )<br />     )<br />   )<br /> ;;汉诺塔递归算法<br /> (defun c:tt ()<br />   (initget 6)<br />   (setq n (getint "\n输入汉诺塔个数:"))<br />   (setq a (hanoi n "A" "B" "C"))<br />   (princ "移动次数:") (princ a)<br />   (princ)<br />   )

ayl1004

2. (defun func (n)
   
3.   (cond ((< n 1) 0)
   
4.         ((= n 1) 1)
   
5.         ((> n 1) (+ (* (func (1- n)) 2) 1))
   
6.         (t nil)
   
7.   )
   
8. )

(defun func (n)<br />   (cond ((< n 1) 0)<br />         ((= n 1) 1)<br />         ((> n 1) (+ (* (func (1- n)) 2) 1))<br />         (t nil)<br />   )<br /> )

aimisiyou

如果要求第k步的移法，用递归效率太低了。我采用满二叉树的数据结构可以直接输入步数k,，直接得出该步移动方法。

Highflybird

aimisiyou 发表于 2015-1-22 19:51
如果要求第k步的移法，用递归效率太低了。我采用满二叉树的数据结构可以直接输入步数k,，直接得出该步移动 ...

期待楼上的代码。

aimisiyou

lisp代码还没写，但在EXCEL里实现过（纯绿色函数）。可以说下算法，完整的移动步骤构成中遍历的满二叉树。1、将第K步转换为序列对（i,j），其中（i,j）代表第k步在满二叉树中的位置，即K=（2*j-1）*2^(N-i);2、若i为奇数，以AC开始执行（j-1）次传递运算；若i为偶数，以AB开始执行（j-1）次传递运算。其中传递运算为XY-—— YZ即后一个保留前一位的右边，右边替换为不在前面的字符。如AC执行3次传递运算为AC——CB——BA——AC。