扫码获取更多资源

●汉诺塔问题

传说在世界刚创建时有一座钻石宝塔A,塔上有64个金碟。所有碟子按照从大到小的 次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔B和C。从世界创始之日起, 婆罗门的牧师们就一直在试图把塔A上的碟子移到塔C上,其间借助于塔B的帮助。每次 只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任 务时,世界末日也就到了。

算法设计

在该问题中，将一个金碟从一个塔移至另一个塔的问题是一个和原问题具有相同特征 属性的问题，只是问题的规模小于1,因此可以使用递归求解。递归模型如下。

基本项：当n=l时，将编号为1的金碟从塔A移至塔C； 归纳项：当n〉l时，将压在编号为n的金碟之上的n—1个金碟从塔A移至塔B；将 编号为n的金碟移至塔C;将塔B上的n-1个金碟移至塔Co

算法描述

下图展示了语句hanoi(3,A,B,C)的执行过程(从主函数进入递归函数到退出递归函 数返回至主函数)中递归工作栈状态的变化情况。因为算法3-10中的递归函数中有四个实 参数，所以每个工作记录包含五个数据项：四个实参和返回地址，并以递归函数中的语句行 号表示返回地址，同时假设主函数的返回地址为0。

由于递归函数结构清晰，程序易读，且其正确性也容易证明，因此利用允许递归调用的 语言（如C、C++语言）进行程序设计时，会给用户编制程序和调试程序带来很大方便。对这 样一类递归问题编程时，不需要用户自己而是由系统来管理递归工作栈。

联系我们：