题目描述

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    /**
     * 时间复杂度O(N*logN)
     * 空间复杂度O(N)
     * @param args
     */
    public static void main(String[] args) {
        int n = sc.nextInt();
//        int n = 1;
        int step = rev(n, "left", "mid", "right");
        System.out.println(String.format("It will move %d steps", step));
    }

    static void println(int n, String d1, String d2){
        String s = String.format("Move %d from %s to %s", n, d1, d2);
        System.out.println(s);
    }

    /*
    left, mid, right
     */
    static int rev(int n, String left, String mid, String right){
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            println(n, left, mid);
            println(n, mid, right);
            return 2;
        }
        int step = 0;
        // n - 1 必须全部从 left -> mid -> right
        // 接着最大的 n 从 left -> mid
        // n - 1 必须全部从 right -> mid -> left
        // n 再 从 mid -> right
        // 至此 完成依次操作，问题由 n 变成 n-1
        // 递归即可
        step += rev(n-1, left, mid, right);
        println(n, left, mid);
        step += 1;
        step += rev(n-1, right, mid, left);
        println(n, mid, right);
        step += 1;
        step += rev(n-1, left, mid, right);
        return step;
    }


}
/*
2

Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move 8 steps.
*/