移64块金片问题,可能较难…………

来源:百度知道 编辑:UC知道 时间:2024/06/01 15:45:08
可能较难
有三根柱子,在其中一根上放有64块金片,它们是从下往上按照由大到小依次放的。现在把这根柱子上的64块金片移到另两根上,并保证大的始终在下,小的在上。请问最少需要移几次?

我们用递归算法解决这个问题,其算法很简单:假定要把n个金片从A搬到C,则首先将A上的前(n-1)个金片搬到B上,然后将A上的最后一个金片搬到C上,最后将B盘上的(n-1)个金片搬到C上。对于如何实现(n-1)个金片的搬动问题,则借助于递归来实现,直到n等于1时才实现真正的搬动。可以证明,这样的搬动算法是可以满足要求的。
定义梵塔问题求解函数HANOI。其中参数a、b、c、n表示将在柱a上的n个金片,通过柱b移动到柱c上。
(DEFUN HANOI(a b c n)
当只有一个金片时,直接将a上的金片移动到c上。
(COND((=n 1)(MOVE-DISK a c))
其他情况下,通过递归调用,先将柱a上的n-1个金片通过柱c移动到柱b上。
(T(HANOI a c b(- n 1))
再将柱a上的一个金片移动到柱c上。
(MOVE-DISK a c)
最后再通过递归调用,将柱b上的n-1个金片通过柱a移动到柱c上。
(HANOI b a c(- n 1)))))
函数MOVE-DISK只起显示的作用,表示出从柱from到柱to移动了一个金片。
(DEFUN MOVE-DISK(from to)
(TERPRI)
(PRINC"Move Disk From")
(PRINC from)
(PRINC"To")
(PRINC to))
为了显示金片的搬动过程,利用MOVE-DISK函数将搬动金片的次序显示出来,其中TERPRI是回车换行函数,PRINC是显示参数的函数。下面是n=3时的求解结果:
(HANOI 'a 'b 'c 3)
MOVE DISK FROM A TO C
MOVE DISK FROM A TO B
MOVE DISK FROM C TO B
MOVE DISK FROM A TO C
MOVE DISK FROM B TO A
MOVE DISK FROM B TO C