什么是分治算法呢？ 對于一個規(guī)模為n的問題，若該問題可以容易地解決(比如說規(guī)模n較小)隘弊，則直接解決，否則將其分解為k個規(guī)模較小的子問題荒适，這些子問題互相獨立且與原問題形式相同梨熙，遞歸地解這些子問題， 然后將各子問題的解合并刀诬，得到原問題的解咽扇。這種算法設(shè)計策略叫做分治法(divide and conquer)。
分治算法引用的條件
①該問題可以分解成若干相互獨立、規(guī)模較小的相同子問題质欲；
②子問題縮小到一定的程度就能輕易得到解树埠；
③子問題的解合并后，能得到原問題的解嘶伟；
分治法三步：
(1) 劃分(divide)：將原問題分解為若干規(guī)模較小怎憋、 相互獨立、 與原問題形式相同的子問題九昧。
(2) 解決(conquer)： 若子問題規(guī)模較小绊袋，則直接求解；否則遞歸求解各子問題铸鹰。
(3) 合并(combine)： 將各子問題的解合并為原問題的解癌别。
if(問題不可分)
{ 直接求解；
返回問題的解蹋笼；
}
else {
對原問題進行分治规个；
遞歸對每一個分治的部分求解;
歸并整個問題，得出全問題的解姓建；
}
例題：給n個實數(shù)诞仓，求它們之中最大值和最小值，要求比較次數(shù)盡量小速兔。
使用分治的方法解決思路：
首先這是一個問題n的題墅拭，當(dāng)n=1時，最大值與最小時不用求涣狗，就是數(shù)本身谍婉，當(dāng)n=2時，最大最小直接比較可以求得镀钓。
那么我們可以將數(shù)據(jù)進行分割為只有兩個元素的可求狀態(tài)穗熬，最后再將其合并。
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];
//保證這個集合中的數(shù)值一定是前小后大
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個正整數(shù)的序列劃分成m個連續(xù)的子序列(每個正整數(shù)恰好屬于一個序列)丁溅。設(shè)第i個序列的各數(shù)之和為S(i)唤蔗，你的任務(wù)是讓所有的S(i)的最大值盡量小。例如序列1 2 3 2 5 4劃分成3個序列的最優(yōu)方案為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掘殴，所有數(shù)字之和不超過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;
}
