汉诺塔-Java实现

作者: 朱Simon | 来源:发表于2018-07-01 19:15 被阅读18次

汉诺塔-Java实现
Python 递归实现汉诺塔
汉诺塔算法java实现
2019-11-28汉诺塔算法-递归实现
数据结构与算法-递归分治-汉诺塔思想
Java算法_汉诺塔
汉诺塔自动解题动画中的iOS开发技巧
汉诺塔算法和背后的数据结构
汉诺塔 python实现
汉诺塔实现程序

图片来自网路

汉诺塔总步数：2^n -1

引入栈来表示移动wafer步骤

/**
 * Copyright (C), 2015-2018, XXX有限公司
 * FileName: Main
 * Author:   simonzhu
 * Date:     2018/7/1 下午5:31
 * Description: 汉诺塔
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package hannuota;

import java.sql.SQLOutput;
import java.util.Stack;

/**
 * 〈一句话功能简述〉<br>
 * 〈汉诺塔〉
 *
 * @author simonzhu
 * @create 2018/7/1
 * @since 1.0.0
 */
class PrintStack extends Stack {
    private String className;

    public PrintStack(String className) {
        this.className = className;
    }

    @Override
    public String toString() {
        return "["+className.toUpperCase()+"]";
    }
}

public class Main {
    private static int count=1;

    public static void main(String[] args) {

        //init hanNuoTa:A,B,C
        int waferCount=6;
        Stack a = new PrintStack("A");
        Stack b = new PrintStack("B");
        Stack c = new PrintStack("C");
        for (int i = waferCount; i >0 ; i--) {
            a.push(i);
        }
        hanNuoTa(waferCount,a,b,c);
    }

    private static void hanNuoTa(int waferCount, Stack a, Stack b, Stack c) {
        if (waferCount==1){
            moveWafer(a,c);
        }else {
            hanNuoTa(waferCount-1,a,c,b);
            moveWafer(a,c);
            hanNuoTa(waferCount-1,b,a,c);
        }
    }

    private static void moveWafer(Stack a, Stack c) {
        System.out.println("--no."+count+++"--");
        System.out.println(a.toString()+"->"+c.toString()+":"+a.peek());
        c.push(a.pop());
        printStack(a);
        printStack(c);
    }

    private static void printStack(Stack stack){
        Stack tempStack=new Stack();
        if(stack.isEmpty()){
            System.out.println(stack.toString()+":empty");
            return;
        }
        while (!stack.isEmpty()){
            tempStack.push(stack.pop());
        }
        System.out.print(stack.toString()+":"+tempStack.peek());
        stack.push(tempStack.pop());
        while (!tempStack.isEmpty()){
            System.out.print(","+tempStack.peek());
            stack.push(tempStack.pop());
        }
        System.out.println();
    }
}

程序打印结果

/Library/Java/JavaVirtualMachines/jdk-9.0.4.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=61300:/Applications/IntelliJ IDEA.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Users/simonzhu/IdeaProjects/HanNuoTa/out/production/HanNuoTa hannuota.Main
--no.1--
[A]->[B]:1
[A]:6,5,4,3,2
[B]:1
--no.2--
[A]->[C]:2
[A]:6,5,4,3
[C]:2
--no.3--
[B]->[C]:1
[B]:empty
[C]:2,1
--no.4--
[A]->[B]:3
[A]:6,5,4
[B]:3
--no.5--
[C]->[A]:1
[C]:2
[A]:6,5,4,1
--no.6--
[C]->[B]:2
[C]:empty
[B]:3,2
--no.7--
[A]->[B]:1
[A]:6,5,4
[B]:3,2,1
--no.8--
[A]->[C]:4
[A]:6,5
[C]:4
--no.9--
[B]->[C]:1
[B]:3,2
[C]:4,1
--no.10--
[B]->[A]:2
[B]:3
[A]:6,5,2
--no.11--
[C]->[A]:1
[C]:4
[A]:6,5,2,1
--no.12--
[B]->[C]:3
[B]:empty
[C]:4,3
--no.13--
[A]->[B]:1
[A]:6,5,2
[B]:1
--no.14--
[A]->[C]:2
[A]:6,5
[C]:4,3,2
--no.15--
[B]->[C]:1
[B]:empty
[C]:4,3,2,1
--no.16--
[A]->[B]:5
[A]:6
[B]:5
--no.17--
[C]->[A]:1
[C]:4,3,2
[A]:6,1
--no.18--
[C]->[B]:2
[C]:4,3
[B]:5,2
--no.19--
[A]->[B]:1
[A]:6
[B]:5,2,1
--no.20--
[C]->[A]:3
[C]:4
[A]:6,3
--no.21--
[B]->[C]:1
[B]:5,2
[C]:4,1
--no.22--
[B]->[A]:2
[B]:5
[A]:6,3,2
--no.23--
[C]->[A]:1
[C]:4
[A]:6,3,2,1
--no.24--
[C]->[B]:4
[C]:empty
[B]:5,4
--no.25--
[A]->[B]:1
[A]:6,3,2
[B]:5,4,1
--no.26--
[A]->[C]:2
[A]:6,3
[C]:2
--no.27--
[B]->[C]:1
[B]:5,4
[C]:2,1
--no.28--
[A]->[B]:3
[A]:6
[B]:5,4,3
--no.29--
[C]->[A]:1
[C]:2
[A]:6,1
--no.30--
[C]->[B]:2
[C]:empty
[B]:5,4,3,2
--no.31--
[A]->[B]:1
[A]:6
[B]:5,4,3,2,1
--no.32--
[A]->[C]:6
[A]:empty
[C]:6
--no.33--
[B]->[C]:1
[B]:5,4,3,2
[C]:6,1
--no.34--
[B]->[A]:2
[B]:5,4,3
[A]:2
--no.35--
[C]->[A]:1
[C]:6
[A]:2,1
--no.36--
[B]->[C]:3
[B]:5,4
[C]:6,3
--no.37--
[A]->[B]:1
[A]:2
[B]:5,4,1
--no.38--
[A]->[C]:2
[A]:empty
[C]:6,3,2
--no.39--
[B]->[C]:1
[B]:5,4
[C]:6,3,2,1
--no.40--
[B]->[A]:4
[B]:5
[A]:4
--no.41--
[C]->[A]:1
[C]:6,3,2
[A]:4,1
--no.42--
[C]->[B]:2
[C]:6,3
[B]:5,2
--no.43--
[A]->[B]:1
[A]:4
[B]:5,2,1
--no.44--
[C]->[A]:3
[C]:6
[A]:4,3
--no.45--
[B]->[C]:1
[B]:5,2
[C]:6,1
--no.46--
[B]->[A]:2
[B]:5
[A]:4,3,2
--no.47--
[C]->[A]:1
[C]:6
[A]:4,3,2,1
--no.48--
[B]->[C]:5
[B]:empty
[C]:6,5
--no.49--
[A]->[B]:1
[A]:4,3,2
[B]:1
--no.50--
[A]->[C]:2
[A]:4,3
[C]:6,5,2
--no.51--
[B]->[C]:1
[B]:empty
[C]:6,5,2,1
--no.52--
[A]->[B]:3
[A]:4
[B]:3
--no.53--
[C]->[A]:1
[C]:6,5,2
[A]:4,1
--no.54--
[C]->[B]:2
[C]:6,5
[B]:3,2
--no.55--
[A]->[B]:1
[A]:4
[B]:3,2,1
--no.56--
[A]->[C]:4
[A]:empty
[C]:6,5,4
--no.57--
[B]->[C]:1
[B]:3,2
[C]:6,5,4,1
--no.58--
[B]->[A]:2
[B]:3
[A]:2
--no.59--
[C]->[A]:1
[C]:6,5,4
[A]:2,1
--no.60--
[B]->[C]:3
[B]:empty
[C]:6,5,4,3
--no.61--
[A]->[B]:1
[A]:2
[B]:1
--no.62--
[A]->[C]:2
[A]:empty
[C]:6,5,4,3,2
--no.63--
[B]->[C]:1
[B]:empty
[C]:6,5,4,3,2,1

Process finished with exit code 0