题解 | 大吉大利，今晚吃鸡

#include <stdio.h>
//常规的汉诺塔，位置不重要，两道题都可以画图推一下
// int Hanoi(int n){
//     if(n==1){
//         return 1;
//     }else {
//         return 2*Hanoi(n-1)+1;
//     }
// }

//移动限制导致大盘子和集合的移动次数都增加了
int Hanoi_Neibor(int n){
    if(n==1){
        return 2;
    }else{
        return 3*Hanoi_Neibor(n-1)+2;
    }
}

int main() {
    int n,count=0;
    while(scanf("%d",&n)!=EOF){
    //汉诺塔f(n)=2*f(n-1)+1递推可知 总的移动次数可以分解为两次小集合的移动f(n-1)+新增盘子的移动1
    //X 0 0 -> X- 0 x == X x 0 -> X- x new -> X- 0 x+
    // count=Hanoi(n);

    //但本题是汉诺塔的变体！！！只能移动到相邻位置
    //X 0 x != X x 0
    //把集合的移动看作整体，前一次集合的状态一定是X 0 x (+f(n-1))-> X- 1 x (+1)-> X-/x 1 0 (+f(n-1))
    //-> X-/x 0 1 (+1) -> X- 0 x+ (+f(n-1))
    //整理可得f(n)=3*f(n-1)+2
    count=Hanoi_Neibor(n);
    printf("%d\n",count);
    }
    return 0;
}