关于hanoi塔的递归算法，求帮助啊【vb吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：106,275贴子：
关于hanoi塔的递归算法，求帮助啊收藏
求大神帮助啊这是我写的代码，但是我不能理解电脑是怎么得出结果的，它是怎样执行的？Private Sub hanoi(n%, one$, two$, three$)If n = 1 ThenP "----"; threeElseCall hanoi(n - 1, one, three, two)P "----"; threeCall hanoi(n - 1, two, one, three)End IfEnd SubPrivate Sub Form_Click()Dim x%x = 4Call hanoi(x, "a", "b", "c")End Sub结果是a--ba--cb--ca--bc--ac--ba--ba--cb--cb--ac--ab--ca--ba--cb--c结果和书上是一样的，但是我并没有理解递归，电脑到底是怎么print出这结果的，电脑是怎么算的，求写出电脑执行的大概步骤啊。。自学vb十天了，碰到坎了。
通用软件不合适,定做软件太昂贵,自己用vb.net开发太难,何不试试FoxTable?
请容许我做一个悲伤的表情
纠结了两三个小时，我想我是废了
小顶一下。
登录百度帐号推荐应用新手园地& & & 硬件问题Linux系统管理Linux网络问题Linux环境编程Linux桌面系统国产LinuxBSD& & & BSD文档中心AIX& & & 新手入门& & & AIX文档中心& & & 资源下载& & & Power高级应用& & & IBM存储AS400Solaris& & & Solaris文档中心HP-UX& & & HP文档中心SCO UNIX& & & SCO文档中心互操作专区IRIXTru64 UNIXMac OS X门户网站运维集群和高可用服务器应用监控和防护虚拟化技术架构设计行业应用和管理服务器及硬件技术& & & 服务器资源下载云计算& & & 云计算文档中心& & & 云计算业界& & & 云计算资源下载存储备份& & & 存储文档中心& & & 存储业界& & & 存储资源下载& & & Symantec技术交流区安全技术网络技术& & & 网络技术文档中心C/C++& & & GUI编程& & & Functional编程内核源码& & & 内核问题移动开发& & & 移动开发技术资料ShellPerlJava& & & Java文档中心PHP& & & php文档中心Python& & & Python文档中心RubyCPU与编译器嵌入式开发驱动开发Web开发VoIP开发技术MySQL& & & MySQL文档中心SybaseOraclePostgreSQLDB2Informix数据仓库与数据挖掘NoSQL技术IT业界新闻与评论IT职业生涯& & & 猎头招聘IT图书与评论& & & CU技术图书大系& & & Linux书友会二手交易下载共享Linux文档专区IT培训与认证& & & 培训交流& & & 认证培训清茶斋投资理财运动地带快乐数码摄影& & & 摄影器材& & & 摄影比赛专区IT爱车族旅游天下站务交流版主会议室博客SNS站务交流区CU活动专区& & & Power活动专区& & & 拍卖交流区频道交流区
白手起家, 积分 56, 距离下一级还需 144 积分
论坛徽章:0
关于hanoi的递归解法，每本书上都有，不用太多解释。用堆栈的方法同样可以实现。
我的这个程序，效率比这个帖子
提供的算法要快一些。(去掉了所有的printf语句，比较30层hanoi塔的求解时间)
==================================================
#include &stdio.h&
#define MAX 3
#define OTHER(a,b) 'x'+'y'+'z'-a-b
struct stk{
& & int&&n;//number 当前盘子的号码
& &//from& &从哪个塔
& &//to& &&&搬到哪个塔
& & void print(){printf(&stk : %d, %c, %c\n&,n,f,t);}
& & inline void set(int ni,char fi,char ti){
& && &&&n= f= t=
& & inline void set(const stk& s){
& && & n=s.n; f=s.f; t=s.t;
int main(int argc, char *argv[])
& & stk pop[MAX+1];
& & stk s[MAX];
& & s[0].set(MAX, 'x', 'z');
& & for(int i=1; i&MAX; ++i)
& && &&&s [ i ] .set(MAX-i,'x',s[i-1].t=='z'?'y':'z');
& & int t=MAX;
& & while(1){
& && &&&--t;
& && &&&pop[(s[t].n)].set(s[t]);
& && &&&s[t].print();
& && &&&if(t+s[t].n==1)
& && &&&if(s[t].n & 1){
& && && && &for(int j= s[t].n-1;j&=1;--j)
& && && && && & s[t++].set(j,pop[j].t,OTHER(pop[j].f,pop[j].t));
& & return 0;
==================================================
(1)用一个静态数组来作为堆栈
(2)把堆栈上面的操作看成是完全2叉树的中序遍历
(3)hanoi的求解过程就是遍历树在堆栈上面的压入和弹出，实现一个求解规则: 例如3层hanoi塔，过程就是: 先弹出1号盘子，再弹出2号盘子，由于2&1，压入比2小的所有的盘子(1号盘子)，继续弹出1号盘子，弹出3号盘子，由于3&1,压入比3小的所有的盘子(2号和1号)，弹出1号，弹出2号，压入1号，弹出1号，到了栈低并且是1号盘，算法结束
(1)一个堆栈是工作栈s,保存当前的活动记录，另一个堆栈是弹出保存栈pop，用于保存各个盘子上一次被弹出的状态(上次出栈的&to&位置，例如pop[1]表示1号盘子上次弹出时的stk.t)
(2)初始化工作栈例如，我有1，2，3这3个盘子组成的hanoi塔，我需要把3从x-&z,把(1,2)这个子塔从x-&y(上一次是z，这一次就是y)，而把(1,2)从x-&y就需要先把1这个盘子从x-&z(上一次是y，这一次就是z)
(3)OTHER是一个宏，表示，'x','y','z'这3个字符当中，我输入其中的两个，输出剩下的一个.
什么作用呢? 在每次我需要压入盘子的时候，例如我第一次压入1号盘子，我要看一下上次1号盘子弹出的时候to是什么值，现在压入的from就是什么值；而现在压入的to的值就是上次to和from都不是的那个柱子
==================================================
实验结果，在我自己的机器上，gcc编译执行
(1)我的求解时间是
time ./a.out
86.06u 0.00s 1:26.31 99.7%
(2)上面那个csdn提供的算法求解时间是
91.42u 0.01s 1:31.71 99.6%
(3)但是，都比不上直接递归的求解时间
time ./a.out
24.17u 0.00s 0:24.25 99.6%
看起来递归的方法还是最快的。
void hanoi(int number,char x,char y,char z/* x,y,z...3.hanoi........char....*/){
& & if(number==1){
& && &//printf(&move 1 from %c to %c\n&,x,z);
& & hanoi( number-1,x,z,y);
& & //printf(&move %d from %c to %c\n&,number,x,z);
& & hanoi( number-1,y,x,z);
[ 本帖最后由 jeanlove 于
11:36 编辑 ]
论坛徽章:0
其实 Hanoi 已经成为经典的堆栈教学范例了，其实大家也许已经习惯用堆栈解决这个问题，其实本来可以不用堆栈……
论坛徽章:0
原帖由 langue 于
13:32 发表
其实 Hanoi 已经成为经典的堆栈教学范例了，其实大家也许已经习惯用堆栈解决这个问题，其实本来可以不用堆栈……
是的，我给学生讲递归的时候总是用这道题。
其实用栈和用递归本质是一样的。
[ 本帖最后由 JohnBull 于
13:45 编辑 ]HANOI塔问题的递归解_C/C++教程_动态网站制作指南
HANOI塔问题的递归解
来源：人气：3040
&&& HANOI塔问题是《数据结构》中用来介绍递归算法的最典型的例题。
&&& 本程序可同时将HANOI塔问题的解题步骤的中间结果显示在屏幕上和保存在文本文件中。（后一点对于显示结果很多无法在一屏中显示时，非凡有用）
&&& 程序思路很简单，看注释就明白了。&
/*& Name:&&&& hanoi2.c&&&&& & Author:&&&&&& zhuqing& Descrtion:&&&&& HANOI塔问题的递归解&& & Date: 06-08-03 11:44& Copyright: */#include &stdio.h&#define N 5/* 原柱，中间柱，目标柱初值数组 */ char a[]={'1','2','3','4','5'};char b[]={'0','0','0','0','0'};char c[]={'0','0','0','0','0'};int step=0;main(){FILE *if((fp=fopen("c:\\hanoi2.txt","w"))==NULL){&intf("\nCannot open the file!\n");&getch();&exit(0);}printf("\n============ HANOI TOWER ============\n");print(N);fprint(N,fp);move(N,a,b,c,fp); fclose(fp);getch();}/* 递归函数 */ void move(int n,char a[],char b[],char c[],FILE* fp){&&& if(n&0){&&&&&&& move(n-1,a,c,b,fp);
&&&&&&& c[n-1]=a[n-1];&&&&&&& a[n-1]='0';&&&&&&& print(N);&&&&&&& fprint(N,fp);
&&&&&&& move(n-1,b,a,c,fp);&&& }&&& }/*& 打印输出结果到屏幕的函数&&& */void print(n){printf("\nSTEP%d",step++);printf("\na:");for(i=0;i&n;i++)&&& printf("%3c",a[i]);printf("\nb:");for(i=0;i&n;i++)&&& printf("%3c",b[i]);printf("\nc:");for(i=0;i&n;i++)&&& printf("%3c",c[i]);printf("\n-------------------------------------\n");}/*& 打印输出结果到文本文件的函数&&& */void fprint(n,fp)FILE *{fputs("\na:",fp);for(i=0;i&n;i++)&&& fputc(a[i],fp);fputs("\nb:",fp);for(i=0;i&n;i++)&&& fputc(b[i],fp);fputs("\nc:",fp);for(i=0;i&n;i++)&&& fputc(c[i],fp);fputs("\n-------------------------------------\n",fp);}&&&&&&&&&&&
优质网站模板3138人阅读
ACM-数据结构（17）
什么是hanoi塔?
汉诺塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。如下图
我们把左边的柱子叫做A,中间的柱子叫做B,右边的柱子叫做C
hanoi`塔的搬运过程；
i ：左边的柱子只有两个圆盘
我们先假设在A柱子上只有两个圆盘，不用图我们用大脑想象出来最佳流程就是，现在最小的放在B柱子上面然后把大的放在C上面，最后把B柱子上面的小圆盘放在C柱子上。
ii：左边的柱子上面有三个圆盘
过程如下图：
在这种情况下，我们可以把上面的两个圆盘看作是一个，然后又回到了i情况，下图展示了三个圆盘的转移过程
iii：左边的柱子上有四个圆盘的时候
在这种情况我们通过作图做出hanoi的转移流程是很困难的了，我们可以用在ii中提及到的过程，就是我们先把上面的三个看作是一个，我们第一步的目的就是把前三个移动到中间的柱子上去。下面简单说一下转移步骤
1. 将A柱子上面的三个移动到B柱子上面(借助C柱子)
2. 将A柱子上面中最下面的圆盘移动到C柱子上面
3. 将B柱子上面的所有圆盘移动到C柱子上面(借助A柱子)
过程如下图：
通过上面的描述我们把hanoi移动的步骤一般化
将左边柱子上的N-1个圆盘移动带中间的柱子上
将第N个圆盘移动到最右边的柱子
将中间柱子上的所有圆盘移动到最右边的柱子
下面我们给出具体的代码
void hanoi(int n,char A,char B,char C)
if(n&=1) {
printf("1 move %c to %c\n",A,C);
hanoi(n-1,A,C,B);
printf("%d move %c to %c \n",n,A,C);
hanoi(n-1,B,A,C);
不要在看了，这就是全部代码了。已经没有了
╭︿︿︿╮
以上是对hanoi塔的总体概述，下面就要聊一聊真正的代码流程！
hanoi(n,A,B,C)代表的意义就是讲n个圆盘从A移动到C借助B；
* 当n等于1的时候，就代表把当前A中最大的圆盘直接从A移动到C
* 当n等于2的时候，就调用hanoi(2，A,B,C)也就是执行下面的三个步骤下面就是本文中重点了
调用honoi(1,A,C,B)就是相当于把B柱和C柱交换了
2. 执行打印语句，不进行继续调用。所以不用交换柱子
3. 调用hanoi(1,B,A,C)相当于把B柱和A柱交换了
上面的语句可以表述为：
hanoi(1,A,C,B);
printf("%d move %c to %c \n",n,A,C);
hanoi(1,B,A,C);
这就是对代码的解释！
当圆盘更多的时候无非就是进行递归知道递归到上面的状态,比如有三个圆盘的时候，调用的是：
hanoi(2,A,C,B); //step1
printf("%d move %c to %c \n",n,A,C);
hanoi(2,B,A,C);
只要理解了前两个对后面的理解也就不难了！还有一点题外话,当递归到程序注释的step1的时候，会为后续语句分配空间但不执行！
hanoi塔还有一个进阶的题目就是判断当前的状态时第几个最优的状态，将在下篇文章进行讲述！
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：317335次
积分：5519
积分：5519
排名：第5660名
原创：234篇
转载：14篇
评论：29条
(1)(3)(5)(2)(3)(4)(9)(9)(2)(28)(56)(4)(11)(3)(13)(26)(11)(13)(8)(1)(10)(3)(15)(9)> 问题详情
[Hanoi塔同题]n阶Hanoi塔同题是这样的：假设有三个分别命名为X，Y和Z的塔 座，在塔座X上插有n个直
悬赏：0&答案豆
提问人：匿名网友
发布时间：
[Hanoi塔同题]n阶Hanoi塔同题是这样的：假设有三个分别命名为X，Y和Z的塔 座，在塔座X上插有n个直径大小各不相同、依小到大编号为1，2，…，n的圆盘，如下图所示。现要求将塔座X上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘移动时必须遵守下列规则：(1)每次只能移动一个圆盘，(2)圆盘可以插在X，Y和Z中任一塔座上，(3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。请写一算法，打印出正确的操作步骤。要求先用递归函数上机实现一般Hanoi塔问题，然后改用非递归函数解同样的问题，并与递归函数进行比较。请帮忙给出正确答案和分析，谢谢！
为您推荐的考试题库
您可能感兴趣的试题
1在LC正弦波振荡电路中，不用通用型集成运算放大器作放大电路的原因是其上限截止频率太低，难以产生高频振荡信号。
)2当集成运放工作在非线性区时，输出电压不是高电平，就是低电平。
)3一般情况下，电压比较器的集成运算放大器工作在开环状态，或者引入了正反馈。
我有更好的答案
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
提示：请截图保存您的账号信息，以方便日后登录使用。
常用邮箱：
用于找回密码
确认密码：}