图片来自网路
汉诺塔总步数：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
