数据结构与算法:汉诺塔问题(C++)
程序员文章站
2024-03-24 14:52:04
...
任务:利用C++编码解决汉诺塔问题
汉诺塔问题简介:相传在古印度圣庙中,有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上,有三根杆(编号A、B、C),在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标:把A杆上的金盘全部移到C杆上,并仍保持原有顺序叠好。操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。
代码如下:
#include <iostream>
#define NUM 4
using namespace std;
void HanoiTower(int num, char src, char tmp, char dst); // 汉诺塔移动算法(递归)
int times = 0; // 全局变量,储存搬运次数
// 主函数
int main()
{
cout << "需要移动的金盘数量:" << NUM << endl;
HanoiTower(NUM, 'A', 'B', 'C');
cout << "一共需要移动:" << times << "次" << endl;
while (1);
return 0;
}
// 汉诺塔移动算法(递归)
// num:圆盘数量 src:源塔 tmp:临时塔 dst:目标塔
void HanoiTower(int num, char src, char tmp, char dst)
{
//如果圆盘数量为1,直接将金盘从源塔移动至目标塔
if (num == 1)
{
cout << src << "-->" << dst << endl;
times++;
return;
}
//如果圆盘数量大于1,将最底下的那个金盘视为一部分,其上所有的金盘视为另一部分(整体当做一个金盘来看待,以下称为 “整体盘”)
//将整体盘从源塔移动到临时塔
HanoiTower(num - 1, src, dst, tmp);
//将源塔中仅剩的金盘移动到目标塔
HanoiTower(1, src, tmp, dst);
//将整体盘从临时塔移动到目标塔
HanoiTower(num - 1, tmp, src, dst);
}
程序运行结果如下(以4个金盘为例):