美文网首页
汉诺塔-Java实现

汉诺塔-Java实现

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

    汉诺塔总步数: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
    
    

    相关文章

      网友评论

          本文标题:汉诺塔-Java实现

          本文链接:https://www.haomeiwen.com/subject/vlchuftx.html