东方博宜OJ 2419：汉诺塔(3) ← 递归

【题目来源】
https://oj.czos.cn/p/2419

【题目描述】
汉诺塔的问题大家都已经很熟悉了，有三个柱子，第 1 个 A 柱子上有一些大小不一的 n 个金片，初始状态下保证金片从上到下按照从小到大的顺序叠放，并按照 1~n 的顺序编号。
要把金片从 A 柱移动到 C 柱，可以借助 B 柱，移动过程中不能出现大金片在小金片上面的情况。
现增加一条规则：移动过程中，只允许将金片移到相邻的柱子，也就是可以从 A 柱移动金片到 B 柱，但不能从 A 直接移动金片到 C 柱；也就是说，每次移动一定会移动到 B 柱，或者从 B 柱移出。
请问：如果有 n 个金片需要从 A 柱移动到 C 柱，需要移动多少步。

【输入格式】
输入一个整数 n，代表金片的数量。（n≤10)

【输出格式】
输出一个整数，代表移动的步数。

【输入样例】
3

【输出样例】
26

【数据范围】
n≤10

【算法分析】
● 带有相邻移动限制的汉诺塔问题，移动次数为 3^n-1。
● 带有相邻移动限制的汉诺塔问题的代码
详见：https://blog.csdn.net/hnjzsyjyj/article/details/156211550

#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
*/

【算法代码】

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin>>n;cout<<pow(3,n)-1;return 0;
}/*
in:3
out:26
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/156211550
https://blog.csdn.net/hnjzsyjyj/article/details/156206151
https://blog.csdn.net/hnjzsyjyj/article/details/156206554
https://blog.csdn.net/hnjzsyjyj/article/details/156201255
https://blog.csdn.net/hnjzsyjyj/article/details/156192874
https://blog.csdn.net/hnjzsyjyj/article/details/156204715
https://blog.csdn.net/hnjzsyjyj/article/details/156185382
https://blog.csdn.net/hnjzsyjyj/article/details/156182882