分治 - 简书

什么是分治算法呢？对于一个规模为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<=10^{6，所有数字之和不超过10}9。

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

分治

分治算法引用的条件

例题：给n个实数，求它们之中最大值和最小值，要求比较次数尽量小。

推荐阅读更多精彩内容