汉诺塔问题的非递归算法分析

汉诺塔问题的非递归算法设计及可视化实现彭伟【摘要】This essay introduces the classic recursive algorithm of the famous Hanoi,and then carries out further analysis and study on the algorithm based on the binary recursive tree to get a non-recursive solution without using the stack technology.Finally,designing procedures of development environment are visualized in NET,using recursive and non-recursive algorithm respectively to solve Hanoi of specified scale,with the moving effects of disc being dynamically simulated.%讨论了汉诺塔问题的经典递归算法,并基于二叉递归树对算法进行研究,得出了一种不使用堆栈技术的非递归解法,最后在.NET可视化开发环境下设计程序,分别用递归与非递归算法求解指定规模的汉诺塔问题,动态模拟了求解过程中盘片的移动效果。

【期刊名称】《武汉船舶职业技术学院学报》【年(卷),期】2011(010)006【总页数】6页(P55-59,72)【关键词】汉诺塔;二叉树;递归,非递归;可视化;模拟【作者】彭伟【作者单位】武汉城市职业学院,湖北武汉430064【正文语种】中文【中图分类】TP301汉诺塔游戏最早于19世纪出现在欧洲，它展示了一项正在婆罗门寺庙进行的任务：在创世之初，牧师被授予一个铜盘，上面有3根钻石针，在第1根针上叠放着64个碟片，每一个都比它下面的稍小一些，这位牧师被安排了一项任务，那就是将所有的碟片从第1根针移到第3根针，但要遵循的规则是：一次只能移动一个碟片，并且不允许将任何一个碟片放在比它小的碟片上面。

盐城工学院C++课程设计二级学院:信息学院班级:姓名:学号:指导老师:1．报告简介1．1 汉诺塔问题简介在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔（如下图）。

不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必在大片上面。

当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。

故汉诺塔问题又被称为“世界末日问题。

”图1-11．2 问题思想解决为满足题目中盘子的移动问题，必须遵循的条件是：一次仅能移动一个盘，且不允许大盘放在小盘的上面。

设要解决的汉诺塔共有N个圆盘，对A杆上的全部N个圆盘从小到大顺序编号，最小的圆盘为1号，次之为2号，依次类推，则最下面的圆盘的编号为N。

第一步：先将问题简化。

假设A杆上只有一个圆盘，即汉诺塔只有一层N，则只要将1号盘从A杆上移到B杆上即可。

第二步：对于一个有N（N>1）个圆盘的汉诺塔，将N个圆盘分成两部分：“上面的N-1个圆盘”看成一个整体，为了解决N个圆盘的汉诺塔，可以按下面图示的方式进行操作：（1）将A杆上面的N-1个盘子，借助B杆，移到C杆上；图1-2（2）将A杆上剩余的N号盘子移到B杆上；图1-3（3）将C杆上的N-1个盘子，借助A杆，移到B杆上。

图 1-41．3 预期目标运行程序后，首先显示：图 1-5选择 1 后，要求输入盘子的数目，即N输入后，显示递归调用时盘子移动的过程图 1-6继续选择 2 ，要求输入盘子的数目，即P输入后，显示非递归调用时盘子移动过程。

图 1-72．需求分析编写汉诺塔程序用到的知识有：符号常量的定义，循环语句，函数，栈与应用；2．1 符号常量的定义常量就是在程序运行过程中其值不发生变化的量。

汉诺塔问题求解思路汉诺塔问题是⼀个经典的问题。

汉诺塔（Hanoi Tower），⼜称河内塔，源于印度⼀个古⽼传说。

⼤梵天创造世界的时候做了三根⾦刚⽯柱⼦，在⼀根柱⼦上从下往上按照⼤⼩顺序摞着64⽚黄⾦圆盘。

⼤梵天命令婆罗门把圆盘从下⾯开始按⼤⼩顺序重新摆放在另⼀根柱⼦上。

并且规定，任何时候，在⼩圆盘上都不能放⼤圆盘，且在三根柱⼦之间⼀次只能移动⼀个圆盘。

问应该如何操作？分析如果是初次接触类似的问题，乍看之下肯定会感觉⽆从下⼿。

要把64个圆盘从a柱⼦移动到c柱⼦上，第⼀步应该怎么做？虽然可以肯定，第⼀步唯⼀的选择是移动a最上⾯的那个圆盘，但是应该将其移到b还是c呢？很难确定。

因为接下来的第⼆步、第三步……直到最后⼀步，看起来都是很难确定的。

能⽴即确定的是最后⼀步：最后⼀步的盘⼦肯定也是a最上⾯那个圆盘，并且是由a或b移动到c——此前已经将63个圆盘移动到了c上。

也许你会说，管他呢，先随便试着移动⼀下好了。

如果你这么做，你会发现，接下来你会⾯临越来越多类似的选择，对每⼀个选择都“试”⼀下的话，你会偏离正确的道路越来越远，直到你发现你接下来⽆法进⾏为⽌。

如果将这个问题的盘⼦数量减为10个或更少，就不会有太⼤的问题了。

但盘⼦数量为64的话，你⼀共需要移动约1800亿亿步（18,446,744,073,709,551,615），才能最终完成整个过程。

这是⼀个天⽂数字，没有⼈能够在有⽣之年通过⼿动的⽅式来完成它。

即使借助于计算机，假设计算机每秒能够移动100万步，那么约需要18万亿秒，即58万年。

将计算机的速度再提⾼1000倍，即每秒10亿步，也需要584年才能够完成。

注：在我的笔记本电脑上，每秒⼤约能够移动6~8百万步。

虽然64个盘⼦超出了⼈⼒和现代计算机的能⼒，但⾄少对于计算机来说，这不是⼀个⽆法完成的任务，因为与我们⼈类不同，计算机的能⼒在不断提⾼。

分解问题⼀股脑地考虑每⼀步如何移动很困难，我们可以换个思路。

python汉诺塔非递归算法如何使用Python编写非递归的汉诺塔算法首先，让我们回顾一下汉诺塔问题的背景。

汉诺塔是一个经典的数学问题，涉及到递归和栈的使用。

问题的目标是将一组不同大小的圆盘从一个柱子移动到另一个柱子，其中有三个柱子可供选择。

在移动过程中，您必须遵守以下规则：1. 您只能移动一个圆盘，并且只能将较小的圆盘放在较大的圆盘上。

2. 您只能在三个柱子之间移动圆盘。

3. 将所有圆盘从一个柱子移动到另一个柱子上是成功的。

使用递归算法可以很容易地解决这个问题。

然而，递归算法在处理大量圆盘时可能会导致递归深度过大，从而消耗大量的内存和计算时间。

因此，我们需要采用非递归的方法来解决这个问题。

接下来，让我们一步一步地介绍如何使用Python编写非递归的汉诺塔算法：步骤1: 定义一个Stack类首先，我们需要定义一个Stack类来模拟栈的行为。

在Python中，可以使用列表来实现这个类。

我们可以使用列表的append()方法将元素添加到栈顶，使用pop()方法从栈顶取出元素，使用isEmpty()方法检查栈是否为空，以及使用size()方法获取栈的大小。

下面是Stack类的代码实现：class Stack:def __init__(self):self.items = []def isEmpty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def size(self):return len(self.items)步骤2: 定义一个非递归的汉诺塔函数接下来，我们需要定义一个非递归的汉诺塔函数。

该函数的输入参数包括圆盘的数量、起始柱子、目标柱子和辅助柱子。

函数的实现思路如下：- 首先，将所有的圆盘按照倒序从起始柱子压入起始栈。

采用递归和非递归方法求解hannol问题汉诺塔问题是数学中的经典问题之一，也被认为是计算机科学中的经典问题。

它的解法可以使用递归或非递归的方法。

在本文中，我们将介绍并比较这两种解法。

汉诺塔问题的描述是：有三根柱子，A、B、C，初始时，A柱子上有n个盘子，这些盘子从小到大按顺序堆叠在一起。

现在需要将这n 个盘子从A柱子移动到C柱子上，期间可以借助B柱子。

移动盘子有以下几个规则：1.每次只能移动一个盘子；2.盘子只能从大盘子移到小盘子上；3.在移动过程中，可以借助柱子进行中转。

接下来，我们将先介绍递归解法。

递归解法：对于n个盘子，我们可以将问题分解为以下三个步骤：1.将n-1个盘子从A柱子移动到B柱子；2.将第n个盘子从A柱子移动到C柱子；3.将n-1个盘子从B柱子移动到C柱子。

递归解法的代码如下：```pythondef hanoi(n, A, B, C):if n == 1:print("Move disk %d from %s to %s" % (n, A, C)) else:hanoi(n-1, A, C, B)print("Move disk %d from %s to %s" % (n, A, C)) hanoi(n-1, B, A, C)```在这个递归函数中，n表示盘子的数量，A、B、C表示三根柱子。

当n为1时，直接将第一个盘子从A柱子移动到C柱子；否则，先将n-1个盘子从A柱子移动到B柱子，然后将第n个盘子从A柱子移动到C柱子，最后将n-1个盘子从B柱子移动到C柱子。

递归的过程中，会不断地将问题分解为子问题，直到子问题规模减小到1。

下面是一个具体的例子，假设有3个盘子，初始时都在A柱子上：```pythonhanoi(3, 'A', 'B', 'C')```输出结果为：```Move disk 1 from A to CMove disk 2 from A to BMove disk 1 from C to BMove disk 3 from A to CMove disk 1 from B to AMove disk 2 from B to CMove disk 1 from A to C```如上所示，递归解法将问题分解为子问题，然后逐步解决子问题，最后得到整体的解。

汉诺塔问题非递归算法c语言汉诺塔问题是一个经典的数学问题，也是一个常见的编程练习题。

在这个问题中，有三根柱子和一些圆盘，圆盘的大小不一，从小到大依次叠放在一根柱子上。

目标是将所有的圆盘从一根柱子移动到另一根柱子，移动过程中要保证大的圆盘在小的圆盘上面。

同时，每次只能移动一个圆盘，且不能把一个大的圆盘放在一个小的圆盘上面。

在解决汉诺塔问题时，通常采用递归算法。

但是递归算法的效率并不高，因为每次递归都会产生额外的函数调用，增加了系统的开销。

因此，我们可以通过非递归的方式来解决汉诺塔问题，提高算法的效率。

以下是一个用C语言实现的汉诺塔问题的非递归算法：```c#include <stdio.h>#include <stdlib.h>typedef struct {int n;char start, end, temp;} StackNode;typedef struct {StackNode data[100];int top;} Stack;void push(Stack *s, StackNode node) {s->data[s->top++] = node;}StackNode pop(Stack *s) {return s->data[--s->top];}void hanoi(int n, char start, char end, char temp) {Stack s;s.top = 0;StackNode node;node.n = n;node.start = start;node.end = end;node.temp = temp;push(&s, node);while (s.top > 0) {node = pop(&s);if (node.n == 1) {printf("Move disk 1 from %c to %c\n", node.start, node.end); } else {StackNode node1, node2, node3;node1.n = node.n - 1;node1.start = node.temp;node1.end = node.end;node1.temp = node.start;push(&s, node1);node2.n = 1;node2.start = node.start;node2.end = node.end;node2.temp = node.temp;push(&s, node2);node3.n = node.n - 1;node3.start = node.start;node3.end = node.end;node3.temp = node.temp;push(&s, node3);}}}int main() {int n;printf("Enter the number of disks: "); scanf("%d", &n);hanoi(n, 'A', 'C', 'B');return 0;}```在这个非递归算法中，我们使用了一个栈来模拟递归的过程。

汉诺塔问题的递归解法和⾮递归解法（python语⾔实现）1. 汉诺塔问题的⾮递归解法（python语⾔类解法）#!/usr/bin/env python#coding:utf-8import sysimport timereload(sys)sys.setdefaultencoding('utf-8')class Mycolumns(object):val=0#__slots__ = ['plates','name']def __init__(self,name='',plates_num=0): = nameself.plates = []if plates_num > 0 :for i in range(0,plates_num):self.plates.append(n-i)@staticmethoddef fun():Mycolumns.val +=1print"this is the %d th time to move" %(Mycolumns.val)【这段可以⽤类⽅法代替】【@classmethoddef fun(cls):cls.val +=1print"this is the %d th time to move" %(cls.val)】def initialize(n):stack = []mycolumn1 = Mycolumns('A',n)if n%2 == 0:mycolumn2 = Mycolumns('B')mycolumn3 = Mycolumns('C')index = 2else:mycolumn2 = Mycolumns('C')mycolumn3 = Mycolumns('B')index = 1stack.append(mycolumn1)stack.append(mycolumn2)stack.append(mycolumn3)return stack,indexdef nowcolumn(i,stack):for item in stack:if i in item.plates:return itemdef nextcolumn(i,stack):for item in stack:if i in item.plates:if i%2!=0:next = (stack.index(item)+1)%3else:next = (stack.index(item)+2)%3#print "%d next column is %s"%(i,stack[next].name)return stack[next]def move(nowcolumn,nextcolumn):n = nowcolumn.plates.pop()nextcolumn.plates.append(n)print "move plate %d from %s to %s" %(n,,)Mycolumns.fun()def hannuoyi(n):stack,index = initialize(n)#max = pow(2,n)-1#k =0#while(k<max): FINAL = [] for i in range(0,n): FINAL.append(n-i) while(stack[index].plates!=FINAL):for i in range(1,n+1):#print "i value is %d" %(i)if(nowcolumn(i,stack).plates.index(i)==len(nowcolumn(i,stack).plates)-1 and (nextcolumn(i,stack).plates==[] or i< nextcolumn(i,stack).plates[-1])): move(nowcolumn(i,stack),nextcolumn(i,stack))#k = k+1else:pass#print"can not move plate %d" %(i)print stack[0].plates,stack[0].nameprint stack[1].plates,stack[1].nameprint stack[2].plates,stack[2].nameif __name__=="__main__":n=3hannuoyi(n) 2. 汉诺塔问题的⾮递归解法（python语⾔过程式解法）#!/usr/bin/env python#coding:utf-8import sysimport timereload(sys)sys.setdefaultencoding('utf-8')global aa =0def fun():global aa = a+1print"this is the %d th time to move" %(a)def nowcolumn(i,stackA,stackB,stackC):if i in stackA:return stackAelif i in stackB:return stackBelse:return stackCdef nextcolumn(n,i,stackA,stackB,stackC):if n%2==0:if i in stackA:if i%2!=0:newcolumn = stackBelse:newcolumn = stackCif i in stackB:if i%2!=0:newcolumn = stackCelse:newcolumn = stackAif i in stackC:if i%2!=0:newcolumn = stackAelse:newcolumn = stackBelse:if i in stackA:if i%2==0:newcolumn = stackBelse:newcolumn = stackCif i in stackB:if i%2==0:newcolumn = stackCelse:newcolumn = stackAif i in stackC:if i%2==0:newcolumn = stackAelse:newcolumn = stackBreturn newcolumndef move(nowcolumn,nextcolumn):n = nowcolumn.pop()nextcolumn.append(n)print "move plate %d" %(n)fun()def hannuoyi(n):stackA = []stackB = []stackC = []FINAL = []for i in range(0,n):stackA.append(n-i)FINAL.append(n-i)print stackA,stackB,stackC,FINALwhile(stackC!=FINAL):for i in range(1,n+1):print "i value is %d" %(i)if(nowcolumn(i,stackA,stackB,stackC).index(i)==len(nowcolumn(i,stackA,stackB,stackC))-1 and (nextcolumn(n,i,stackA,stackB,stackC)==[] or i< nextcolumn(n,i,stackA,stackB,stackC)[-1])):move(nowcolumn(i,stackA,stackB,stackC),nextcolumn(n,i,stackA,stackB,stackC))else:print"can not move plate %d" %(i)print stackA,stackB,stackCif __name__=="__main__":n=6hannuoyi(n)2. 汉诺塔问题的递归解法（python语⾔）#!/usr/bin/env python#coding:utf-8import sysreload(sys)sys.setdefaultencoding('utf-8')global aa =0def fun():global aa = a+1def hannuoyi(n,A,B,C):if n==1:move(1,A,C)else:hannuoyi(n-1,A,C,B)move(n,A,C)hannuoyi(n-1,B,A,C)def move(n,tempA,tempB):print "move plate %d from column %s to column %s" %(n,tempA,tempB)fun()if __name__=="__main__":hannuoyi(3,'A','B','C')print "total:we need %d steps"%(a)。

汉诺塔问题算法思路
汉诺塔问题是一个经典的数学问题，要求将一堆大小不同的圆盘从柱子A移动到柱子C，其中每一次移动都需要满足以下条件：
1. 每次只能移动一个圆盘；
2. 大的圆盘不能放在小的圆盘上面。

如何实现这个问题的算法呢？以下是一些思路：
1. 递归算法
最常见的解决汉诺塔问题的方法就是递归。

我们可以将问题分解为三个步骤：
(1) 将n-1个圆盘从起始柱子A经过辅助柱子B移动到目标柱子C；
(2) 将最大的圆盘从起始柱子A移动到目标柱子C；
(3) 将n-1个圆盘从辅助柱子B经过起始柱子A移动到目标柱子C。

这个算法的递归终止条件是只有一个圆盘需要移动时，直接将其从起始柱子A移动到目标柱子C即可。

2. 非递归算法
除了递归算法，我们还可以使用非递归算法来解决汉诺塔问题。

具体的算法流程如下：
(1) 将起始柱子A、辅助柱子B和目标柱子C分别压入堆栈。

(2) 当堆栈不为空时，执行以下循环：
a. 弹出栈顶元素，得到当前需要移动的圆盘数目n、起始柱子A、
辅助柱子B和目标柱子C；
b. 如果n==1，直接将起始柱子A上的一个圆盘移动到目标柱子C上；
c. 否则将n-1个圆盘从起始柱子A移动到辅助柱子B上，再将第n个圆盘从起始柱子A移动到目标柱子C上，最后将n-1个圆盘从辅助柱子B移动到目标柱子C上。

d. 将移动后的三个柱子B、A和C按照起始柱子A、辅助柱子B 和目标柱子C的顺序压入堆栈，重复(2)直到堆栈为空。

以上就是汉诺塔问题的两种解决思路，大家可以根据自己的需要和理解选择适合自己的算法来解决这个问题。

python 汉诺塔非递归方法解题---随着编程语言的发展，算法问题解决的方式也在不断变化。

汉诺塔问题就是一个经典的算法问题，通常采用递归的方法来解决。

但是，非递归的方法同样可以解决汉诺塔问题，下面就让我们来看看如何用Python实现非递归方法解决汉诺塔问题。

汉诺塔问题的基本概念是这样的：给定三个柱子A、B、C，每个柱子上都放了若干个按照一定顺序排列的盘子，每个盘子都由一个数字标记，表示盘子的位置和大小。

任务是将所有的盘子从一个柱子移动到另一个柱子，移动过程中需要遵守以下规则：1. 每个盘子只能移动到比它小的柱子上；2. 三个柱子上的盘子不能重叠；3. 移动过程中不能使用柱子C。

非递归方法解决汉诺塔问题通常采用回溯法。

这种方法的基本思路是尝试将问题分解为更小的子问题，通过回溯不同的子问题的解来找到最终的解。

在汉诺塔问题中，我们可以将任务分解为将最大的盘子从柱子A移到柱子B，然后将中间大小的盘子从柱子A移到柱子C，最后将最小的盘子从柱子C移到柱子B。

通过这种方式，我们可以逐步解决汉诺塔问题。

下面是用Python实现非递归方法解决汉诺塔问题的代码：```pythondef hanoi(n, source, target, auxiliary):if n > 0:# 将n-1个盘子从source柱子移动到auxiliary柱子，再将最大的盘子从source移动到targ et柱子hanoi(n-1, source, auxiliary, target)# 将最大的盘子从auxiliary移动到target柱子print(f'Move disk {n} from {source} to {target}')# 将n-1个盘子从auxiliary柱子移动到target柱子hanoi(n-1, auxiliary, target, source)```在这个函数中，参数n表示盘子的数量，source表示起始柱子，target表示目标柱子，auxiliary表示辅助柱子。

汉诺塔（Tower of Hanoi）是一个经典的问题，它源自印度传说，相传在一个印度庙里，有一个圆座，圆座上套着三根铜柱，柱上套着64片黄金圆盘。

圆盘从大到小依序套在一根柱子上，而圆盘要从柱子上移至另一柱子上。

并且呢，规矩是穿小的不能套在大的上面，且每次只能移动一片。

有个传说是这样说的：世界末日来临前，大梵天要将这些圆盘从最左边的柱子移动到最右边的柱子上，如果在世界毁灭之前完成的话，世界就不毁灭了。

所以印度教徒一直想要研究这个问题，因为他们认为只要研究出汉诺塔的奥义，就能够通过移动圆盘，把世界毁灭的最终日期推迟。

但是即便是现代日常生活中，汉诺塔的问题也被广泛的用于算法科学的教学与理论研究之中。

那么究竟这个汉诺塔问题是怎样呢？究竟它的算法应该怎样编写呢？Python语言应该怎样实现它呢？下面就让我为你一一解答：一、汉诺塔问题背后的算法逻辑1. 汉诺塔问题的规则汉诺塔问题是经典的递归问题，它遵循以下规则：1）每次只能移动一个盘子；2）大盘子不能放在小盘子上面；3）只能在三根柱子之间移动盘子。

2. 汉诺塔问题的解法对于汉诺塔问题的解法，我们可以简单概括为以下三个步骤：A. 将n-1个盘子由A柱经过C柱移动到B柱；B. 将第n个盘子由A柱移动到C柱；C. 将n-1个盘子由B柱经过A柱移动到C柱。

二、非递归算法的实现在Python中，我们可以使用非递归算法来实现汉诺塔问题的解法。

下面给出一个示例代码：```pythondef hanoi(n, a, b, c):i = 1while n > 0:if n == 1:print("将第", n, "个盘子由", a, "移动到", c)else:print("将第", n, "个盘子由", a, "移动到", b)print("将第", n, "个盘子由", b, "移动到", c)print("将第", n, "个盘子由", c, "移动到", a)n -= 1```以上的代码中，我们使用了一个while循环来模拟递归的过程，实现了汉诺塔问题的非递归解法。

汉诺塔问题非递归算法
汉诺塔问题是一个经典的递归算法问题，但也可以使用非递归的方式解决。

下面是一种非递归算法的实现思路：
1. 创建三个栈，分别命名为A、B、C，表示三个柱子。

2. 对于n个盘子的汉诺塔问题，首先将所有盘子按从大到小的顺序依次压入栈A中。

3. 定义一个变量count，用来记录移动步数，初始值为0。

4. 如果n为奇数，则执行步骤5；如果n为偶数，则执行步骤6。

5. 循环执行以下操作：
5.1 将栈A的栈顶元素弹出，放入栈B中；
5.2 将栈A中剩余的n-1个盘子移到栈C中；
5.3 将栈B中的盘子移到栈C中；
5.4 将栈A作为辅助栈，栈B作为目标栈，栈C作为源栈，重复步骤5.1~5.3，直到栈A为空。

6. 循环执行以下操作：
6.1 将栈A的栈顶元素弹出，放入栈C中；
6.2 将栈A中剩余的n-1个盘子移到栈B中；
6.3 将栈C中的盘子移到栈B中；
6.4 将栈A作为辅助栈，栈C作为目标栈，栈B作为源栈，重复步骤6.1~6.3，直到栈A为空。

通过上述非递归算法，可以按照汉诺塔问题的规则将所有的盘子从栈A移动到栈B，并记录移动的步骤数。

3-2汉诺塔的⾮递归实现 汉诺塔实现的基本思路是：不断将n个盘的汉诺塔问题转换为2个(n-1)个盘的汉诺塔问题，⽤递归实现⽐较好理解。

设n盘问题为(n, a, b, c)，其中参数如下结构体所定义，第⼀个参数表⽰需要移动的盘⼦的数量，第⼆个参数表⽰n个盘⼦起始所在柱⼦a, 第三个参数表⽰会被借⽤的柱⼦b, 第四个参数表⽰这 n个盘⼦所在的⽬标柱⼦c。

递归思路假设(n, a, b, c)表⽰把 a柱⼦上的n个盘借助b柱⼦移动到 c 柱⼦上，这个问题的递归求解⽅式是先把 a 柱⼦的(n-1)盘⼦借助c柱⼦移动到b柱⼦上(n-1, a, c, b),然后把 a 柱⼦剩下的⼀个盘⼦移动到 c 柱⼦上(1, a, b, c)，最后把 b 柱⼦上的(n-1)个盘⼦移动到 c 柱⼦上(n-1, b, a, c)则问题求解可转换为对(n - 1, a, c, b)、(1, a, b, c)、(n - 1, b, a, c）这三个问题的求解，其中(1, a, b, c）不需要递归，可直接实现，将n个盘的汉诺塔问题转换为2个(n-1)个盘的汉诺塔问题，然后使⽤递归将(n-1)盘问题转换成(n-2)盘问题，直到盘数为1⾮递归的⽅式 递归⽅式本质上使⽤栈来实现的，所以如果采⽤⾮递归的⽅式也是使⽤栈来辅助实现。

但是若是⽤堆栈来实现的话，当将分解出的上述三个问题压⼊栈时，应该按照“需要先求解的问题后压⼊”的顺序，也就是压⼊顺序为：(n - 1, b, a, c), (1, a, b, c), (n - 1, a, c, b).1 typedef struct { //汉诺塔问题的结构类型2int N;3char A; //起始柱4char B; //借助柱5char C; //⽬标柱67 }ElementType; //汉诺塔问题的结构类型1//借助栈的⾮递归实现2void Hanoi(int n)3 {4 ElementType P, toPush;5 Stack S;67 P.N = n; P.A = 'a'; P.B = 'b'; P.C = 'c';8 S.top = -1;910 Push(&S, P);11while (S.top != -1) //当堆栈不为空时12 {13 P = Pop(&S);14if (P.N == 1)15 printf("%c -> %c\n", P.A, P.C);16else17 {18 toPush.N = P.N - 1;19 toPush.A = P.B; toPush.B = P.A; toPush.C = P.C;20 Push(&S, toPush); //将第⼆个待解⼦问题(n - 1, b, a, c)⼊栈21 toPush.N = 1;22 toPush.A = P.A; toPush.B = P.B; toPush.C = P.C;23 Push(&S, toPush); //将可直接求解的⼦问题(1, a, b, c)⼊栈24 toPush.N = P.N - 1;25 toPush.A = P.A; toPush.B = P.C; toPush.C = P.B;26 Push(&S, toPush); //将第⼀个待解⼦问题(n - 1, a, c, b)⼊栈27 }28 }29 }下⾯是栈的实现和主函数：1 #include <stdio.h>2#define MaxSize 10034 typedef struct {5 ElementType Data[MaxSize];6int top;7 }Stack; //堆栈的标准定义89void Push(Stack *PtrS, ElementType item)10 {11//⼊栈操作12if (PtrS->top == MaxSize)13 {14 printf("The stack is full!\n");15return;16 }17else18 {19 PtrS->Data[++(PtrS->top)] = item;20return;21 }22 }2324 ElementType Pop(Stack *PtrS)25 {26if (PtrS->top == -1)27 {28 printf("The stack is empty!\n");29return ERROR; //ERROR是ElementType的特殊值，标志错误30 }31else32 {33 PtrS->top--;34return (PtrS->Data[PtrS->top + 1]); //或者是return PtrS->Data[PtrS->top--];35 }36 }3738int main()39 {40int n;41 ERROR.N = -1; //ERROR是ElementType的特殊值，标志错误42 scanf_s("%d", &n);43 Hanoi(n);44return0;45 }。

汉诺塔百科名片汉诺塔初始状态汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。

上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。

上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

目录由来汉诺塔与宇宙寿命concreteHAM：汉诺塔问题的程序实现由来汉诺塔与宇宙寿命concreteHAM：汉诺塔问题的程序实现展开编辑本段由来来源汉诺塔是源自印度神话里的玩具。

上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。

上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

传说在印度，有这么一个古老的传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的６４片金片，这就是所谓的汉诺塔。

不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。

僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大，如果考虑一下把６４片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。

这需要多少次移动呢?这里需要递归的方法。

假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。

此后不难证明f(n)=2^n-1。

n=64时，f(64)= 2^64-1=18446744073709551615假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，18446744073709551615/31556952=584554049253.855年这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。

汉诺塔问题算法描述汉诺塔问题是一个经典的递归问题，其背后的算法思想可以推广到许多其他领域。

该问题的基本形式是：有三根柱子，A、B、C，A 柱子上有 n 个盘子，盘子大小不一，要将它们移到 C 柱子上，移动过程中可以借助 B 柱子，盘子移动时必须遵循以下规则：1. 每次只能移动一个盘子；2. 盘子可以放置在空柱子或比它大的盘子上；3. 盘子不能放置在比它小的盘子上。

汉诺塔问题是一个典型的递归问题，通过扩展汉诺塔问题的规模，可以引出更加深刻的递归思想和算法。

下面对汉诺塔问题的算法描述进行详细解释：1. 求解汉诺塔问题的递归算法求解汉诺塔问题的递归算法由三个部分组成：（1）将上面的 n-1 个盘子移动到 B 柱子上；（2）将最底下的一个盘子从 A 柱子移动到 C 柱子上；（3）将 B 柱子上的 n-1 个盘子移动到 C 柱子上。

基于以上三步，我们可以得到汉诺塔问题的递归算法：def hanoi(n, p1, p2, p3): if n == 1: print(p1, "->", p3) else: hanoi(n - 1,p1, p3, p2) print(p1, "->", p3) hanoi(n - 1, p2, p1, p3)该算法的时间复杂度为 O(2^n)，由于需要移动 2^n-1 次，因此对于较大的 n 值，计算时间会非常长。

2. 求解汉诺塔问题的非递归算法上面提到的递归算法，虽然精简高效，但是对于大规模数据求解效率会很低。

而非递归算法，一般具有更好的时间复杂度、更低的计算成本。

接下来我们介绍如何通过栈数据结构来实现汉诺塔问题的非递归算法：（1）我们可以将每个子问题看作一个状态，用一个元组 (n, p1, p2, p3) 来表示状态，其中 n 表示当前状态还有多少个盘子需要移动，p1、p2、p3 分别表示 A、B、C 三个柱子的状态。

（2）我们将状态元组压入栈中，每次取出栈顶元组进行处理。