分治思想

分治算法适宜用很重要的算法，字面上的解释是“分而治之”，就是把一个复杂的问题分解为两个或更多相同或相似的自问题，再把子问题分解成更小的自问题。。。。。。直到最后子问题可以简单的直接求解，原问题的解即子问题解的合并。这个技巧是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）。。。。。。

分治算法可以求解一些经典问题

  • 二分搜索
  • 大整数乘法
  • 棋盘算法
  • 归并排序
  • 快速排序
  • 线性时间选择
  • 最接近点对问题
  • 循环赛日程表
  • 汉诺塔

汉诺塔

image.png

  1. function hannuoTower(num, a, b, c) {
  2.   if (num === 1) return console.log(`把${a}盘移动到${c}盘`);
  3.   // 1、把最上面的盘从A盘移动到B盘, 会使用到C盘
  4.   hannuoTower(num - 1, a, c, b);
  5.   // 2、 把最下面的盘 A移动到C
  6.   console.log(`把${a}盘移动到${c}盘\n`);
  7.   // 3、 把B上面的所有盘移动到C盘
  8.   hannuoTower(num - 1, b, a, c);
  9. }
  11. hannuoTower(5, 'A', 'B', 'C');