汉诺塔问题

链接：https://ac.nowcoder.com/acm/contest/93963/L链接：https://ac.nowcoder.com/acm/contest/93963/L

来源：牛客网

题目描述

汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。

请编写程序，输入汉诺塔圆片的数量，输出移动汉诺塔的步骤。假定圆盘从小到大编号为1, 2, ...

输入描述:

输入为一个整数(小于20），后面跟三个单字符，用空格分隔。整数为盘子的数目，后三个字符表示三个柱子的编号。

输出描述:

移动汉诺塔的步骤：

每行显示一步操作，具体格式为：

圆盘号：起始柱 -> 目标柱子

其中圆盘号从 1 开始由小到大顺序编号。

示例1

输入

复制

3 a b c

输出

复制

1: a -> c

2: a -> b

1: c -> b

3: a -> c

1: b -> a

2: b -> c

1: a -> c

#include <iostream>

using namespace std;

void hanoi(int n, char from, char to, char aux) {

if (n == 1) {

cout << "1: " << from << " -> " << to << endl;

return;

}

hanoi(n - 1, from, aux, to);

cout << n << ": " << from << " -> " << to << endl;

hanoi(n - 1, aux, to, from);

}

int main() {

int n;

char from, to, aux;

cin >> n >> from >> aux >> to;

hanoi(n, from, to, aux);

return 0;

}

递归的经典汉诺塔问题

将问题分为

最后一个到to

n-1到aux

再将n-1从aux到to此过程与第一步相同只不过是柱子不同