大吉大利，今晚吃鸡
大吉大利，今晚吃鸡
https://ac.nowcoder.com/acm/contest/21763/1009
本题与经典汉罗塔很像，但由于只能相邻移动的特点有导致移动方法有些不同。
假设只有两个盘子：由于只能相邻移动所以不能先从A到B，再A到C，因为A到B之后中间那根柱子由于最上面的盘子挡着呢，所以过不去。
那么就只能通过B柱子一次性移动到C才可以将下面的盘子从A到B。然后还需要将C上面的盘子借助B移动到A，将C柱子的位置留出来让B上面的大盘子移动到C。
最后让A到C就可以了。
当然这是2个盘子的情况。扩展到n个盘子的情况就是：
先将n-1个盘子从A到C；
再第n个盘子将A到B；
再n-1个盘子将C到A；
再第n个盘子将B到C；
在前n-1个盘子将A到C；
中间直接移动的两步直接cnt++就可以了。
代码：
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
void hanoi(char a, char b, char c, int n) {
if (n==0) return ;
hanoi(a, b, c, n-1);
cnt++;
hanoi(c, b, a, n-1);
cnt++;
hanoi(a, b, c, n-1);
}
int main() {
int n;
while (cin>>n) {
cnt = 0;
hanoi('a', 'b', 'c', n);
cout<<cnt<<endl;
}
return 0;
}
另一种方法：
从上面总结出来的规律可以得到：F(n)=F(n-1)+1+F(n-1)+1+F(n-1)，左右都加上一可以得到：F(n)+1=3(F(n-1)+1) 可以得到F(n) = 3^n-1;
直接计算即可。
难怪小公司那么挑剔，让你们这些大佬把位置拿了
