package com.iflytek.hanluo;

import java.util.Stack;

public class HLTower {
public static Stack stack = new Stack();
public static void recursion(int count,Pillar pillarA, Pillar pillarC, Pillar pillarB){
if(count == 1){
System.out.println(pillarA.name + " -> " + pillarC.name);
}else{
HLTower.recursion(count - 1, pillarA, pillarB, pillarC);
System.out.println(pillarA.name + " -> " + pillarC.name);
HLTower.recursion(count - 1, pillarB, pillarC, pillarA);
}
}

public static void nonRecursion(Node node){
if(node.count > 0)
stack.push(node);
while(!stack.isEmpty()){

while(node.count > 1){
node = new Node(node.count - 1, node.from, node.mid, node.to);
stack.push(node);
}

if(node.count == 1){
//弹出叶子节点
Node popNode = stack.pop();
System.out.println(popNode.from + " - > " + popNode.to);
}
//弹出非叶子节点
if(!stack.isEmpty()){
node = stack.pop();
System.out.println(node.from + " - > " + node.to);
node = new Node(node.count - 1, node.mid, node.to, node.from);
stack.push(node);
}
}
}

public static void main(String[] args){
HLTower.recursion(3, new Pillar('A'), new Pillar('C'), new Pillar('B'));
System.out.println("------------------------");
HLTower.nonRecursion(new Node(3, 'A', 'C', 'B'));
}

}

package com.iflytek.hanluo;

public class Node {
public int count;
public char from;
public char to;
public char mid;

public Node(int count, char from, char to, char mid) {
this.count = count;
this.from = from;
this.mid = mid;
this.to = to;
}
}

package com.iflytek.hanluo;

public class Pillar {
public char name;

public Pillar(char name){
this.name = name;
}

}

ITPub博客

汉诺塔递归与非递归实现

最新文章