分治算法详细讲解（含经典例题分析）.pdfVIP

分治算法详细讲解（含经典例题分析）

分治法思路：

将整个问题分解成若⼲⼩问题后再分⽽治之如果分解得到的⼦问题相对来说还是太⼤，则可反复使⽤分治策略将这些⼦问题分成更⼩的同

类型⼦问题，直⾄产⽣⽅便求解的⼦问题，必要时逐步合并这些⼦问题的解，从⽽得到问题的解

分治算法可以由递归过程来表⽰，因为分治法就是⼀种找⼤规模问题与⼩规模问题关系的⽅法，是递归设计的⼀种具体策略

步骤

1.分解

将原问题分解为若⼲规模较⼩，相互独⽴，与原问题相同的⼦问题

2.解决

若⼲⼦问题较⼩⽽容易被解决则直接解决，否则再继续分解为更⼩的⼦问题，直到容易解决

3.合并

将已求解的各个⼦问题的解，逐步合并为原问题的解

有的问题分解后不需要合并⼦问题的解，此时就不需要再做第3步了多数问题需要⼦问题的解，按照题意使⽤恰当的⽅法合并成为整个问

题的解需要具体问题具体分析

算法框架

分治法的⼀般算法设计模式如下：

Divide-and-Conquer(intn){

if(n=n0){//n为问题规模,n0为可解⼦问题的规模

解⼦问题;

return(⼦问题的解);

}

for(i=1;i=k;i++){//分解成较⼩的⼦问题p1,p2,...,pk

yi=Divide-and-Conquer(|Pi|);//递归解决

}

T=ERGE(y1,y2,...yk);//合并⼦问题

return(T);//返回问题的解

}

典型⼆分法

（⼀）

在算法设计中，每次⼀个问题分解成的⼦问题个数⼀般是固定的，每个⼦问题的规模也是平均分配的当每次都将问题分解为原问题规模的

⼀半时，称为⼆分法

⼆分法是分治法较常⽤的分解策略，数据结构课程中的折半查找、归并排序等算法都是采⽤此策略实现的

问题：⾦块问题

⽼板有⼀袋⾦块（共n块），最优秀的雇员得到其中最重的⼀块，最差的雇员得到其中最轻的⼀块，假设有⼀台⽐较重量的仪器，我们希望

⽤最少的⽐较次数找出最重的⾦块

⽅法1：逐个查找⽐较

最简单的⽅就是逐个的⽐较查找，算法类似于选择排序先拿两块进⾏⽐较，留下最重的与下⼀块⽐较，直到全部⽐较完毕就找到了最重的

⾦⼦

完整代码如下：

//⾦块算法1：逐个查找⽐较

#includestdio.h

intmain(){

voidmaxmin(floata[],intn);//定义查找⽐较的函数

floata[5]={5,3,1,9,0};

inti;

maxmin(a,5);

return0;

}

voidmaxmin(floata[],intn){

floatmax,min;

inti;

intcount=0;

max=min=a[0];

for(i=1;in;i++){

if(maxa[i]){//记录每次⽐较重量最⼤的⾦块

max=a[i];

count++;

}

if(mina[i]){//记录每次⽐较重量最⼩的⾦块

min=a[i];

count++;

}

}

printf(max=%.2f\nmin=%.2f\ncount=%d\n,max,min,count);//输出结果

}

⽅法2：分治法（⼆分法）

1.将数据等分为两组（两组数据可能差1），⽬的是分别选取其中最⼤值（最⼩值）

2.递归分解直到每组元素的个数不⼤于2，可简单的找到最⼤值（最⼩值）

3.回溯时将分解的两组解⼤者取⼤，⼩者取⼩

⽤分治法可以⽤较少的⽐较次数解决问题

完整代码如下：

//⾦块算法2:运⽤递归实现分半查询

#includestdio.h

floata[5]={3,6,9,2,5};

intmain(){

voidmaxmin(inti,intj,floatfmax,floatfmin,intcount);//fmax的地址,fmin的地址

floatfmax=0,fmin=0;

intcount=0;

maxmin(0,4,fmax,fmin,count);

//传递地址是为了能够把值带出来

printf(fmax=%f\nfmin=%f\ncount=%d\n,fmax,fmin,