一分治算法概述
一分治算法（Divide and Conquer）是一种重要的算法设计策略。
核心思想（基本步骤）：
1、分（Divide）- 分解：
将原问题分解为若干个规模较小的同类型子问题；
2、治（Conquer）- 解决：
递归求解子问题（如果子问题规模足够小，则直接求解）；
3、合（Combine）- 合并：
将子问题的解合并得到原问题的解。
二分治算法经典案例
【描述】汉诺塔（Hanoi Tower），又称河内塔，源于印度的一个古老传说。大梵天创造世界的时候做了3根金刚石柱子，在一根柱子上从下往上按照从大到小的顺序摞着64片黄金圆盘。大梵天命人把圆盘从下往上按照从大到小的顺序重新摆放到另一根柱子上。并且规定，任何时候，在小盘上都不能放大盘，且在3根柱子之前一次只能移动一个圆盘。
【输入】圆盘的数量n（0<n<10）。
【输出】移动圆盘的过程，每一步占一行。
【分析过程】
为了便于描述，给三根柱子分别命名A、B、C，刚开始的时候，圆盘都在A柱上，假设C柱是目标柱子，B柱是辅助柱子。
情形1：如果只有1个圆盘，直接从A柱移到C柱，只需1步。
情形2：如果有2个圆盘，需要把第1个圆盘从A柱移到B柱，再将第2个圆盘从A柱移到C柱，最后将第1个圆盘从B柱移到C柱，总共需要3步。
情形3：如果有3个圆盘，将最上面的2个圆盘看作一个整体，整体部分与最下方圆盘构成情形2。先将整体部分从A柱移到B柱，再将最下方圆盘从A柱移到C柱，最后再将整体部分从B柱移动C柱，总体来看，也需要3步。
由于每次只能移动一个圆盘，所以将整体部分（最上面两个圆盘）从A柱移到B柱，参照情形2，需要3步；再将最下方圆盘从A柱移到C柱，需要1步；最后将整体部分（最上面两个圆盘）从B柱移到C柱，再次参照情形2，需要3步。所以，移动3个圆盘总共需要7步（3+1+3）。
情形4：如果有64个圆盘，将最上面的63个圆盘看作一个整体，整体部分与最下方圆盘构成情形2。将整体从A柱移到B柱，再将最下方圆盘从A柱移到C柱，最后将整体从B柱移到C柱。
如何将整体（最上面的63个圆盘）从A柱移到B柱呢？
继续分而治之，将最上面的62个圆盘看作一个整体，与倒数第二个（第63个）圆盘构成情形2。
62个圆盘还是没法移动，那就继续分而治之，直到圆盘的数量足够少，可以移动为止。
以上就是分治算法的解题思路，可以使用递归函数实现。
【示例程序】
- # include <bits/stdc++.h>
- using namespace std;
- void hanoi(int n, char a, char b, char c) {
- // 情形 1
- if (n == 1) {
- printf("%d: %c -> %c\n", n, a, c); // 将n号圆盘从a柱移到c柱
- return;
- }
- // 情形 2 和 其它情形
- else {
- hanoi(n-1, a, c, b); // 将整体部分从a柱借助c柱移到b柱
- printf("%d: %c -> %c\n", n, a, c); // 将n号圆盘从a柱移到c柱
- hanoi(n-1, b, a, c); // 再将整体部分从b柱借助a柱移到c柱
- }
- }
- int main() {
- int n;
- cin >> n;
- hanoi(n, 'A', 'B', 'C');
- return 0;
- }
注意：
大家在测试的时候，圆盘的数量不要太多，最好不要超过10个圆盘，否则递归函数频繁调用自己，不断地压栈，会导致计算机内存溢出。
通过观察规律，发现移动n个圆盘需要的步数：f(n) = 2^n - 1。
可见，移动次数随着圆盘个数的增加呈指数级增长，千万不要轻易尝试64个圆盘。感兴趣的同学可以计算一下，移动64个圆盘的步数。
【案例二】快速排序
【例题】快速排序
让用户输入的n个整数，使用递归函数实现快速排序（升序排序），请输出第m小的元素。（1<m<n<100）
【示例程序】快速排序
- # include <bits/stdc++.h>
- using namespace std;
- // 在函数之前声明的变量，可供全局使用
- int a[101];
- // 创建递归函数，实现快速排序
- void qucik_sort(int L, int R) {
- int key = a[L]; // 将开始元素作为分界值
- int l = L; // 存储左索引
- int r = R; // 存储右索引
- if (l >= r) return; // 递归终止条件（元素少于2个）
- while (l < r) { // 本轮排序执行条件
- // 1、先从右向左查找小于等于key的元素
- while (a[r] > key && r > l) r--;
- a[l] = a[r]; // 将小元素移到左边
- // 2、再从左向右查找大于key的元素
- while (a[l] <= key && l < r) l++;
- a[r] = a[l]; // 将大元素移到右边
- }
- a[r] = key; // 将分界值存入“中间”位置
- qucik_sort(L, r-1); // 独立排序左边部分
- qucik_sort(r+1, R); // 独立排序右边部分
- }
- int main() {
- int n, m;
- cin >> n >> m;
- for (int i = 1; i <= n; i++) {
- cin >> a[i]; // 输入元素
- }
- qucik_sort(1, n); // 调用快速排序函数排序
- cout << a[m]; // 输出排序后的指定元素
- return 0;
- }
三课后习题
让用户输入的n个整数，查找并输出第m小的元素。（1<m<n<100）
要求：只需找到第m小的元素，无需全部排序。
提示：每轮排序后，左边部分都不超过key，右边元素都大于key，只需要针对目标元素所在的区间排序即可，其它区间无需排序。
【参考代码】区间排序（快速查找）
- # include <bits/stdc++.h>
- using namespace std;
- // 在函数之前声明的变量，可供全局使用
- int a[101];
- // 创建递归函数，实现快速查找（区间排序）
- int qucik_find(int L, int R, int m) {
- int key = a[L]; // 将开始元素作为分界值
- int l = L; // 存储左索引
- int r = R; // 存储右索引
- while (l < r) { // 本轮排序执行条件
- // 1、先从右向左查找小于等于key的元素
- while (a[r] > key && r > l) r--;
- a[l] = a[r]; // 将小元素移到左边
- // 2、再从左向右查找大于key的元素
- while (a[l] <= key && l < r) l++;
- a[r] = a[l]; // 将大元素移到右边
- }
- a[r] = key; // 将分界值存入“中间”位置
- // 创建变量ans存储查找结果
- int ans;
- // 如果m和中间索引相等，这是最理想的情况，直接将key赋值给ans
- if (m == r) ans = key;
- // 如果m小于中间索引，说明目标在左边部分，递归查找左边部分，将结果存入ans
- else if (m < r) ans = qucik_find(L, r-1, m);
- // 如果m大于中间索引，说明目标在右边部分，递归查找右边部分，将结果存入ans
- else ans = qucik_find(r+1, R, m);
- return ans; // 返回查找结果
- }
- int main() {
- int n, m;
- cin >> n >> m;
- for (int i = 1; i <= n; i++) {
- cin >> a[i]; // 输入元素
- }
- // 调用快速查找函数，并输出查找结果
- cout << qucik_find(1, n, m) << endl;
- return 0;
- }
