我的数据结构学习从汉诺塔开始,这个简单的算法我可是整整想了一晚上,现在终于有点明白了,上机单步了几遍,有所了解,,还是写点什么以供以后参考,也希望能对正在学算法的盆友有所裨益······
总得来说汉诺塔就是层叠递归调用的典型例子,一直是利用A—>B A-->C B-->C这样的单个步骤。
具体来说,当盘数大于一时,不违背原则下(过程中总是大在下小的在上),A先借助B再放到C上。总是把盘数看成两个来解决问题。
比如说,当盘数为二时,顾名思义,这个很简单只要三下即可完成。这个时候,可以这样想,如果是三个,就相当于二个完成,还有一个待完成,(注意要有把问题简化为两个盘的思想,这样是递归思想的思想实现),那么把完成的看成一个,剩下待完成的看成一个(带完成的还可以把最近要完成的看成一个,剩下的先别管),这样问题就回到了二个盘数时的第一步完成状态,接下来就是递归的精华了(我是膜拜数学的强大,一个式子可以表达万种情感),然后C上的(二个看成一个那)在借助B放到A上,这样第三个就可以从B放到C上,接下来又是二个了(这个是真正的二个),看基本步骤完成。当盘数是N时,也是利用这种思想,一步一步简化,递归完成。
接下来谈一下N个盘要几次完成问题
书上说是2^n-1次,经过计算验证是正确的。当然我有我的思考计算,哈哈····思考如下:
当完成n个时设用M(n)次,那么,如上我说的算法当完成n个(也就是n+1个时了)还有一个,这时需要把在C上的看成一个,借助B移动到A上(这时最后一个已到B上),当然要做M(n)次搬动了,完成后,B上的最后一个((n+1)个)搬动到C上。这时,问题又回到了n次开始,当然需要M(n)次了。这么一来就是M(n)*2次,加上最后一个的两次,总共是M(n)*2+2=M(n+1)次,好了现在是纯数学问题了,可以利用数学知识算出来最后结果,(我还没算,哈哈,我数学不好呀),步骤没错的话,应该结果是M(n)=2^n-1.
以上只是个人体会,写的有些弱智,有什么不正确的还请高人指教。
下面是程序具体实现,(上面为C下面C++)仅供参考······
#include<stdio.h>
int a=0;
void hanoi(int n, char A, char B, char C)
{
a++;
if(n==1)
{
printf("Move sheet %d from %c to %c\n",n,A,C);
}
else
{
hanoi(n-1,A,C,B);
printf("Move sheet %d from %c to %c\n",n,A,C);
hanoi(n-1,B,A,C);
}
printf("a是:%d\n",a);
}
int main()
{
int n;
printf("请输入盘数:");
scanf("%d",&n);
hanoi(n,"A","B","C");
return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include<iostream>
using namespace std;
void move(int n, char s, char d)
{
cout<<n<<","<<s<<"->"<<d<<endl;
}
void hanoi(int n, char A='A', char B='B',char C='C')
{ if(1==n)
move(n,A,C);
else
{
hanoi(n-1,A,C,B); move(n,A,C); hanoi(n-1,B,A,C);
}
}
int main()
{
int i=0;
cout<<"请输入盘数:";
cin>>i;
hanoi(i);
return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
若果有什么修给的地方还请指出,学习阶段需要交流······
分享到:
相关推荐
程序设计 汉诺塔算法演示
这是个汉诺塔程序,在调试的时候,输入的数字最好不要大于15,因为每大一个数 所得的结果的步骤都会多一倍。如果你有耐心等待结果的话除外。汉诺塔是在欧洲 流行的一种游戏,有a,b,c三个竿。a竿上有若干个由大到小的...
汉诺塔的算法流程 仅供参考,本程序,可以实现N个盘子的汉诺塔排序,并在屏幕上显示操作步骤
采用C++ Buidler开发环境,C++ 语言,结合线程技术,将经典的汉诺塔算法的执行过程动态的演示出来,对于用户理解汉诺塔算法产生巨大的帮助
汉诺塔 (又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放...
知道汉诺塔的同学,有想知道其中原理的,可以看看,一个小游戏,需要源码的发邮件至:568954956@qq.com,VS2010
这个程序是汉诺塔算法的可视化软件,如果在学习这个算法但是始终搞不清时可以使用这个软件帮助理解。
汉诺塔算法 C++ 有截图 结果如下: 请输入盘子数:4 各步骤如下: A-->B A-->C B-->C A-->B C-->A C-->B A-->B A-->C B-->C B-->A C-->A B-->C A-->B A-->C B-->C 总步骤数为:15 Press any key to continue
数据结构 汉诺塔算法
一步步演示汉诺塔算法的执行流程
汉诺塔算法的演示,比较简单
网上看来的,比较详细。包含了递归以及不用递归的代码。 C和C++版的都有。
里面有递归和非递归算法,画图板,换位递归
//程序实现了mystack栈的声明和定义,并且通过函数 //move_stacks的递归调用和函数move_a_ring实现汉 //诺塔的算法,并用函数print_stacks和pr_chars实现汉诺 //塔的动画效果
今天看到了汉诺塔算法,自己实现了,并将移动过程在界面上演示出来,共入门的参考。
VC 汉诺塔算法
VC++汉诺塔算法.7z
汉诺塔算法的非递归演示.doc