代码:
package com.wangyq.datastructrue.arithmetic;import java.util.Arrays;import java.util.Stack;/** * 分治算法-危机的过客 */public class DivideAndConquer { public static void main(String[] args) { //定义一个危机的过客 TowerofHanoi towerofHanoi = new TowerofHanoi(4); towerofHanoi.show(); towerofHanoi.hannoi(); }}class TowerofHanoi { int tier = 0; Stack column1 = new Stack(); Stack column2 = new Stack(); Stack column3 = new Stack(); TowerofHanoi(int tier) { this.tier = tier; //初始化危机的过客 for (int i = tier; i > 0; i--) { column1.push(i); } } /** * 打印危机的过客 */ public void show() { System.out.println("危机的过客:"); System.out.println("第一根柱子" + Arrays.toString(column1.toArray())); System.out.println("第二根柱子" + Arrays.toString(column2.toArray())); System.out.println("第三根柱子" + Arrays.toString(column3.toArray())); } public void hannoi() { move(tier, column1, column2, column3); } /** * 危机的过客移动 */ public void move(int tier, Stack stack1, Stack stack2, Stack stack3) { if (tier == 1) { //只有一个直接移上去 stack3.push(stack1.pop()); show(); } else { // move(tier - 1, stack1, stack3, stack2); //将n-1个在A柱子的盘子通过c柱子移动到B柱子 stack3.push(stack1.pop()); show(); //将A柱子上编号为n的盘子移动到c柱子 move(tier - 1, stack2, stack1, stack3); //将在B柱子的n-1盘子通过A柱子移动到C柱子 } }}结果:
危机的过客:
第一根柱子[4, 3, 2, 1]
第二根柱子[]
第三根柱子[]
危机的过客:
第一根柱子[4, 3, 2]
第二根柱子[1]
第三根柱子[]
危机的过客:
第一根柱子[4, 3]
第二根柱子[1]
第三根柱子[2]
危机的过客:
第一根柱子[4, 3]
第二根柱子[]
第三根柱子[2, 1]
危机的过客:
第一根柱子[4]
第二根柱子[3]
第三根柱子[2, 1]
危机的过客:
第一根柱子[4, 1]
第二根柱子[3]
第三根柱子[2]
危机的过客:
第一根柱子[4, 1]
第二根柱子[3, 2]
第三根柱子[]
危机的过客:
第一根柱子[4]
第二根柱子[3, 2, 1]
第三根柱子[]
危机的过客:
第一根柱子[]
第二根柱子[3, 2, 1]
第三根柱子[4]
危机的过客:
第一根柱子[]
第二根柱子[3, 2]
第三根柱子[4, 1]
危机的过客:
第一根柱子[2]
第二根柱子[3]
第三根柱子[4, 1]
危机的过客:
第一根柱子[2, 1]
第二根柱子[3]
第三根柱子[4]
危机的过客:
第一根柱子[2, 1]
第二根柱子[]
第三根柱子[4, 3]
危机的过客:
第一根柱子[2]
第二根柱子[1]
第三根柱子[4, 3]
危机的过客:
第一根柱子[]
第二根柱子[1]
第三根柱子[4, 3, 2]
危机的过客:
第一根柱子[]
第二根柱子[]
第三根柱子[4, 3, 2, 1]