洛谷 T131261 梵塔问题（递归）
题目背景
相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。
题目描述
给定初始圆盘数量，要求输出移动步骤。
输入格式
一个数n，表示初始A杆上圆盘的数量
输出格式
若干行，每行的格式如下：
step x: y -> z
其中x表示这是第几步，y,z为a,b,c三个字母中的某两个，表示该步的具体操作
注意：冒号“：”右侧有一个空格，“->”号两侧各有一个空格
输入输出样例
输入 #1
2
输出 #1
step 1: a -> b step 2: a -> c step 3: b -> c
说明/提示
1≤n≤20
参考解答：
#include <iostream> using namespace std; int step; void print(char sta, char fin) {//打印出步骤 cout << "step " << ++step << ": " << sta << " -> " << fin << endl; } void Hanoi(int n, char sta, char fin, char temp) { if (n == 1) { print(sta, fin); return; } Hanoi(n - 1, sta, temp, fin);//先将初始塔的前n-1个盘子借助目的塔移动到借用塔上 print(sta, fin);//将剩下的一个盘子移动到目的塔上 Hanoi(n - 1, temp, fin, sta);//最后将借用塔上的n-1个盘子移动到目的塔上 } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; Hanoi(n, 'a', 'c', 'b'); return 0; }
