『嗨威说』算法设计与分析 – 分治法思想小结

• 2019 年 10 月 13 日
• 筆記

本文索引目录：

一、分治算法的基本思想

二、一道二分题点拨分治思想

三、结对编程小结

一、分治算法的基本思想：

　　1.1　　基本概念：

　　“分而治之”( Divide and conquer)方法 (在ACM玩家中还有一种说法叫 分治术) ，是追求高效算法中常用的一种算法思想。

　　所谓“分而治之” 就是把一个复杂的算法问题按一定的“分解”方法分为等价的规模较小的若干部分，然后逐个解决，分别找出各部分的解，把各部分的解组成整个问题的解，这种朴素的思想来源于人们生活与工作的经验，也完全适合于技术领域。

　　1.2　　使用条件：

　　（1）问题规模当缩小到某种规模时易于解决的状态。

　　（2）分解成的子问题是相同类型的子问题，具有最优子结构性质。

　　（3）分解而成的更小的问题在解决之后可以合并出正确答案。

　　（4）子问题是相互独立的，即子问题之间没有公共的子问题，当然也可以有，但是会降低效率，在出现众多重复子问题的时候常使用动态规划dp。

　　1.3　　使用步骤：

　　（1）确定需要分解的问题大类。

　　（2）分解成小问题后，解决小问题。

　　（3）最后进行合并小问题，简称归并。

　　1.4　　常用工具：

　　递归方法，递归，是指子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的常用方法。递归有两个基本要素：
　　①边界条件，即确定递归到何时终止，也称为递归出口。
　　②递归模式，即大问题是如何分解为小问题的，也称为递归体。

　　1.5　　基本模板：

T getAns(T l, T r,T i)  {          /* 结束条件 */      if(l >= r)          return r;            /* 取得中值 */      T mid = (l+r) >> 1;            /* 二分递归 */      if(满足的条件)      return getAns(l,mid,i+1);      else              return getAns(mid,r,i+1);  } 

二、一道二分题点拨分治思想：

2.1　　题目来源：

POJ：http://poj.org/problem?id=1064

2.2　　题目题干：

Cable master

 2.3题目大意：

　　每条电缆的长度都可以达到一厘米，并且告知必须切割的长度，可以精确地切割一厘米。
　　通过编写一个程序确定可以从电缆上切下的电缆的最大可能长度，以获得指定的电缆数量。

2.4题目思路：

　　第一步：先书写满足要求的判断函数，即如下的（isGetNum）

　　第二步：套用二分模板，修改部分内容。

　　第三步：综合结果

2.5题目AC代码：

#include<stdio.h>  #include<math.h>  int n,m;  double Ntemp[10005],maxx;  bool isGetNum(double x)  {      int cnt = 0;      for(int i = 0;i<n;i++)          cnt += (int)(Ntemp[i] / x);      return cnt >= m;  }  double getAns(double l, double r,int i)  {      if(fabs(l-r) < 1e-6)          return r;      if(i == 100) return r;      double mid = (l+r) / 2;      if(!isGetNum(mid))    return getAns(l,mid,i+1);      else                return getAns(mid,r,i+1);  }  int main()  {      while(~scanf("%d %d",&n,&m))      {          maxx = 0;          for(int i = 0;i<n;i++)          {              scanf("%lf",&Ntemp[i]);              if(Ntemp[i] > maxx) maxx = Ntemp[i];          }          printf("%.2fn",floor(getAns(0,100001,1) * 100) / 100);      }      return 0;   } 

三、结对编程小结：

　　刚开始很自信的就上来打题，过了样例就很自信的提交了，结果在一些测试点WA了，思前想后都觉得代码没有问题，结果是没有完整理清题意，在部分边界处理上出了点问题，还好最后也解决了出来，在后面的题中就很顺利就求解了。

　　结对编程可以互相找出对方的不足之处，也可以齐心协力想出一个更好的算法，队友VS编码debug能力很强，编码过程愉快和谐，下次继续一起加油~。