文档介绍:关于汉诺塔问题的最终解决
这是一个的问题,几乎全部的教材上都有这个问题。由于条件是一次只能移动一个盘,且不允许大盘放在小盘上面,所以64个盘的移动次数是:
18,446,744,073,709,551,615
关于汉诺塔问题的最终解决
这是一个的问题,几乎全部的教材上都有这个问题。由于条件是一次只能移动一个盘,且不允许大盘放在小盘上面,所以64个盘的移动次数是:
18,446,744,073,709,551,615
这是一个天文数字,若每一微秒可能计算(并不输出)一次移动,那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小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);
重复以上过程,直到将全部的盘子移动到位时为止。
*程序与程序解释
#include
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
int i=0;
void main()
{
unsigned n;
printf(“please enter the number of disc:“);
scanf(“%d“, /*输入N值*/
printf(“\tneedle:\ta\t b\t c\n“);
movedisc(n,”a”,”c”,”b”); /*从A上借助B将N个盘子移动到C上*/
printf(“\t Total: %d\n“,i);
}
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle)
{
if(n>0)