C＋＋汉诺塔算法：汉诺塔是递归的一个非常典型的问题---任务易只需一步，快速开始
扫一扫，访问微社区
请完成以下验证码
查看: 7617|回复: 5|关注: 0
用Matlab递归解决，汉诺塔解决过程
<h1 style="color:# 麦片财富积分
新手, 积分 5, 距离下一级还需 45 积分
我的作业是编一个展示出任意盘数的汉诺塔的解决过程，要求用递归解决。我写的代码如下
function [start,finish,tmp]=moveTower(n,start,finish,tmp)
& & finish=[start(1) finish]；
& & start(1)=[ ]；
& & moveTower(n-1,start,tmp,finish);
& & finish=[start(1) finish]；
& & start(1)=[ ]；
& &moveTower(n-1,tmp,finish,start);
但我遇到了两个问题。
1调用下一层函数时tmp和finish应该互换，也就是把tmp当finish，但结果表明并没有互换。moveTower(n-1,start,tmp,finish);这种顺序不应该让他俩已经互换了吗？怎么办？
2从下层函数反馈会的变量不能进入上层函数，比如在最底层时，finish有一个元素1，start有两个元素2，3。但进入倒数第二层后，start又变成了1，2，3，而finish是空的（初始情况）。我试过global,但报错说“Warning: The value of local variables may have been changed to match the
& && && &globals.&&Future versions of MATLAB will require that you declare
& && && &a variable to be global before you use that variable.“能说一下是怎么回事吗？我该怎么办？
[ 本帖最后由 mooni 于
09:54 编辑 ]
<h1 style="color:# 麦片财富积分
function [start,finish,tmp]=moveTower(n,start,finish,tmp)
改为function [newN start,finish,tmp]=moveTower(n,start,finish,tmp)
并且在函数里加上newN = n-1;
调用moveTower，参数是值传递。所以只在内部有效。
你需要在调用的时候返回值更新当前值，例如：
[n start finish tmp]=moveTower(n-1,start,tmp,finish);
我没细看你的算法，返回顺序不一定对，主要是说明需要这样来更新现在的状态。
<h1 style="color:#0 麦片财富积分
不知何许人也~
关注者： 490
回复 1# heyuhao89 的帖子
貌似这个可以实现:
===========
function moveTower(n,start,mid,over)
%n表示塔的数量,start 表示起始位置,over表示终止位置,mid表示借助于这个位置将塔从start移动到over.
& & str = sprintf('%d-&%d',start,over);
& & disp(str);
& & moveTower(n-1,start,over,mid);
& & moveTower(1,start,mid,over);
& & moveTower(n-1,mid,start,over);
================测试:
moveTower(3,1,2,3)
[ 本帖最后由 faruto 于
00:10 编辑 ]
[url=http://blog.sina.com.cn/faruto][color=red]孤单是一个人的狂欢狂欢是一群人的孤单[/color][/url] [url=http://www.ilovematlab.cn/thread-.html]神经网络30个案例分析[/url]
<h1 style="color:# 麦片财富积分
谢谢二位的帮助！现在变量传递的问题已经解决了。因为我们最后要求画图，我令start=1:n,tmp=[ ],finish=[ ],移动碟子就是移动数字。现在最后结果没问题，但我发现无论n是几，第一步都是从start移到tmp上，这显然不对。而且其中总有一步把一个棒上的碟子一下全部移到另一个上，十分诡异。是不是运算过程中变量名在曾与层间变化？请再帮忙看一眼吧。谢谢。
function [start,finish,tmp]=moveTower(n,start,finish,tmp)
& & finish=[start(1) finish];
& & start(1)=[];
& & [start tmp finish]=moveTower(n-1,start,tmp,finish);
& & start%为了看一下运算的过程
& & finish
& & [start finish tmp]=moveTower(1,start,finish,tmp);
& & finish
& & [tmp finish start]=moveTower(n-1,tmp,finish,start);
& & finish
<h1 style="color:# 麦片财富积分
这是我的运算结果
please inter a positive integer for the level of Hano Tower-&3
& &&&2& &&&3
& &Empty matrix: 1-by-0
& &&&1& &&&2
& &&&1& &&&2
& &Empty matrix: 1-by-0
& &Empty matrix: 1-by-0
& &&&1& &&&2
& &Empty matrix: 1-by-0
& &&&2& &&&3
& &Empty matrix: 1-by-0
& &Empty matrix: 1-by-0
& &&&1& &&&2& &&&3
& &Empty matrix: 1-by-0
& &Empty matrix: 1-by-0
& &&&1& &&&2& &&&3
<h1 style="color:# 麦片财富积分
谢谢，我的问题已经全部解决了。谢谢二位！
站长推荐 /3
用 MATLAB/Simulink开发自动驾驶功能的实例研究
MATLAB中文论坛是全球最大的 MATLAB & Simulink 中文社区。用户免费注册会员后，即可下载代码，讨论问题，请教资深用户及结识书籍作者。立即注册加入我们吧！
MATLAB官方社交平台
MATLAB中文论坛微社区豆丁微信公众号
君，已阅读到文档的结尾了呢~~
汉诺塔问题的非递归算法分析
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
汉诺塔问题的非递归算法分析
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口算法详解--汉诺塔
我的图书馆
算法详解--汉诺塔
汉诺塔算法详解&说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小 至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当 盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。&&&如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A-&B、A -&C、B-&C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。&&事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：264- 1 = 为5.82e+16年，也就是约5000世纪，如果对这数字没什么概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。&演算法Procedure HANOI(n, A, B, C) [
IF(n == 1) [
PRINT("Move sheet " n " from " A " to " C);
HANOI(n-1, A, C, B);
PRINT("Move sheet " n " from " A " to " C);
HANOI(n-1, B, A, C);
] 实作C#include &stdio.h&void hanoi(int n, char A, char B, char C) {
if(n == 1) {
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n-1, A, C, B);
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n-1, B, A, C);
}}int main() {
printf("请输入盘数：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;} Javaimport java.io.*;public class Hanoi {
public static void main(String args[]) throws IOException {
buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入盘数：");
n = Integer.parseInt(buf.readLine());
Hanoi hanoi = new Hanoi();
hanoi.move(n, 'A', 'B', 'C');
public void move(int n, char a, char b, char c) {
if(n == 1)
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, a, c, b);
System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, b, a, c);
}} 解释如下：【From：http://zhidao.baidu.com/question/】Hanoi塔问题, 算法分析如下，设A上有n个盘子。如果n=1，则将圆盘从A直接移动到C。如果n=2，则：（1）将A上的n-1（等于1）个圆盘移到B上；（2）再将A上的一个圆盘移到C上；（3）最后将B上的n-1（等于1）个圆盘移到C上。如果n=3，则：A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：（1）将A上的n`-1（等于1）个圆盘移到C上。（2）将A上的一个圆盘移到B。（3）将C上的n`-1（等于1）个圆盘移到B。B）将A上的一个圆盘移到C。C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：（1）将B上的n`-1（等于1）个圆盘移到A。（2）将B上的一个盘子移到C。（3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。从上面分析可以看出，当n大于等于2时， 移动的过程可分解为三个步骤：第一步 把A上的n-1个圆盘移到B上；第二步 把A上的一个圆盘移到C上；第三步 把B上的n-1个圆盘移到C上；其中第一步和第三步是类同的。 当n=3时，第一步和第三步又分解为类同的三步，即把n`-1个圆盘从一个针移到另一个针上，这里的n`=n-1。
[转]&[转]&[转]&[转]&[转]&
喜欢该文的人也喜欢算法工程师。兴趣广泛，喜欢尝试不同的东西。
汉诺塔问题的递归和非递归算法
汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
如果考虑一下把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。
在本文中，将讨论用递归和非递归的方法来解决汉诺塔问题。
1、 通过递归实现汉诺塔问题的求解
设f(n)为将n片圆盘所在塔全部移动到另一塔最少总次数；由递归算法可知：f(1) = 1;当n&1时，f(n)
= f(n-1) +
1 + f(n-1)。f(n) = 把上面n-1片圆盘移动到中间塔最少总次数f(n-1) + 把第n片圆盘移动到目标塔+ 把中间盘的n-1片圆盘移动到目标塔最少总次数为f(n-1)。由数学计算可得：f(n)=2^n-1。(n&0)。此算法的递归代码实现如下所示：
#include &fstream&
#include &iostream&
#include&time.h&
void Move(int n,char x,char y)
cout&&"把"&&n&&"号从"&&x&&"挪动到"&&y&&
void Hannoi(int n,char a,char b,char c)
Move(1,a,c);
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
int main()
cout&&"请输入要求解的汉诺塔的阶数： ";
clock_t start,
start = clock();
cout&&"以下是7层汉诺塔的解法:"&&
Hannoi(n,'a','b','c');
cout&&"输出完毕！"&&
finish = clock();
printf("解决此 %d 阶汉诺塔所需的时间为：%.2f ms\n",n,(double)(finish-start));
system("pause");
}2、 通过非递归的思想来实现汉诺塔问题的求解
汉诺塔的非递归算法描述如下：
首先容易证明，当盘子的个数为n时，移动的次数应等于2^n - 1。
一位美国学者发现一种出人意料的方法，只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。
根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；
若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。
即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘
这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。
该算法的实现代码如下：
#include &iostream&
#include&time.h&
//圆盘的个数最多为64
const int MAX = 64;
//用来表示每根柱子的信息
struct st{
int s[MAX]; //柱子上的圆盘存储情况
//栈顶，用来最上面的圆盘
//柱子的名字，可以是A，B，C中的一个
int Top()//取栈顶元素
return s[top];
int Pop()//出栈
return s[top--];
void Push(int x)//入栈
s[++top] =
long Pow(int x, int y); //计算x^y
void Creat(st ta[], int n); //给结构数组设置初值
void Hannuota(st ta[], long max); //移动汉诺塔的主要函数
int main(void)
clock_t start,
cout&&"请输入汉诺塔的阶数：";
cin && //输入圆盘的个数
start = clock();
st ta[3]; //三根柱子的信息用结构数组存储
Creat(ta, n); //给结构数组设置初值
long max = Pow(2, n) - 1;//动的次数应等于2^n - 1
Hannuota(ta, max);//移动汉诺塔的主要函数
finish = clock();
printf("解决此 %d 阶汉诺塔所需的时间为：%.2f ms\n",n,(double)(finish-start));
system("pause");
void Creat(st ta[], int n)
ta[0].name = 'A';
ta[0].top = n-1;
//把所有的圆盘按从大到小的顺序放在柱子A上
for (int i=0; i&n; i++)
ta[0].s[i] = n -
//柱子B，C上开始没有没有圆盘
ta[1].top = ta[2].top = 0;
for (int i=0; i&n; i++)
ta[1].s[i] = ta[2].s[i] = 0;
//若n为偶数，按顺时针方向依次摆放 A B C
if (n%2 == 0)
ta[1].name = 'B';
ta[2].name = 'C';
//若n为奇数，按顺时针方向依次摆放 A C B
ta[1].name = 'C';
ta[2].name = 'B';
long Pow(int x, int y)
long sum = 1;
for (int i=0; i&y; i++)
void Hannuota(st ta[], long max)
intk = 0; //累计移动的次数
while (k & max)
//按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch = ta[i%3].Pop();
ta[(i+1)%3].Push(ch);
cout && ++k && ": " &&
"Move disk " && ch && " from " &&ta[i%3].name &&
" to " && ta[(i+1)%3].name &&
//把另外两根柱子上可以移动的圆盘移动到新的柱子上
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())
ta[(i-1)%3].Pop();
ta[(i+1)%3].Push(ch);
cout && ++k && ": " && "Move disk"
&& ch && " from " && ta[(i-1)%3].name
&& " to " && ta[(i+1)%3].name &&
ta[(i+1)%3].Pop();
ta[(i-1)%3].Push(ch);
cout && ++k && ": " && "Move disk"
&& ch && " from " && ta[(i+1)%3].name
&& " to " && ta[(i-1)%3].name &&
}3、 实验结果及分析（测试时以7阶汉诺塔为例）
使用递归算法时运行的情况：
使用非递归算法时运行的情况：
从实验结果可以看出，与n皇后问题不同，对于汉诺塔问题的求解，当使用递归的方法来解决时它的时间复杂度比非递归的方法要好。而且，使用递归算法写代码时更容易理解。通过对于汉诺塔问题非递归与递归方法的对比可以得出结论：有的时候使用的递归的方法对于问题的求解不仅更能使人容易理解，而且效率更高。我们在以后编代码时也应该注意递归方法的使用。
递归转非递归学习三：汉诺塔问题
汉诺塔(必须经过中间柱子)递归与非递归详解与代码实现
《程序员的数学》：汉诺塔问题（Hanoi问题）的递归算法与非递归算法总结
非递归求解汉诺塔的两种方法
汉诺塔非递归算法分析与实现
汉诺塔的递归实现与非递归实现
汉诺塔 经典递归算法 in python
没有更多推荐了，