分治算法之汉诺塔问题

分治法在每一层递归上都有三个步骤

1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2. 解决：若子问题规模较小而容易被解决则直接解决，否则递归的解各个子问题
3. 合并：将各个子问题的解合并为原问题的解

汉诺塔问题描述

有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

public class HanoiTower {

  public static void main(String[] args) {

  }

  public static void hanoiTower(int num, char a, char b, char c) {
    if (num == 1) {
      System.out.println("第一个盘从" + a + "->" + c);
    } else {
      // 如果我们有n>=2情况，我们总是可以看做是两个盘，1.最下边的一个盘 2.上边所有盘
      // 1.先把最上边的所有盘A -> B，移动过程会用到c
      hanoiTower(num - 1, a, c, b);
      // 2. 把最下边的盘A->C
      System.out.println("第" + num + "个盘从" + a + "->" + c);
      // 3. 把B所有盘从B->C，移动过程使用A
      hanoiTower(num - 1, b, a, c);
    }
  }
}