Question

栈和队列篇·第五章·栈与递归·应用

Answer 1

假设有三个分别命名为X,Y,Z的灯塔，在X上有n个直径大小不同，以小到大编号1,2,...,n的圆盘。现要求将X上的n个圆盘移动到Z上并按照同样的次序堆叠排列，移动时必须遵守以下三点：
（1）每次只能移动一格圆盘
（2）圆盘可以放置在X,Y,Z任一塔上
（3）任何情况下都不能将大圆盘放到小圆盘上面

如果n=1，则这个圆盘直接从X移动到Z，否则执行以下步骤：
（1）用Z做中继，将X上的(n-1)个圆盘移动到Y上
（2）将X上的最后一个圆盘直接移动到Z上
（3）把X做中继，将Y轴上的(n-1)个圆盘移动到Z上

此时，通过重复以上步骤即可完成，对于术式表示如下：

首先要理解在计算机中的实现：调用函数与被调用函数之间的链接和信息交换必须通过栈进行，当一个函数运行期间调用另一个函数时，在运行该被调用函数之前，需要先完成以下的事情：

1.将所有的实际参数、返回地址等信息传递给被调用函数保存（形象的称为“保存现场”，以便需要时“恢复现场”返回到某一状态）
2.为被调用函数的局部变量分配储存空间
3.将控制转移到被调用函数的入口

从被调用函数返回调用函数之前，应完成以下：

1.保存被调用函数的计算结果
2.释放被调用函数的数据区
3.依照被调用函数保存的返回地址将控制转移到调用函数

对于多个函数嵌套的 调用的规则 是：后调用的先返回，此时内存管理实行“栈式管理”

对于hanoi(3,X,Y,Z)注意以下的变化情况：

//以上-1.21
//完整算法有时间再写XD-1.21