# 分治算法

# 什么是分治算法

『 分治算法 divide & conquer 』的核心思想是 “分而治之“，也就是将原问题划分成 n 个规模较小，并且结构与原问题相同的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

( Divide & Conquer 的中文意思就是，拆分开来，逐个击破 )

关于分治和递归的区别，分治算法是一种 “处理问题的思想”，递归是一种 “编程技巧”。分治算法一般都是用递归来实现。

分治算法的递归实现中，每一层递归都会涉及这样三个操作：

分解：将原问题分解成一系列子问题；
解决：递归地求解各个子问题；
合并：将子问题的结果合并成原问题。

2020-08-17-12-02-51

分治算法能解决的问题，一般需要满足下面这几个条件：

原问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；
原问题分解成的子问题可以独立求解，子问题之间没有相关性；
具有分解终止条件，也就是说，当问题足够小时，就不需要再分解了，可以直接求解；
可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

# 二分查找

二分查找就利用了分治思想缩小查找范围。

public static int binary_search(int[] a, int target) {
  int low = 0;
  int high = a.length - 1;
  int mid;

  while (low <= high) {
    mid = (high + low) / 2;

    if (a[mid] == target) {
      return mid;
    } else if (a[mid] < target) {
      low = mid;
    } else {
      high = mid;
    }
  }

  return -1;
}

# 归并排序

采用分治思想, 将原始数组切分成较小的数组，直到每个小数组只有一个项；
接着将小数组归并成较大的数组，归并的时候将两个小数组排序成一个顺序的大数组；
直到最后只有一个排序完毕的大数组；

public static int[] bucket_sort(int[] arr, int bucketSize) throws Exception {

  if (arr.length == 0) {
    return arr;
  }

  // 找到数组中的 “最大值” 和 “最小值”
  int minValue = arr[0];
  int maxValue = arr[0];
  for (int i = 0; i < arr.length; i++) {
    int value = arr[i];
    if (value < minValue) {
      minValue = value;
    } else if (value > maxValue) {
      maxValue = value;
    }
  }
  // 创建桶
  // 注意：因为是整数除法，等于进行了 floor 操作，所以要在结果加 1
  int bucketCount = (maxValue - minValue) / bucketSize + 1;
  int[][] buckets = new int[bucketCount][0];
  // 利用映射函数将数据分配到各个桶中
  for (int i = 0; i < arr.length; i++) {
    int index = (arr[i] - minValue) / bucketSize;
    buckets[index] = arr_append(buckets[index], arr[i]);
  }

  int arrIndex = 0;
  for (int j = 0; j < buckets.length; j++) {
    int[] bucket = buckets[j];

    // 如果桶是空的，就直接跳过
    if (bucket.length <= 0) {
      continue;
    }
    // 对每个桶进行排序，这里使用了快速排序
    quick_sort(bucket, bucket.length);
    for (int k = 0; k < bucket.length; k++) {
      int value = bucket[k];
      arr[arrIndex] = value;
      arrIndex++;
    }
  }

  return arr;
}

// 自动扩容，并保存数据
public static int[] arr_append(int[] arr, int value) {
  arr = Arrays.copyOf(arr, arr.length + 1);
  arr[arr.length - 1] = value;
  return arr;
}

# 汉诺塔

# 问题描述

汉诺塔游戏中，有三根杆子 A，B，C。A 杆上有 n 个穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

每次只能移动一个圆盘；
大盘不能叠在小盘上面；
可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

请问该怎么移动？

# 问题分析

如果现在在塔 A 上面只有 1 个圆盘，那么直接把圆盘移动到塔 C 即可；
如果现在在塔 A 上面有 2 个圆盘，那么先把圆盘 1 从塔 A 移动到塔 B，再把圆盘 2 从塔 A 移动到塔 C，最后把圆盘 1 从塔 B 移动到塔 C；
$……$
如果塔 A 有 n 个圆盘，那么需要先把圆盘 n 之前的（n-1 ~ 1）从塔 A 先移动到塔 B，再把圆盘 n 从塔 A 移动到塔 C，最后把放在塔 B 的（n-1 ~ 1）从塔 B 移动到塔 C；

👆 上面的解法是很典型的分治法算法思想。

# 代码实现

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);
  }
}

public static void move(int n, String sourceTower, String targetTower) {
  System.out.println("第" + n + "号盘子 move:" + sourceTower + "--->" + targetTower);
}

输出结果：

hanoi(3, "a", "b", "c");

第1号盘子 move:a--->c
第2号盘子 move:a--->b
第1号盘子 move:c--->b
第3号盘子 move:a--->c
第1号盘子 move:b--->a
第2号盘子 move:b--->c
第1号盘子 move:a--->c