问题描述
importjava.io.*;publicclassHanoi{publicstaticvoidmain(Stringargs[])throwsIOException{intn;BufferedReaderbuf;buf=newBufferedReader(newInputStreamReader(System.in));System.out.print("请输入盘数：");n=Integer.parseInt(buf.readLine());Hanoihanoi=newHanoi();hanoi.move(n,'A','B','C');}publicvoidmove(intn,chara,charb,charc){if(n==1)System.out.println("盘"+n+"由"+a+"移至"+c);else{move(n-1,a,c,b);System.out.println("盘"+n+"由"+a+"移至"+c);move(n-1,b,a,c);}}}那位兄弟能帮我分析一下这个程序，我看不懂，分析不好。特别是那个递归，谢谢，
解决方案
解决方案二：
汉诺塔咯？
解决方案三：
自己用笔模拟一行一行运行一下这些代码，就会清晰很多
解决方案四：
LZ的程序错了吧，这个递归没有终止的时候看你的程序else{move(n-1,a,c,b);System.out.println("盘"+n+"由"+a+"移至"+c);move(n-1,b,a,c);}
当n递归到2的时候，这一段执行完n就成0了，继续递归...也看不出这个程序是做什么的，就是从控制台输入一个数字，然后就是递归打印一些东西
解决方案五：
这个程序是没有错误的。题目是：河内之塔(TowersofHanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家EdouardLucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。当提示输入3的时候。结果是这样子的：请输入盘数：3盘1由A移至C盘2由A移至B盘1由C移至B盘3由A移至C盘1由B移至A盘2由B移至C盘1由A移至C看完这个结果，我发现盘3由A移至C这句有点搞不懂
解决方案六：
先占个位置。
解决方案七：
路过,学习
解决方案八：
引用4楼songchaomin的回复:
这个程序是没有错误的。题目是：河内之塔(TowersofHanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家EdouardLucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。当提示输入3的时候。结果是这样子的：请输入盘数：3盘1由A移至C盘2由A移至B盘1由C移至B盘3由A移至C盘1由B移至A盘2由B移至C盘1由A移至C看完这个结果，我发现盘3由A移至C这句有点搞不懂
有什么不懂?就是,盘123由柱A移到了盘C
解决方案九：
上面打错字,是盘123由柱A移到了柱C
解决方案十：
以前学数据结构当时就搞不懂！！递归有时真的很乱！！！
解决方案十一：
引用9楼lz12366007的回复:
以前学数据结构 当时就搞不懂！！递归有时真的很乱！！！
妖刀,通常就是难掌握,但威力无穷.
解决方案十二：
上网搜下汉诺塔问题就明白了！
解决方案十三：
算法介绍：其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n–1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放ABC；若n为奇数，按顺时针方向依次摆放ACB。（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C汉诺塔问题也是程序设计中的经典递归问题，下面我们将给出递归和非递归的不同实现源代码。●汉诺塔算法的递归实现C++源代码#include<fstream>#include<iostream>usingnamespacestd;ofstreamfout("out.txt");voidMove(intn,charx,chary){fout<<"把"<<n<<"号从"<<x<<"挪动到"<<y<<endl;}voidHannoi(intn,chara,charb,charc){if(n==1)Move(1,a,c);else{Hannoi(n-1,a,c,b);Move(n,a,c);Hannoi(n-1,b,a,c);}}intmain(){fout<<"以下是7层汉诺塔的解法:"<<endl;Hannoi(7,'a','b','c');fout.close();cout<<"输出完毕！"<<endl;return0;}●汉诺塔算法的递归实现C源代码：#include<stdio.h>voidhanoi(intn,charA,charB,charC){if(n==1){printf("Movedisk%dfrom%cto%cn",n,A,C);}else{hanoi(n-1,A,C,B);printf("Movedisk%dfrom%cto%cn",n,A,C);hanoi(n-1,B,A,C);}}main(){intn;printf("请输入数字n以解决n阶汉诺塔问题：n");scanf("%d",&n);hanoi(n,'A','B','C');}●汉诺塔算法的非递归实现C++源代码#include<iostream>usingnamespacestd;//圆盘的个数最多为64constintMAX=64;//用来表示每根柱子的信息structst{ints[MAX];//柱子上的圆盘存储情况inttop;//栈顶，用来最上面的圆盘charname;//柱子的名字，可以是A，B，C中的一个intTop()//取栈顶元素{returns[top];}intPop()//出栈{returns[top--];}voidPush(intx)//入栈{s[++top]=x;}};longPow(intx,inty);//计算x^yvoidCreat(stta[],intn);//给结构数组设置初值voidHannuota(stta[],longmax);//移动汉诺塔的主要函数intmain(void){intn;cin>>n;//输入圆盘的个数stta[3];//三根柱子的信息用结构数组存储Creat(ta,n);//给结构数组设置初值longmax=Pow(2,n)-1;//动的次数应等于2^n-1Hannuota(ta,max);//移动汉诺塔的主要函数system("pause");return0;}voidCreat(stta[],intn){ta[0].name='A';ta[0].top=n-1;//把所有的圆盘按从大到小的顺序放在柱子A上for(inti=0;i<n;i++)ta[0].s[i]=n-i;//柱子B，C上开始没有没有圆盘ta[1].top=ta[2].top=0;for(inti=0;i<n;i++)ta[1].s[i]=ta[2].s[i]=0;//若n为偶数，按顺时针方向依次摆放ABCif(n%2==0){ta[1].name='B';ta[2].name='C';}else//若n为奇数，按顺时针方向依次摆放ACB{ta[1].name='C';ta[2].name='B';}}longPow(intx,inty){longsum=1;for(inti=0;i<y;i++)sum*=x;returnsum;}voidHannuota(stta[],longmax){intk=0;//累计移动的次数inti=0;intch;while(k<max){//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子ch=ta[i%3].Pop();ta[(i+1)%3].Push(ch);cout<<++k<<":"<<"Movedisk"<<ch<<"from"<<ta[i%3].name<<"to"<<ta[(i+1)%3].name<<endl;i++;//把另外两根柱子上可以移动的圆盘移动到新的柱子上if(k<max){//把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘if(ta[(i+1)%3].Top()==0||ta[(i-1)%3].Top()>0&&ta[(i+1)%3].Top()>ta[(i-1)%3].Top()){ch=ta[(i-1)%3].Pop();ta[(i+1)%3].Push(ch);cout<<++k<<":"<<"Movedisk"<<ch<<"from"<<ta[(i-1)%3].name<<"to"<<ta[(i+1)%3].name<<endl;}else{ch=ta[(i+1)%3].Pop();ta[(i-1)%3].Push(ch);cout<<++k<<":"<<"Movedisk"<<ch<<"from"<<ta[(i+1)%3].name<<"to"<<ta[(i-1)%3].name<<endl;}}}}
解决方案十四：
我希望大家以后别再发这种类似“在网上搜一下”“下载一个”等等的废话了...1个的时候当然是1次，2个的时候是3次，3个的时候就用了7次...... 4个的时候是 “3个圆盘重新摞在一起的次数”+1次（一个盘移动的次数）+“3个圆盘重新摞在一起需要的次数” =2x“3个圆盘重新摞在一起的次数”+1次 =15次。 那么，n个的时候是 2x“（n-1）个圆盘重新摞在一起的次数”+1次。 由于1个的时候是1次，结果n个的时候为（2的n次方减1）次。 1个圆盘的时候2的1次方减1 2个圆盘的时候2的2次方减1 3个圆盘的时候2的3次方减1 4个圆盘的时候2的4次方减1 5个圆盘的时候2的5次方减1 ........ n个圆盘的时候2的n次方减1 也就是说，n=64的时候是（2的64次方减1）次。了解了数学问题再写到程序，抽象一下思维就很好理解了.可能难以理解的是参数的传递问题，hanoi.move(n,'A','B','C');这里确定了move这个方法的实参是A,B,Cpublicvoidmove(intn,chara,charb,charc)确定abc为形参，所以move(n-1,a,c,b);move(n-1,b,a,c);可以看做是改变了柱子的位置，即把问题归结为三个盘子的移动...谢谢楼主，我以前也想不通，看着上边这些不着边际的答案一气之下给想通了.这个例子还告诉我们递归分为递推和回推两个阶段你仔细看看结果是上下对称的！