什么是分治算法？( 三 ) _分治算法

③ 如果有 3 个盘子，那么根据 2 个盘子的结论，可以借助 C 将盘子 3 上的两个盘子从 A 移动到 B ；将盘子 3 从 A 移动到 C，A 变成空座；借助 A 座，将 B 上的两个盘子移动到 C。

④ 以此类推，上述的思路可以一直扩展到 n 个盘子的情况，将将较小的 n-1个盘子看做一个整体，也就是我们要求的子问题，以借助 B 塔为例，可以借助空塔 B 将盘子A上面的 n-1 个盘子从 A 移动到 B ；将A 最大的盘子移动到 C，A 变成空塔；借助空塔 A，将 B 塔上的 n-2 个盘子移动到 A，将 C 最大的盘子移动到 C，B 变成空塔。。。

代码实现：
public static void hanoi(int n, String sourceTower, String tempTower, String targetTower) { if (n == 1) { //如果只有一个盘子1，那么直接将其从sourceTower移动到targetTower move(n, sourceTower, targetTower); } else { //将（盘子n-1~盘子1）由sourceTower经过targetTower移动到tempTower hanoi(n - 1, sourceTower, targetTower, tempTower); //移动盘子n由sourceTower移动到targetTower move(n, sourceTower, targetTower); //把之前移动到tempTower的（盘子n-1~盘子1），由tempTower经过sourceTower移动到targetTower hanoi(n - 1, tempTower, sourceTower, targetTower); } } //盘子n的从sourceTower->targetTower的移动 private static void move(int n, String sourceTower, String targetTower) { System.out.println("第" + n + "号盘子 move:" + sourceTower + "--->" + targetTower); }7 总结分析
分治法将规模为 n 的问题分成 k 个规模为 n／m 的子问题去解。设分解阀值 n0 = 1，且 adhoc 解规模为 1 的问题耗费 1 个单位时间。再设将原问题分解为 k 个子问题以及用 merge 将 k 个子问题的解合并为原问题的解需用 f(n) 个单位时间。用T(n)表示该分治法解规模为 |P| = n 的问题所需的计算时间，则有：
T（n）= k T(n/m) + f(n)