首页 > 代码库 > 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(汉诺塔问题)用栈来求解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。