关于汉诺塔问题的最终解决

问题提出:约19世纪末在欧州商店中出售种智力玩具在块铜板上有 3根杆最左边杆上自上而下、由小到大顺序串着由64个圆盘构成塔目是将最左边杆上盘全部移到右边杆上条件是次只能移动个盘且不允许大盘放在小盘上面

*问题分析和算法设计
这是个著名问题几乎所有教材上都有这个问题由于条件是次只能移动个盘且不允许大盘放在小盘上面所以64个盘移动次数是:
18446744073709551615
这是个天文数字若每微秒可能计算(并不输出)次移动那么也需要几乎百万年我们仅能找出问题解决思路方法并解决较小N值时汉诺塔但很难用计算机解决64层汉诺塔
分析问题找出移动盘子正确算法
首先考虑a杆下面盘子而非杆上最上面盘子于是任务变成了:
*将上面63个盘子移到b杆上；
*将a杆上剩下盘子移到c杆上；
*将b杆上全部盘子移到c杆上
将这个过程继续下去就是要先完成移动63个盘子、62个盘子、61个盘子....工作
为了更清楚地描述算法可以定义个movedisc(n,a,b,c)该功能是:将N个盘子从A杆上借助C杆移动到B杆上这样移动N个盘子工作就可以按照以下过程进行:
1)movedisc(n-1,a,c,b);
2)将个盘子从a移动到b上；
3)movedisc(n-1,c,b,a)；
重复以上过程直到将全部盘子移动到位时为止
*和注释
#<stdio.h>
voidmovedisc(unsignedn,charfromneedle,chartoneedle,charusingneedle);
i=0;
void
{
unsignedn;
prf(\"pleaseenterthenumberofdisc:\");
scanf(\"%d\",&n);/*输入N值*/
prf(\"\\tneedle:\\ta\\tb\\tc\\n\");
movedisc(n,\'a\',\'c\',\'b\');/*从A上借助B将N个盘子移动到C上*/
prf(\"\\tTotal:%d\\n\",i);
}
voidmovedisc(unsignedn,charfromneedle,chartoneedle,charusingneedle)
{
(n>0)
{
movedisc(n-1,fromneedle,usingneedle,toneedle);
/*从fromneedle上借助toneedle将N-1个盘子移动到usingneedle上*/
i;
switch(fromneedle)/*将fromneedle上个盘子移到toneedle上*/
{
\'a\':switch(toneedle)
{
\'b\':prf(\"\\t[%d]:\\t%2d.........>%2d\\n\",i,n,n);
;
\'c\':prf(\"\\t[%d]:\\t%2d...............>%2d\\n\",i,n,n);
;
}
;
\'b\':switch(toneedle)
{
\'a\':prf(\"\\t[%d]:\\t%2d<...............>%2d\\n\",i,n,n);
;
\'c\':prf(\"\\t[%d]:\\t%2d........>%2d\\n\",i,n,n);
;
}
;
\'c\':switch(toneedle)
{
\'a\':prf(\"\\t[%d]:\\t%2d<............%2d\\n\",i,n,n);
;
\'b\':prf(\"\\t[%d]:\\t%2d<........%2d\\n\",i,n,n);
;
}
;
}
movedisc(n-1,usingneedle,toneedle,fromneedle);
/*从usingneedle上借助fromneedle将N-1个盘子移动到toneedle上*/
}
}



=span_ad>

延伸阅读