 ← 递归)
【题目来源】
【题目描述】
汉诺塔的问题大家都已经很熟悉了，有三个柱子，第 1 个 A 柱子上有一些大小不一的 n 个金片，初始状态下保证金片从上到下按照从小到大的顺序叠放，并按照 1~n 的顺序编号。
要把金片从 A 柱移动到 C 柱，可以借助 B 柱，移动过程中不能出现大金片在小金片上面的情况。
现增加一条规则：移动过程中，只允许将金片移到相邻的柱子，也就是可以从 A 柱移动金片到 B 柱，但不能从 A 直接移动金片到 C 柱；也就是说，每次移动一定会移动到 B 柱，或者从 B 柱移出。
请问：如果有 n 个金片需要从 A 柱移动到 C 柱，应该怎样移动。
【输入格式】
一个整数 n，代表 A 柱上金片的数量。(n≤5)
【输出格式】
输出若干行，第 i 行输出第 i 步需要将哪个立柱上的金片移动到哪个立柱。
【输入样例】
2
【输出样例】
A To B
B To C
A To B
C To B
B To A
B To C
A To B
B To C
【数据范围】
n≤5
【算法分析】
● 带有相邻移动限制的汉诺塔问题，移动次数为 3^n-1。
【算法代码】
#include <bits/stdc++.h>
using namespace std;void hnt(int n, char st, char to, char aux) {if(n==0) return;if(n==1) {if((st=='A' && to=='B') || (st=='B' && to=='A') ||(st=='B' && to=='C') || (st=='C' && to=='B')) {cout<<st<<" To "<<to<<endl;} else {cout<<st<<" To "<<aux<<endl;cout<<aux<<" To "<<to<<endl;}return;}if((st=='A' && to=='C') || (st=='C' && to=='A')) { //n>1hnt(n-1,st,to,aux); //A->Ccout<<st<<" To "<<aux<<endl; //A->Bhnt(n-1,to,st,aux); //C->Acout<<aux<<" To "<<to<<endl; //B->Chnt(n-1,st,to,aux); //A->C} else {hnt(n-1,st,aux,to);cout<<st<<" To "<<to<<endl;hnt(n-1,aux,to,st);}
}int main() {int n;cin>>n;hnt(n,'A','C','B');return 0;
}/*
in:
2out:
A To B
B To C
A To B
C To B
B To A
B To C
A To B
B To C
*/
【参考文献】