汉诺塔递归实现C++算法

汉诺塔问题的递归实现,内附C++可运行代码

问题提出：

设有三个塔柱（分别为A号，B号和C号）。初始时，有n 个圆盘按自下向上、从大到小的次序叠置在A 塔上。现要将A 塔上的所有圆盘，借助于B塔，全部移动到C塔上，且仍按照原来的次序叠置。移动的规则如下：这些圆形盘只能在个塔间进行移动，一次只能移动一个盘子，且任何时候都不允许将较大的盘子压在比它小的盘子的上面。要求如下：从键

[1]盘输入初始圆形盘子个数n，用C 语言实现n 个盘子最佳移动的全过程。

本题的目的是设计一个盘子移动的方案，使得A 号塔上的所有盘子借助于B塔按照原来的次序移动到C塔上，并且，要给出完整的盘子移动的方案。下面我们从递归和非递归两

[2]种方面进行考虑。

递归解法及其C++实现

1. 当仅有1个盘子时，把这个盘子从A塔柱移动到C塔柱上

2. 当圆盘的个数多于1个时，如下解决：

（1） 先将A塔柱上的（n-1）个圆盘通过C塔柱移动到B塔柱上

（2） 再将A塔柱上的第n个圆盘直接移动到C塔柱上

（3） 最后B塔柱上的（n-1）个圆盘通过A塔柱移动到C塔柱上

//递归算法求解汉诺塔问题2013年5月5日22:36:31

#include <iostream>

//A为放盘子的珠子，B为中间柱子，C为目标柱子

using namespace std;

void hanoi(int n,char a,char b,char c)

{

if(n==1)

{

cout<<"把"<<n<<"号盘子从"<<a<<"->"<<c<<endl;

}

else

{

hanoi(n-1,a,c,b);

cout<<"把"<<n<<"号盘子从"<<a<<"->"<<c<<endl;

hanoi(n-1,b,a,c);

}

}

int main()

{

int n;

cout<<"请输入汉诺塔问题规模：";

cin>>n;

char A='a';

char B='b';

char C='c';

hanoi(n,A,B,C);

return 0;

}

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库汉诺塔递归实现C++算法在线全文阅读。