锐客网

  1. 首页 > 睿知 > it技术 > >

【Zeus】算法|算法系统学习-大事化小，小事化了（分而治之）

算法【Zeus】算法

分而治之算法 主要的设计思想是：将一个难以解决的大问题，分割成几个规模较小的相似问题，逐个击破。其实这个算法并不陌生，在数据结构中很常见例如：折半查找，合并排序，快速排序，二叉树遍历（先左后右），二叉树排序树的查找算法。
算法思路： 可以用一个递归过程表示，分治法就是一种大规模问题与小规模问题关系的方法，是递归设计方法的一种具体策略，分治法在每一层递归上一般分为三个步骤：

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]; } } } 复制代码

【【Zeus】算法|算法系统学习-大事化小，小事化了（分而治之）】算法中需要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



    推荐阅读


    上一篇：小杨带你玩转C语言【初阶】|操作符知识你会了，那表达式求值呢（）

    下一篇：【Zeus】算法|算法系统学习-取数先取如何必定获胜（（相对或近似贪心））