对汉诺塔(Hanoi)问题的算法探索与研究

引言

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

1问题分析与算法设计

汉诺塔(Hanoi)问题是一个著名的问题。64个圆盘按从小到大的顺序依次套在柱x上，如图1所示。规定每次只能从一根柱子上搬动一个圆盘到另一根柱子上，且要求在搬动过程中不许大盘放在小盘上，且只有x、y、z三根柱子可供使用。

由于一次只能移动一个盘，且不允许大盘放在小盘上面,所以64个盘的移动次数是1844674407370955615。

这是一个天文数字，若1us可计算(并不输出)一次移动,那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔问题，但很难用计算机解决64层的汉诺塔问题。

针对具体问题，我们必须找出移动盘子的正确算法。首先考虑x杆下面的盘子而非杆上最上面的盘子，于是任务变成:

将上面的63个盘子移到y杆上；

将x杆上剩下的盘子移到z杆上；

将y杆上的全部盘子移到z杆上。

将这个过程继续下去，就是要先完成移动63个盘子、62个盘子、61个盘子……的工作。为了更清楚地描述算法，可以定义一个函数movedisc(n,a,b,c)。该函数的功能是：将N个盘子从x杆上借助z杆移动到y杆上。这样，移动N个盘子的工作就可以按照以下过程进行:

movedisc(n-1,x,y,z)；

将一个盘子从x移到y上；

movedisc(n-1,z,y,x)；

重复以上过程，直到将全部的盘子移动到位时为止。

2汉诺塔问题算法

下面是基于三种语言的汉诺塔算法实现程序。

(1)基于C语言的汉诺塔的算法实现程序如下：

voidhanoi(intn,charx,chary,charz)

{

if(n==1)

move(x,1,z);

else{

hanoi(n-1,x,z,y);

move(x,n,z);

hanoi(n-1,y,x,z);

}

}

⑵基于C++的汉诺塔的算法实现程序如下：

voidMove(inti,charx,chary)

{

fout«"把"《i«"号从"《x«"挪动到”《y«endl;

}

voidHannoi(intn,charx,chary,charz)

{

if(n==1)

Move(1,x,z),

else

{

Hannoi(n-1,x,z,y);Move(n,x,z);

Hannoi(n-1,y,x,z);

}

}

intmain()

{

fout<<"下面是7层汉诺塔的解法:"<<endl;Hannoi(7,'x','y','z');

fout.close();

cout<<"输出完毕！”《endl;return0;

}

(3)基于Java的汉诺塔的算法实现程序如下：publicclassHanoiTower{

staticintnDisks=3;

publicstaticvoidmain(String[]args){hanoiTower(nDisks,'x','y','z');

}

publicstaticvoidhanoiTower(inttopN,charsrc,charinter,chardest){

if(topN==1)

System.out.println("Disk1from"+src+"to"+dest);

else{

//srctointerhanoiTower(topN-1,src,dest,inter);

//movebottom

System.out.println("Disk"+topN+"from"+src+"to"+dest);

//intertodesthanoiTower(topN-1,inter,src,dest);

}

}

}

3用组合数学的思想来分析汉诺塔问题的算法

汉诺塔问题也是组合数学中著名的问题，用组合数学的思想分析如图2所示。

2基于组合数

假设/=1,但=3,对于任何nN3,那么:可以作如下设计:

第一步，将套在柱x的上部的n—1个盘按要求移到柱y上，共搬动了次；

第二步，将柱x上的最大一个盘移到柱z上，只要搬动1次;

第三步，再从柱y将n-1个盘按要求移到柱z上，也要用an-1次。

则由加法法则，{an}满足：

3结语

汉诺塔问题是一个古老的数学问题，本文给出了四种不同的的经典算法，这几种算法的优点是逻辑清晰、易于理解、可读性好、算法语句少，有助于读者更好地对汉诺塔问题进行分析和探究。

20211022_6172dcded1f07__对汉诺塔