暴力递归——汉诺塔问题

2021-11-08 07:27:43

打印n层汉诺塔从最左边移动到最右边的全部过程

暴力递归就是尝试

1）把问题转化为规模缩小了的同类问题的子问题

2）有明确的不需要继续进行递归的条件(base case)

3）有当得到了子问题的结果之后的决策过程

4）不记录每一个子问题的解

补充一点，如果记录每一个子问题的解就是动态规划，后续文章会讲到。

递归方法

假设有3跟柱子，左、中、右，我们细分为如下三个步骤：

1）将1~N-1层圆盘从左 -> 中（大问题，需要继续划分为小问题）

2）将第N层圆盘从左 -> 右（base case）

3）将1~N-1层圆盘从中 -> 右（大问题，需要继续划分为小问题）

递归方法改进版

如果我们忘记柱子的左中右，将三根柱子标记为from、to、other。我们实现的是，将所有的圆盘（一共N层）从from -> to，同样细分为3个步骤：

1）将1~N-1层圆盘从from -> other（大问题，需要继续划分为小问题）

2）将第N层圆盘从from -> to（base case，可以直接打印）

3）将1~N-1层圆盘从other -> to（大问题，需要继续划分为小问题）

貌似没什么改进，因为还是细分这三步，同样要递归，但关键在于忘掉柱子的左中右顺序，只需要三个变量，代码可以少很多。

总结

汉诺塔问题还有非递归的解法，因为任何递归都可以改成非递归，只需要自己设计压栈。但是博主个人认为汉诺塔的递归方法比非递归更好容易理解和实现，非递归自己去设计压栈还比较麻烦，博主目前也还没弄懂，所以就只附上代码了。后面如果搞懂了在补充吧，????

附上完整代码

package com.harrison.class12;

import java.util.Stack;

public class Code01_Hanoi {
    public static void leftToRight(int n) {
        if(n==1) {
            System.out.println("move 1 from left to right");
            return ;
        }
        leftToMid(n-1);
        System.out.println("move "+ n +" from left to right");
        midToRight(n-1);
    }
    
    public static void leftToMid(int n) {
        if(n==1) {
            System.out.println("move 1 from left to mid");
            return ;
        }
        leftToRight(n-1);
        System.out.println("move "+ n +" from left to mid");
        rightToMid(n-1);
    }
    
    public static void midToRight(int n) {
        if(n==1) {
            System.out.println("move 1 from mid to right");
            return ;
        }
        midToLeft(n-1);
        System.out.println("move "+ n +" from mid to right");
        leftToRight(n-1);
    }
    
    public static void midToLeft(int n) {
        if(n==1) {
            System.out.println("move 1 from mid to left");
            return ;
        }
        midToRight(n-1);
        System.out.println("move "+ n +" from mid to left");
        rightToLeft(n-1);
    }
    
    public static void rightToLeft(int n) {
        if(n==1) {
            System.out.println("move 1 from right to left");
            return ;
        }
        rightToMid(n-1);
        System.out.println("move "+ n +" from right to left");
        midToLeft(n);
    }
    
    public static void rightToMid(int n) {
        if(n==1) {
            System.out.println("move 1 from right to mid");
            return ;
        }
        rightToLeft(n-1);
        System.out.println("move "+ n +" from right to mid");
        leftToMid(n-1);
    }
    
    public static void hanoi1(int n) {
        leftToRight(n);
    }
    
    public static void f(int n,String from,String to,String other) {
        if(n==1) {
            System.out.println("move 1 from "+ from + " to " + to);
        }else {
            f(n-1, from, other, to);
            System.out.println("move " + n + " from " +from +" to "+to);
            f(n-1, other,to,from);
        }
    }
    
    public static void hanoi2(int n) {
        if(n>0) {
            f(n, "left", "right", "mid");
        }
    }
    
    public static class Record {
        public boolean finish1;
        public int base;
        public String from;
        public String to;
        public String other;

        public Record(boolean f1, int b, String f, String t, String o) {
            finish1 = false;
            base = b;
            from = f;
            to = t;
            other = o;
        }
    }

    public static void hanoi3(int N) {
        if (N < 1) {
            return;
        }
        Stack<Record> stack = new Stack<>();
        stack.add(new Record(false, N, "left", "right", "mid"));
        while (!stack.isEmpty()) {
            Record cur = stack.pop();
            if (cur.base == 1) {
                System.out.println("Move 1 from " + cur.from + " to " + cur.to);
                if (!stack.isEmpty()) {
                    stack.peek().finish1 = true;
                }
            } else {
                if (!cur.finish1) {
                    stack.push(cur);
                    stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
                } else {
                    System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
                    stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int n=3;
        hanoi1(n);
        System.out.println("=======================");
        hanoi2(n);
        System.out.println("=======================");
        hanoi3(n);
        System.out.println("=======================");
    }
}

码农公寓

递归方法

递归方法改进版

总结

相关文章