算法系统学习-大事化小,小事化了(分而治之)

发布时间:2022-08-19 11:35

分而治之算法

主要的设计思想是:将一个难以解决的大问题,分割成几个规模较小的相似问题,逐个击破。其实这个算法并不陌生,在数据结构中很常见例如:折半查找,合并排序,快速排序,二叉树遍历(先左后右),二叉树排序树的查找算法。

算法思路:

可以用一个递归过程表示,分治法就是一种大规模问题与小规模问题关系的方法,是递归设计方法的一种具体策略,分治法在每一层递归上一般分为三个步骤:

1、分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题

2、解决:若子问题规模较小而容易被解决,则直接解决,否则再继续分解成更小规模的问题,直到容易解决

3、合并:将已求解的各个子问题的解,逐步合并成原问题的解

常见分为等分分治法和非等分治法

二分法

不同于现实中对问题的分解,需要考虑问题的重点,难点,承担人员的能力等来进行问题的分解和分配,在算法设计中每次一个问题分解成的子问题个数的一般是固定的,每个子问题的规模也是平均分配的。当每次都将问题分解成原问题的一半时,称为 二分法。 (二分法是分治法较为常用分解策略,折半查找,归并排序等算法都是采用此策略实现的)

Case1:金块问题

老板有一袋金块(共n块)。最优秀的雇员得到其中的最重的一块,最差的雇员得到最轻的一块,假设有一台比较重量的仪器,请使用最少的比较次数找出最重的金块

算法分析:

比较简单的方法是逐个进行查找,先拿两块比较重量,留下重的一个与下一块比较,直到全部比较完毕,就找到了最重的金子。(类似于选择排序)

算法设计:

maxmin(float a[],int n){
	max ==min =a[1];
    for(i=2;i<=n;i++){
        if(maxa[i]){
            min=a[i];
        }
    }
}
复制代码

算法中需要n-1次比较从而得到max,

最好的情况是金块是由小到大取出的,不需要进行与min的比较,共进行n-1次比较,

最坏的情况是金块由大到小取出的,需要再经过n-1次比较得到min,共进行2n-2次比较的

至于在平均的情况下,a(i)将有一般的时间比max大,因此平均比较数是 3(n-1)/2


Case2:求数列的最大子段和(不独立子问题)

给定n个元素的整数列(可能为负整数)a1,a2....an求形如:ai,ai+1,....aj(i,j=1.....n,i<=j)的子段,使其和为最大。当所有整数均为负整数时定义其最大子段和为0。例如当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为i=2,j=4(下标从1开始)

问题分析:

若用二分法将实例中的数据分解成两组(-2,11,-4)和(13,-5,-2),第一个子问题的解是11,第二个子问题的解是13,两个子问题的解不能简单地得到问题的解。由此看出这个问题不能用二分法分解成为独立的两个子问题,子问题中间还有公共的子问题,这类问题称为子问题重叠类的问题。那么,怎样解决这类问题呢?(不独立子问题)

算法分析:

分解方法还是用二分法,虽然分解后的子问题并不独立,但通过对重叠的子问题进行专门处理,并对所有的问题合并进行设计,就可以用二分法策略解决问题。

如果将所给的序列a【1:n】分为长度相等的两段a【1 :(n/2)】和a【(n/2)+1:n】分别求出这两段的最大子段和,则a【1:n】的最大子段和有三种情形:

  1. a【1:n】的最大子段和与a[1:(n/2)]的最大子段和相同
  2. a【1:n】的最大子段和与a[(n/2)+1:n]的最大子段和相同
  1. a【1:n】的最大子段和与a[i:j],且1≤i≤(n/2), (n/2)+1≤j≤n;

对于情况1,2可分别递归求得。但是对于情况3,a[(n/2)] 和a[(n/2)+1]一定在最优的子序列中,因此可得a[i:(n/2)]的最大值s1,并计算出a[(n/2)+1:j]中的最大值s2,则情况3的最优值为 s1+s2

算法设计:


int max_sum3 (int a[],int n)
{
return (max_sub_sum (a,1,n));
}
 
max_sub_sum(int a [],int left,int right){
int center,i,j,sum,left_sum,right_sum,s1,s2,lefts,rights;
    if(left =right){
    	if(a[left]>0){
            return(a[left]);
            
    	}else{
        return (0);
        }
    }else{
    center =(left +right )/2;
        left_sum=max_sub_sum(a,left,center);
        right_sum=max_sub_sum(a,center+1,right);
        s1=0;
        lefts=0;
        
        for(i=center;i>=left;i--){
            { lefts=lefts+a[i];
             	if(lefts>s1){
                s1=lefts;
                }
            
            }
        s2=0;righs=0;
        for(i=center+1;i<=right;i++){
            rights=rights+a[i];
            	if(rights>s2){
                    s2=rights;
                }
        }
        }
        if(s1+s2


 

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号