练习17，L题，汉诺塔问题
题目如下：
汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。
请编写程序，输入汉诺塔圆片的数量，输出移动汉诺塔的步骤。假定圆盘从小到大编号为1, 2, ...
输入描述:
输入为一个整数(小于20），后面跟三个单字符，用空格分隔。整数为盘子的数目，后三个字符表示三个柱子的编号。
输出描述:
移动汉诺塔的步骤：
每行显示一步操作，具体格式为：
圆盘号：起始柱 -> 目标柱子
其中圆盘号从 1 开始由小到大顺序编号。
解决该问题，我们只拿三个盘来举例，会更清晰，我们的目的是把最底层挪到目标柱上，在此之前，我们应该先是把最上面的盘挪到最右面，第二个盘是放在借力柱上，如下图：
拿n个盘来举例，那就是首先第n个盘放在最右面，然后n-1号盘是放在借力柱上，所以就有了递归关系，假设起始柱子是A，目标柱子是C，借力柱子是B，那应该就是定义一个函数进行递归，flag（int n,char a,char c,char b），如果n == 1直接输出，n如果不等于1，进行flag(n-1,a,b,c);然后再进行输出，再递归，flag（n-1,c,a,b），以此类推，代码如下：
#include <iostream>
using namespace std;
void flag(int n, char a, char b, char c)
{
if (n == 1)
{
cout << "1: " << a << " -> " << c << endl;
return;
}
flag(n - 1, a, c, b);
cout << n << ": " << a << " -> " << c << endl;
flag(n - 1, b, a, c);
}
int main()
{
int n;
char a, b, c;
cin >> n >> a >> b >> c;
flag(n, a, b, c);
return 0;
}
最右公司氛围 5人发布
投递蔚来等公司10个岗位 >