首页 > 代码库 > Hanoi(汉诺塔问题)用栈来求解

Hanoi(汉诺塔问题)用栈来求解

学习c语言必定会遇到递归问题,学递归一定知道汉诺塔问题:如何将圆盘移动到另一根柱子上,但是圆盘的顺序不能改变。

技术分享

有XYZ三个轴,n个盘子放在X轴上,目标是将N个盘子从X轴上移动到Z轴上

这里我们假设有这样一个方法F,F:将N个盘子按照原来的顺序从X轴上移动到Z轴上

如果只有一个盘子的话,一步到位

但是有N个(N>1)是,为了实现目标,我们需要利用中间轴来倒腾,我们将最后一个盘子上方的N-1个盘子按照顺序不变的方式(方法F)(这并不是移动步数最少的办法)先移动到Y轴,在将最后一个剩余的盘子移动到Z轴,最后将Y轴上的N-1个盘子(方法F)移动到Z轴。这又是两个新的汉诺塔问题,对吧。

以此类推,每次问题的规模都-1,直到只剩下一个盘子的时候,直接放过去就完成任务了。

下面我用Python代码实现

# -*-coding:utf-8-*-def move(A,B):    print(%s --> %s % (A, B))def Hanoi(n, X, Y, Z):    if n == 1:        move(X, Z)    else:        Hanoi(n - 1,X,Z,Y)        move(X,Z)        Hanoi(n-1,Y,X,Z)Hanoi(3, X, Y, Z)

递归是函数之间的调用的特殊情况,调用自身。我们先简单了解一下函数互相调用的知识,

函数A调用了函数B,系统先建立一个工作栈,调用函数B时,系统首先将做这些工作:(1)A给B的参数和返回到函数A的地址传递个B函数;(2)为函数B的局部变量分配存储区(3)将控制转移到函数B的入口。然后进行工作(1)函数B进行运算;(2)释放局部变量的存储区;(3)根据函数B内的返回地址,将控制转移到函数A。(4)函数A进行计算;以上过程符合栈的先进后出。递归同理。

技术分享 

Hanoi(汉诺塔问题)用栈来求解