什么是分治算法呢？ 对于一个规模为n的问题，若该问题可以容易地解决(比如说规模n较小)，则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题， 然后将各子问题的解合并，得到原问题的解。这种算法设计策略叫做分治法(divide and conquer)。
分治算法引用的条件
①该问题可以分解成若干相互独立、规模较小的相同子问题；
②子问题缩小到一定的程度就能轻易得到解；
③子问题的解合并后，能得到原问题的解；
分治法三步：
(1) 划分(divide)：将原问题分解为若干规模较小、 相互独立、 与原问题形式相同的子问题。
(2) 解决(conquer)： 若子问题规模较小，则直接求解；否则递归求解各子问题。
(3) 合并(combine)： 将各子问题的解合并为原问题的解。
if(问题不可分)
{ 直接求解；
返回问题的解；
}
else {
对原问题进行分治；
递归对每一个分治的部分求解;
归并整个问题，得出全问题的解；
}
例题：给n个实数，求它们之中最大值和最小值，要求比较次数尽量小。
使用分治的方法解决思路：
首先这是一个问题n的题，当n=1时，最大值与最小时不用求，就是数本身，当n=2时，最大最小直接比较可以求得。
那么我们可以将数据进行分割为只有两个元素的可求状态，最后再将其合并。
public static void main(String[] args) {
int[] seq = {1,5,6,9,5,2,9,10,18,3};
Main main = new Main();
int end = seq.length - 1;
int[] res = main.DC_maxmin(seq,0,end);
for (int a :res) {
System.out.println(a);
}
}
public int[] setTwo(int a , int b) {
int[] res = new int[2];
//保证这个集合中的数值一定是前小后大
if (a > b) {
res[0] = b;
res[1] = a;
} else {
res[0] = a;
res[1] = b;
}
return res;
}
public int[] DC_maxmin(int[] seq,int start,int end){
//如果序列中只有一个元素
if(end-start==0){
return setTwo(seq[start],seq[start]);
}
else if(end-start==1){
return setTwo(seq[start],seq[end]);
}else {
//否则进行迭代切分
int[] left_seq = DC_maxmin(seq, start, (start + end) / 2);
int[] right_seq = DC_maxmin(seq, (start + end) / 2 + 1, end);
int[] res = new int[2];
if(left_seq[0]<right_seq[0]){
res[0] = left_seq[0];
}else{
res[0] = right_seq[0];
}
if(left_seq[1]<right_seq[1]){
res[1] = right_seq[1];
}else{
res[1] = left_seq[1];
}
return res;
}
}
把一个包含n个正整数的序列划分成m个连续的子序列(每个正整数恰好属于一个序列)。设第i个序列的各数之和为S(i)，你的任务是让所有的S(i)的最大值尽量小。例如序列1 2 3 2 5 4划分成3个序列的最优方案为1 2 3|2 5|4，其中S(1)=6，S(2)=7，S(3)=4，最大值为7；如果划分成1 2|3 2|5 4，则最大值为9；不如刚才的好。n<=106，所有数字之和不超过109。
#include <cstdio>
int prime[664590];
bool check[10000102];
int process(int N) {
int tot = 0;
for(int i=2 ; i<=N ; ++i){
if (! check[i]) prime[tot++] = i;
for(int j=0 ; j<tot ; j++) {
if(i * prime[j] > N) break;
check [i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
return tot;
}
int main() {
process(10000020);
int n, tmp;
scanf("%d", &n);
while (n--) {
scanf("%d", &tmp);
if (tmp <= 2) puts("2");
else {
int l = 0, r = 664579, mid;
while (l < r) {
mid = l + r >> 1;
if (prime[mid] >= tmp) r = mid;
else l = mid + 1;
}
if (tmp - prime[l - 1] < prime[l] - tmp) printf("%d\n", prime[l - 1]);
else printf("%d\n", prime[l]);
}
}
return 0;
}
