左神算法笔记——汉诺塔问题

题目

问题一：给定一个数n，表示n层汉诺塔问题，请打印最优步数的所有过程。
问题二：输出一个n层汉诺塔移动的最少步数。

思路分析

• 直接使用尝试的方法写出暴力递归
• 如果n为1，那么直接向1从左边的塔移动到右边的塔即可。
• 如果不为1，那么先将n-1个棋子从左边移动到中间，以右边的塔作为跳板。
• 然后将左边最后一个棋子移动到右边。
• 然后将中间n-1个棋子移动到右边。

代码

• 问题一：

    // 问题一： 打印汉诺塔的移动过程
    public static void hanoi(int n){
        printProcess(n,"左边","中间","右边");
    }

    private static void printProcess(int n, String left, String mid, String right) {
        if(n == 1) {
            System.out.println("从" + left + "中取出一个棋子，移动到" + right);
        }else{
            printProcess(n-1,left,right,mid);
            printProcess(1,left,mid,right);
            printProcess(n-1,mid,left,right);
        }
    }

    // 测试函数
    public static void main(String[] args) {
        hanoi(4);
    }

• 问题二

    // 问题2：计算汉诺塔移动的最小步数
    public static int hanoi2(int n){
        if(n == 1) {
            return 1;
        }else{
            return hanoi2(n - 1) + 1 + hanoi2(n - 1);
        }
    }

    // 问题2衍生，使用动态规划计算最小的步数
    public static int hanoi3(int n){
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 2 * dp[i -1] + 1;
        }
        return dp[n - 1];
    }

    // 问题2衍生,优化动态规划代码
    public static int hanoi4(int n){
        int dp = 1;
        for (int i = 1; i < n; i++) {
            dp = 2 * dp + 1;
        }
        return dp;
    }

    // 测试函数
    public static void main(String[] args) {
        System.out.println(hanoi4(4));
    }