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

本题类似于汉诺塔解决方案，可参见Wiki百科 汉诺塔问题-Wiki

其核心思想是递归，欲获取到n个盘从A柱移动到C柱的次数，可由n - 1个盘从A柱移动到C柱的次数得出。假设n - 1个盘从A柱移动到C柱的次数已知为fun(n + 1),而n个盘从A柱移动到C柱的次数为f(n)。

首先将n + 1个盘从a柱依靠c柱移动到b柱；将剩余1个盘由a柱移动到c柱，次数++；再将n + 1个盘从b柱依靠a柱移动到c柱，以此便完成了n - 1到n的移动（最小重复问题），可得出递归表达式为f(n) = 2f(n - 1) + 1;

而本题在汉诺塔问题上增加了限制条件：
a <-> b
b <-> c

同理如上，首先将n + 1个盘从a柱依靠b柱移动到c柱；将剩余1个盘由a柱移动到b柱，次数++；再将n + 1个盘从c柱依靠b柱移动到a柱;将剩余1个盘由b柱移动到c柱，次数++；再将n + 1个盘从a柱依靠b柱移动到c柱，以此便完成了n - 1到n的移动（最小重复问题），可得出递归表达式为f(n) = 3f(n - 1) + 2;

总结

汉诺塔问题中，a柱上的盘可以依赖b/c柱移至c/b柱，其他柱同理

而本题中，a柱上的盘只可依赖b柱移至c柱，b柱始终是中间柱

import java.util.*;
public class Main {
    public static int num = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            fun('a', 'b', 'c', n);
            System.out.println(num);
            num = 0;
        }

    }

    public static void fun(char a, char b, char c, int n) {
        if (n == 0) {
            return;
        }
        fun(a, b, c, n - 1);
        num++;
        fun(c, b, a, n - 1);
        num++;
        fun(a, b, c, n - 1);

    }
}