汉诺塔问题

汉诺塔问题

问题描述

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

自定义一个栈

public class Stack<E> implements Iterable<E>{
    private LinkedList<E> stack = new LinkedList<>();
    private String name;

    public Stack() {}

    public Stack(String name) {
        this.name = name;
    }
    public String getName() {
        return name;
    }
    public void setName(String name){
        this.name = name;
    }

    public void push(E e){
        stack.push(e);
    }

    public E pop(){
        return stack.pop();
    }

    public E peek(){
        return stack.peek();
    }

    public void each(Consumer<? super E> consumer){
        stack.stream().forEach(consumer);
    }

    public boolean isEmpty(){
        return stack.isEmpty();
    }

    public int size(){
        return stack.size();
    }

    @Override
    public Iterator<E> iterator() {
        return stack.iterator();
    }
}

1.递归实现

    /** 递归方式
     */
    public void hanoi(int n,Stack<Integer> a,Stack<Integer> b,Stack<Integer> c){
        if(n == 1){
            c.push(a.pop());
            System.out.println(a.getName()+" -> "+c.getName());
        }
        else{
            hanoi(n-1,a,c,b);   //将n-1个圆盘 a -> b,此时c作为辅助柱子
            c.push(a.pop());       //将a上第n个圆盘移动到c  a -> c
            System.out.println(a.getName()+" -> "+c.getName());
            hanoi(n-1,b,a,c);   //将b上n-1个圆盘 b -> c,此时a作为辅助柱子
        }
    }

2.非递归实现

    /** 非递归方式
     *
     * 概述: 根据美国学者总结的规律写即可
     * 1. 将最小圆盘移动到下一个柱子(next)上(顺序ABC循环)
     * 2. 将除了next以外的2个柱子顶部圆盘比较,将小的移动到大的上面(如果为空则直接移动到空柱上)
     * 3. 循环步骤1,步骤2即可将一个柱子上圆盘移动到另一个柱子上
     *    如果初始时A为放圆盘柱子,B,C为空,当圆盘数量N为奇数时结果会移动到B上,N为偶数会移动到C上,
     *    因此起始时若N为奇数调换柱子B,C即可,最终会将圆盘移动到C上
     */
    public Stack<Integer> hanoiTower(int N,Stack<Integer> a,Stack<Integer> b,Stack<Integer> c){
        if((N&1) == 1){         //当n为奇数时调换b,c 柱子
            b.setName("c");
            c.setName("b");
        }
        Stack<Integer> realB = b.getName().equals("b")?b:c;    //获取到真正的b柱子
        while(!(a.isEmpty() && realB.isEmpty())) {      //当a,b柱子为空时移动完成
            int topA = a.isEmpty()?Integer.MAX_VALUE:a.peek();
            int topB = b.isEmpty()?Integer.MAX_VALUE:b.peek();
            int topC = c.isEmpty()?Integer.MAX_VALUE:c.peek();
            if(topA < topB && topA < topC){
                b.push(a.pop());    //1. 将最小圆盘移动到下一个柱子(next)上(顺序ABC循环)
                System.out.println(a.getName()+" -> "+b.getName());
                compareAndMove(a,c);//2. 将除了next以外的2个柱子顶部圆盘比较,将小的移动到大的上面(如果为空则直接移动到空柱上)
            }
            else if(topB < topA && topB < topC){
                c.push(b.pop());
                System.out.println(b.getName()+" -> "+c.getName());
                compareAndMove(b,a);
            }
            else if(topC < topA && topC < topB){
                a.push(c.pop());
                System.out.println(c.getName()+" -> "+a.getName());
                compareAndMove(b,c);
            }

        }
        return c;
    }

   public void compareAndMove(Stack<Integer> a,Stack<Integer> b){
        if(a.isEmpty() && b.isEmpty())
            return;     //移动完成
        int topA = a.isEmpty()?Integer.MAX_VALUE:a.peek();
        int topB = b.isEmpty()?Integer.MAX_VALUE:b.peek();
        if(topA < topB) {
            b.push(a.pop());
            System.out.println(a.getName()+" -> "+b.getName());
        }
        else {
            a.push(b.pop());
            System.out.println(b.getName()+" -> "+a.getName());
        }
    }

测试

    @Test
    public void testHanoi(){
        Stack<Integer> stackA = new Stack<>("a");
        Stack<Integer> stackB = new Stack<>("b");
        Stack<Integer> stackC = new Stack<>("c");
        int N = 4;
        for(int i=N;i>0;--i){
            stackA.push(i);
        }
        hanoiTower(N,stackA,stackB,stackC);     //非递归方式
        //hanoi(N,stackA,stackB,stackC);        //递归方式

        //查看结果
        if(stackC.isEmpty())
            stackB.forEach(x -> System.out.print(x+" "));
        else
            stackC.forEach(x -> System.out.print(x+" "));
    }