洛谷 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; }注:题目来源于洛谷平台,转载请注明文章出处https://blog.csdn.net/weixin_45912291/article/details/108369610