场景：三个柱子，左边从小到大排列，要把左边的全部移动到右边
规则：移动必须要经过中间的柱子，任何柱子上不能违反从小到大排列的规则，打印移动过程和最优移动总步数。
有两种解法：
其中递归的解法如下：
左边移动思路：想要移动最底下的到中间，就要移动上一个，依次递推，直到最上边的就可以移动到中间，然后要把右边的移动到左边，这样可以使当初移动到中间的那个移动到右边。右边的移动到左边也是左边移动思路的应用。
public class SortHanoi {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
Stack<Integer> stack3 = new Stack<Integer>();
int num = 0;
public static void main(String[] args) {
SortHanoi sortHanoi = new SortHanoi();
sortHanoi.method1(2);
System.out.println("it will move "+sortHanoi.num+" steps");
}
private void initHanoi(int tier) {
for (int i = tier; i > 0; i--) {
stack1.push(i);
}
}
private void method1(int tier) {
initHanoi(tier);
moveLeftToRight(tier);
}
private void moveLeftToRight(int level) {
if(level==1) {
move123();
return;
}else {
moveLeftToRight(level-1);
move12();
int rightLevel = stack3.size();
moveRightToLeft(rightLevel);
move23();
moveLeftToRight(rightLevel);
}
}
private void moveRightToLeft(int level) {
if(level==1) {
move321();
return;
}else {
moveRightToLeft(level-1);
move32();
moveLeftToRight(level-1);
move21();
moveRightToLeft(level-1);
}
}
private void move21() {
stack1.push(stack2.pop());
num++;
System.out.println("move "+stack1.peek()+" from mid to left");
}
private void move32() {
stack2.push(stack3.pop());
num++;
System.out.println("move "+stack2.peek()+" from right to mid");
}
private void move23() {
stack3.push(stack2.pop());
num++;
System.out.println("move "+stack3.peek()+" from mid to right");
}
private void move12() {
stack2.push(stack1.pop());
num++;
System.out.println("move "+stack2.peek()+" from left to mid");
}
private void move321() {
move32();
move21();
}
private void move123() {
move12();
move23();
}
}
////TODO 只有一个的时候
//move123();
////TODO 只有两个的时候
//move12();
//
//move23();
////TODO 只有三个的时候
//move12();
// // 右边清空
// move32();
// move21();
//
//move23();
// //左边清空
// move12();
// move23();
//
////TODO 只有四个的时候
//move12();
// // 右边清空
// move32();
// move21();
// move32();
// move12();
// move23();
// move21();
// move32();
// move21();
//
//move23();
// //左边清空
// move12();
// move23();
// move12();
// move32();
// move21();
// move23();
// move12();
// move23();
另外一种是书中提供的：
移动有四种可能，左右到中，或者中到左右。移动有两个规则，第一，不能反向，没有意义。第二，不能大压小，多以这样直接排除了两步。下一步就是比较剩下的两步哪一个没有违反这两个规则。这样从第一步开始，以后的每一步其实都是确定的了。
第二种排除思路是很有借鉴性的
在解决这个问题的时候，不能用常规的思路去推导移动的规律，这是这个算法问题的难点，也是这个算法问题的核心之处。