分治¶
前置知识¶
递归
目标¶
分治的概念，典型题目
What¶
在计算机科学中，分治法（英语：Divide and conquer）是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
How¶
分治算法是一个解决复杂问题的好工具，比如，汉诺塔问题如果采用分治算法，可以把高度为 n 的塔的问题转换成高度为 n-1 的塔来解决，如此重复，直至问题化简到可以很容易的处理为止。
在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
- 解决：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
- 合并：将各子问题的解合并为原问题的解。
例题，1326：【例7.5】 取余运算（mod）¶
题意，求 a^b mod p
#include <bits/stdc++.h>
using namespace std;
int a, b, p;
int qmi(int a, int b, int p) {
if (b == 0) return 1;
int t = qmi(a, b / 2, p);
if (b & 1) return 1ll * t * t * a % p;
return 1ll * t * t % p;
}
int main() {
cin >> a >> b >> p;
printf("%d^%d mod %d=%d\n", a, b, p, qmi(a, b, p));
return 0;
}
例题，1205：汉诺塔问题¶
题意，经典汉诺塔问题，输出每一步移动盘子的步骤
#include <bits/stdc++.h>
using namespace std;
// n个盘子，现在，辅助，目标
void f(int n, int a, int b, int c) {
if (!n) return ;
f(n - 1, a, c, b);
printf("%c->%d->%c\n", a, n, c);
f(n - 1, b, a, c);
}
int main() {
int n;
char a, b, c;
cin >> n >> a >> b >> c;
f(n, a, c, b);
return 0;
}
例题，P1177 【模板】排序¶
题意，从小到大排序，使用归并排序
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], n;
int tmp[N];
void merge_sort(int q[], int l, int r) {
if (l >= r) return ;
int mid = (l + r) >> 1;
merge_sort(q, l, mid); merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
while (i <= mid) tmp[k++] = q[i++];
while (j <= r) tmp[k++] = q[j++];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}
题单¶
P1115 最大子段和（使用分治实现）
总结¶
Divide and conquer，分而治之，在以前打仗，一起打不好打，就分开打，一个一个消灭，就是这样的思路。
分治，是一个重要的算法思想，其有一个特点是，子问题不重叠，需认真分析这个性质，后续学习会用到。